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$
5
  • $\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, 2015 at 1:20
  • $\begingroup$ What happens when $n=1?$ $\endgroup$
    – Will Jagy
    Dec 17, 2015 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, 2015 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, 2015 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, 2015 at 20:21

2 Answers 2

7
$\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$
2
  • $\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, 2015 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$ May 22, 2017 at 6:40
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .