Local Mathematical Competitions

Since the integers could well be distinct primes, this is equivalent to proving the stricter problem of, given a finite alphabet $A$ of $n$ letters $a_1,a_2,\dots ,a_n$, and a word $w$ of length $2^n$ on this alphabet, to show it contains a nonempty contiguous subword $x$ ($w=\overline{uxv}$, where $u,v$ could be the empty word), in which each letter appears at an even number of times.

Let us, further on, identify the letter $a_k$ with the element ${\mathbf{e}}_k\in {\mathbb{Z}}_2^n$ given by ${\mathbf{e}}_k=(0,\dots ,0,1,0,\dots ,0)$, where the 1 is at the $k$th position. Now the requirement is to find a subword such that the sum of its elements is $0=(0,0,\dots ,0)$.

We will apply a classical idea of Erdős. Let $w=\overline{x_1{x}_2\dots x_{2^n}}$ be the word, with $x_i\in \{{\mathbf{e}}_1,{\mathbf{e}}_2,\dots ,{\mathbf{e}}_n\}$ for all $i=1,2,\dots ,2^n$. Define ${\sigma }_k={\sum }_{i=1}^k{x}_i$ for all $k=1,2,\dots ,2^n$. If any of ${\sigma }_k=0$, we are done, since $\overline{x_1\dots x_k}$ can be taken as the subword; otherwise there must exist $1\le p<q\le 2^n$ such that ${\sigma }_p={\sigma }_q$, so then $0={\sigma }_q-{\sigma }_p={\sum }_{i=1}^{q-p}{x}_{p+i}$, and we can take the subword $\overline{x_{p+1}\dots x_q}$.

Let us notice that the result is tight. There exist words of length $2^n-1$ without this property. We can build them inductively. Take $w_1=\overline{a_1}$, and build $w_{n+1}=\overline{w_n{a}_{n+1}{w}_n}$ for all $n\ge 1$.