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 $\mathbf{0} = (0, 0, \dots, 0)$.

We will apply a classical idea of Erdős. Let $w = \overline{x_1x_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 = \mathbf{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 $\mathbf{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$.