# Combinatorics Pigeonhole problem

• Nov 18th 2013, 07:02 AM
ivanpeter
Combinatorics Pigeonhole problem
Hello to all! So i have to do this problem: In the course of an year of 365 days Peter solves combinatorics problems. Each day he solves at least 1 problem, but no more than 500 for the year. Prove that for the year there exists an interval of consecutive days in which he had solved exactly 229 problems. PS: I think that the pigeonhole principle can be used here , but i just can't show a meaningful and descriptive way of proving it.Big thanks to anyone who can help !
• Nov 18th 2013, 10:23 AM
SlipEternal
Re: Combinatorics Pigeonhole problem
Suppose he solves exactly one problem per day. Then any choice of 229 consecutive days he will solve exactly 229 problems. Work your way up through some of the base cases and you should spot a pattern.
• Nov 18th 2013, 02:18 PM
Plato
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by ivanpeter
[B]In the course of an year of 365 days Peter solves combinatorics problems. Each day he solves at least 1 problem, but no more than 500 for the year. Prove that for the year there exists an interval of consecutive days in which he had solved exactly 229 problems. PS: I think that the pigeonhole principle can be used here , but i just can't show a meaningful and descriptive way of proving it.Big thanks to anyone who can help !

Suppose that $S_k$ denotes the total number of problems done at the end of the $k^{\text{th}}$ day.

Note that $1\le S_1 < S_2~\&~S_{365}\le 500$. There are 365 different numbers there.

To each of those add 229, $S_1+229.~S_2+229.\cdots,S_{365}+229$.

So now we have 730, $S_1.~S_2,\cdots,S_{365},~S_1+229.~S_2+229.\cdots,S _{365}+229$ sums in that collection,

But each is $\le 500+229=729$

Thus there are at least two of the numbers are equal or $S_k=S_j+229$. How does that work?
• Nov 19th 2013, 06:50 AM
johng
Re: Combinatorics Pigeonhole problem
Plato,
Very clever nice solution. My only comment is that perhaps you should point out that 229 is magic; for any value greater than 229, the argument fails.
• Nov 19th 2013, 02:15 PM
SlipEternal
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by johng
Plato,
Very clever nice solution. My only comment is that perhaps you should point out that 229 is magic; for any value greater than 229, the argument fails.

It is not that magical. You can extend the argument for any positive integer up to 365. Suppose you want to find an interval of consecutive days in which Peter solves exactly $0< n < 365$ problems. For $0, Plato's argument finds the interval. Suppose $230\le n < 365$. Let $p_i$ be the number of problems Peter does on the $i$-th day of the year. Obviously, $1 \le p_i$ for all $i$. Also $S_{365} = \sum_{k = 1}^{365} p_k \le 500$. So, $p_i = S_{365} - \sum_{k = 1}^{i-1}p_k - \sum_{k = i+1}^{365}p_k \le S_{365}-364 \le 500-364 = 136$.

Next, let $k_1$ be the smallest positive integer so that $S_{k_1}> n$ and $k_2$ be the greatest positive integer so that $S_{k_2}+n \le S_{365}$. Note: $S_1 + n \le S_1+364 \le S_{365}$. So, for all $k_1 \le i \le 365$ and for all $1 \le j \le k_2$, $n < S_i \le S_{365}$ and $n < S_{j}+n < S_{365}$. There are $S_{365}-n$ positive integers in that range and there are $365-k_1+1$ terms of the form $S_i$ and $k_2$ terms of the form $S_j+n$. So, if $S_{365}-n < 366-k_1+k_2$, then by the pigeonhole principle, there must exist $n and $n such that $S_i = S_j+n$. You should be able to show that for any choice of $n$, $S_{365}-n < 366-k_1+k_2$.
• Nov 19th 2013, 02:50 PM
Plato
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by johng
My only comment is that perhaps you should point out that 229 is magic; for any value greater than 229, the argument fails.

