I have never attempted or considered any contest math problems, but I recently found a page of Putnam Prep problems in a recycling bin on campus and decided to give some a try since I am home for break. I am a bit embarrassed I cannot solve this one, looking for a prod in the right direction. Hints before full solutions preferred but all responses appreciated.
Use the Pigeonhole Principle to prove the following:
A sequence of $m$ positive integers contains exactly $n$ distinct terms. Show that if $2^{n} \leq m$, there exists a block of consecutive terms who's product is a perfect square.
The statement of the Pigeonhole Principle offered on the page is:
If $kn+1$ pigeons are placed in $n$ pigeonholes, then there is some pigeonhole that contains at least $k+1$ pigeons.
I searched for a solution but could not find one, it does however appear that this question is from chapter 1 of Putnam and Beyond by Razvan Gelca.
I have heard that competition math problems are sometimes relatively easy problems disguised as harder problems and the trick is to manage to find the easy problem embedded within in a timely manner, that may be the case here, as I seem to be arriving at many possible routes of investigation that lead me no where and just eat up time!
Since I have tried many extremely different approaches to this problem over the last two hours I will be brief with what I have tried but I can elaborate on any individual piece upon request. I have reworded the proposition in many ways, I have considered parity, permutations, combination, contraposition, I have checked many cases to see in fact the proposition does hold, looked for patterns between cases, etc. Considered different generalizations of the pigeonhole principal.
Best Answer
Call the sequence $a_1,\ldots,a_m$ and the $n$ distinct terms $t_1,\ldots,t_n$. For each $k$ from $1$ to $m$ define the set $$S(k)=\{j\mid \hbox{$t_j$ occurs an odd number of times among $a_1,\ldots,a_k$}\}\ .$$ Now consider two cases.
For some $k$ we have $S(k)=\varnothing$.
$S(k)$ is never empty. Then there are fewer than $m$ distinct $S(k)$ so at some point we have $S(k_1)=S(k_2)$ and then...
Since you asked for hints rather than a solution I'll leave it there....