# 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...

Since you asked for hints rather than a solution I'll leave it there....

• 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

I'll just add my own solution to this. 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.