6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Prince M Dec 17 '15 at 1:20
  • $\begingroup$ What happens when $n=1?$ $\endgroup$ – Will Jagy Dec 17 '15 at 1:59
  • $\begingroup$ 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. $\endgroup$ – Prince M Dec 17 '15 at 6:15
  • $\begingroup$ 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. $\endgroup$ – Will Jagy Dec 17 '15 at 17:41
  • $\begingroup$ From original post. "I have checked many cases to see in fact the proposition does hold, looked for patterns between cases, etc" $\endgroup$ – Prince M Dec 17 '15 at 20:21
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Prince M Dec 17 '15 at 6:09
  • $\begingroup$ 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)$ $\endgroup$ – user1936752 May 22 '17 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.