### 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 terms, all of which belong to a set of natural numbers. Prove that if , then there exists a block of consecutive terms, the product of which is a square number.

Let the numbers be , and consider the function a tuple of ‘s and ‘s), where the ‘s and ‘s denote the number of times that each element has appeared from the st to the th element of the sequence of positive integers.

So ( somewhere, and the rest of the terms are ), etc.

Clearly, if for any , then the consecutive sequence of numbers from the 1st term to the kth terms is a square. If no is , then there are such tuples, and at least values of . Hence, two of them must be equal. Let us suppose that . Then the sequence of terms from until is a square. Hence proved.