Over the years of teaching this material, I have seen this very problem is many different disguises. I do remember when I first saw that proof. It had to be in the mid-seventies to early eighties. I was junior faculty and asked to advised undergraduate thesiss.
I do not remember where we saw. Mathematics Magazine most likely. But I no longer can find it.

As has been pointed out above, the 229 is not special except as you pointed out it is an upper bound for this particular problem.
• Nov 19th 2013, 03:02 PM
SlipEternal
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by Plato
Over the years of teaching this material, I have seen this very problem is many different disguises. I do remember when I first saw that proof. It had to be in the mid-seventies to early eighties. I was junior faculty and asked to advised undergraduate thesiss.
I do not remember where we saw. Mathematics Magazine most likely. But I no longer can find it.

As has been pointed out above, the 229 is not special except as you pointed out it is an upper bound for this particular problem.

It is not an upper bound for that problem. It is only an upper bound for that particular argument. 364 might be an upper bound for my argument, but I believe one can even find an argument for 365.
• Nov 19th 2013, 03:38 PM
Plato
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by SlipEternal
It is not an upper bound for that problem. It is only an upper bound for that particular argument. 364 might be an upper bound for my argument, but I believe one can even find an argument for 365.

$S_k-S_j=229$ that means that from the end of the $j^{\text{th}}$ day to the end of the $k^{\text{th}}$ day there were 229 problems solved.

Because $365+365=730$ and $500+229=729$ would it work for $230~?$
• Nov 19th 2013, 03:58 PM
SlipEternal
Re: Combinatorics Pigeonhole problem
But, you don't care about any of the $S_j$ where $S_j \le n$ since all of the $S_k+n > n$. So, count the number of $S_i$'s where $S_i > n$ and the number of $S_j$'s where $S_j + n \le S_{365}$ and you will find that for any $230 \le n < 365$, the number of those is greater than $S_{365}-n$. See my argument in post #5.
• Nov 19th 2013, 04:54 PM
Plato
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by SlipEternal
But, you don't care about any of the $S_j$ where $S_j \le n$ since all of the $S_k+n > n$. So, count the number of $S_i$'s where $S_i > n$ and the number of $S_j$'s where $S_j + n \le S_{365}$ and you will find that for any $230 \le n < 365$, the number of those is greater than $S_{365}-n$. See my argument in post #5.

I think you simply do not understand the argument. This same argument has been used so many times.
There is one that seems particularly clear. You can find it on page 201 of Goodaire & Parmenter, third edition.
• Nov 19th 2013, 05:20 PM
SlipEternal
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by Plato
I think you simply do not understand the argument. This same argument has been used so many times.
There is one that seems particularly clear. You can find it on page 201 of Goodaire & Parmenter, third edition.

I think you simply do not understand my argument. Let's use smaller numbers. Suppose Peter does at least one problem a day for 7 days and at most 10 problems in those seven days. You claim that because $7+7 = 14$ and $10+3 = 13$, there might not exist an interval of days such that Peter does exactly 4. I can prove to you that there is such an interval of days. There are four cases to consider.

Case 1: $S_4 = 4$. Then there are 3 number $S_5,S_6,S_7$ that are greater than 4. But then, $S_1 + 4 = 5 < 7\le S_7$, $S_2 + 4 = 6 < 7 \le S_7$, $S_3 + 4 =7 \le S_7$. That means there are six values, all in the range $\{5, \ldots, S_7\}$. Now, $S_4+4 \le S_7$ only if $S_7 \ge 8$. So, we consider only two cases: $S_7 = 7$ and $S_7 \ge 8$. If $S_7 = 7$, then $\{S_5,S_6,S_7,S_1+4,S_2+4,S_3+4\}$ are six values in the range $\{5,6,7\}$, so there must be two that are equal. If $S_7 \ge 8$, then $\{S_5,S_6,S_7,S_1+4,S_2+4,S_3+4,S_4+4\}$ are seven values in the range $\{5,6,7,8,9,10\}$. Either way, at least two must be equal.

