# Putnam Problem, Pigeonhole Principle

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.

• Again, sorry for the incredibly general explanation of my attempted work. I have gone in so many directions with this it was difficult for me to decide what bits would be beneficial to include and the post was already rather long. I can certainly elaborate on my work and observations. – Prince M Dec 17 '15 at 1:20
• What happens when $n=1?$ – Will Jagy Dec 17 '15 at 1:59
• is that a serious question? Then as long as $m > 1$ you are guaranteed a (kind of) subsequence such that its product is a perfect square. – Prince M Dec 17 '15 at 6:15
• It was a serious question. If you have a question with an integer parameter $n,$ and you can't see what is going on, you carefully examine, and prove, $n=1$ and $n=2$ and $n=3.$ Depending on the type of question, this may reveal an induction argument, maybe not, but in any case we learn something relevant. – Will Jagy Dec 17 '15 at 17:41
• From original post. "I have checked many cases to see in fact the proposition does hold, looked for patterns between cases, etc" – Prince M Dec 17 '15 at 20:21

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.
1. For some $k$ we have $S(k)=\varnothing$.
2. $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...
• Ah I see. Its interesting, I had gathered mostly all of the correct tools but could not organize my thinking towards this manner. I was too distracted considering permutations of the sequence etc. So we have $s(k) = \emptyset$ implies $\prod_{i = 1}^{k} a_{i}$ will be a perfect square and $s(k_{i}) = s(k_{j})$ implies $\prod_{s(k_{i+1})}^{s(k_{j})} a_{i}$ will be a perfect square. And also, thank you for you hint – Prince M Dec 17 '15 at 6:09
• It is obvious but I add here, for the sake of completeness, that there are only $2^n - 1$ unique $S(k)$ that do not contain a sequence that is a perfect square (we must exclude $S(k) = \varnothing$). Thus, when $m>2^n - 1$, we must have the situation of $S(k_i) = S(k_j)$ – user1936752 May 22 '17 at 6:40