# An interesting Putnam problem on the Pigeonhole Principle

The following problem is contained in the book “Putnam and Beyond” by Gelca, and I saw it on stackexchange. I’m mainly recording this solution because it took me longer than usual to come up with the solution, as I was led down the wrong path many a time. Noting what is sufficient for a block of numbers to be a square is the main challenge in solving this problem.

Let there be a sequence of $m$ terms, all of which belong to a set of $n$ natural numbers. Prove that if $2^n\leq m$, then there exists a block of consecutive terms, the product of which is a square number.

Let the $n$ numbers be $\{a_1,\dots,a_n\}$, and consider the function $f(k)=($ a tuple of $0$‘s and $1$‘s), where the $0$‘s and $1$‘s denote the number of times $\pmod 2$ that each element $a_i$ has appeared from the $1$st to the $k$th element of the sequence of positive integers.

So $f(1)=$($1$ somewhere, and the rest of the terms are $0$), etc.

Clearly, if $f(k)=(0,0,\dots,0)$ for any $k$, then the consecutive sequence of numbers from the 1st term to the kth terms is a square. If no $f(k)$ is $(0,0,0\dots,0)$, then there are $2^m-1$ such tuples, and at least $2^m$ values of $k$. Hence, two of them must be equal. Let us suppose that $f(k_1)=f(k_2)$. Then the sequence of terms from $k_1$ until $k_2$ is a square. Hence proved.