Case 2: $S_3\le 4, S_4>4$. Then there are four numbers: $S_4,S_5,S_6,S_7$ that are greater than 4. But then, $S_1+4,S_2+4,S_3+4$ all must be less than or equal to $S_7$ since $S_7 \ge S_4+3 >7$, so $S_7 \ge 8$ and $S_3 \in \{3,4\}$, so $S_3+4 \le 8$. Again, you have seven values in a range of only 6 values.

Case 3: $S_2 \le 4, S_3>4$. Then there are five numbers: $S_3,\ldots,S_7$ that are greater than 4. But then $S_1+4,S_2+4$ must both be less than or equal to $S_7$. Again, there are seven numbers in a range of only six values, so at least two must be equal.

Case 4: $S_1 \le 4, S_2>4$. Then there are six numbers: $S_2,\ldots, S_7$ that are greater than 4. But, still, $S_1+4 \le S_7$, so there are still at least seven values in a range of only six values, so at least two must be equal.

Those are the only possible cases. This same proof can be extended to find an interval of days where Peter solves exactly 5 or 6 problems, and as I said, I believe it can even be extended to find an interval of days where Peter solves exactly 7 problems.
• Nov 19th 2013, 05:34 PM
Plato
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by SlipEternal
I think you simply do not understand my argument. Let's use smaller numbers. Suppose Peter does at least one problem a day for 7 days and at most 10 problems in those seven days. You claim that because $7+7 = 14$ and $10+3 = 13$, there might not exist an interval of days such that Peter does exactly 4. I can prove to you that there is such an interval of days. There are four cases to consider.

Case 1: $S_4 = 4$. Then there are 3 number $S_5,S_6,S_7$ that are greater than 4. But then, $S_1 + 4 = 5 < 7\le S_7$, $S_2 + 4 = 6 < 7 \le S_7$, $S_3 + 4 =7 \le S_7$. That means there are six values, all in the range $\{5, \ldots, S_7\}$. Now, $S_4+4 \le S_7$ only if $S_7 \ge 8$. So, we consider only two cases: $S_7 = 7$ and $S_7 \ge 8$. If $S_7 = 7$, then $\{S_5,S_6,S_7,S_1+4,S_2+4,S_3+4\}$ are six values in the range $\{5,6,7\}$, so there must be two that are equal. If $S_7 \ge 8$, then $\{S_5,S_6,S_7,S_1+4,S_2+4,S_3+4,S_4+4\}$ are seven values in the range $\{5,6,7,8,9,10\}$. Either way, at least two must be equal.

Case 2: $S_3\le 4, S_4>4$. Then there are four numbers: $S_4,S_5,S_6,S_7$ that are greater than 4. But then, $S_1+4,S_2+4,S_3+4$ all must be less than or equal to $S_7$ since $S_7 \ge S_4+3 >7$, so $S_7 \ge 8$ and $S_3 \in \{3,4\}$, so $S_3+4 \le 8$. Again, you have seven values in a range of only 6 values.

Case 3: $S_2 \le 4, S_3>4$. Then there are five numbers: $S_3,\ldots,S_7$ that are greater than 4. But then $S_1+4,S_2+4$ must both be less than or equal to $S_7$. Again, there are seven numbers in a range of only six values, so at least two must be equal.

Case 4: $S_1 \le 4, S_2>4$. Then there are six numbers: $S_2,\ldots, S_7$ that are greater than 4. But, still, $S_1+4 \le S_7$, so there are still at least seven values in a range of only six values, so at least two must be equal.

Those are the only possible cases. This same proof can be extended to find an interval of days where Peter solves exactly 5 or 6 problems, and as I said, I believe it can even be extended to find an interval of days where Peter solves exactly 7 problems.

Well you need to publish that. It contradicts at least thirty years of scholarship.
• Nov 19th 2013, 05:45 PM
SlipEternal
Re: Combinatorics Pigeonhole problem
Quote:

Originally Posted by Plato
Well you need to publish that. It contradicts at least thirty years of scholarship.

It does NOT contradict thirty years of scholarship. I have read through several similar proofs. The only upper bound they use is on when that particular argument applies. The converse argument is not necessarily true.