# Thread: Combinatorics Pigeonhole problem

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

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

3. ## Re: Combinatorics Pigeonhole problem

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 $\displaystyle S_k$ denotes the total number of problems done at the end of the $\displaystyle k^{\text{th}}$ day.

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

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

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

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

Thus there are at least two of the numbers are equal or $\displaystyle S_k=S_j+229$. How does that work?

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

5. ## Re: Combinatorics Pigeonhole problem

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 $\displaystyle 0< n < 365$ problems. For $\displaystyle 0<n<230$, Plato's argument finds the interval. Suppose $\displaystyle 230\le n < 365$. Let $\displaystyle p_i$ be the number of problems Peter does on the $\displaystyle i$-th day of the year. Obviously, $\displaystyle 1 \le p_i$ for all $\displaystyle i$. Also $\displaystyle S_{365} = \sum_{k = 1}^{365} p_k \le 500$. So, $\displaystyle 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 $\displaystyle k_1$ be the smallest positive integer so that $\displaystyle S_{k_1}> n$ and $\displaystyle k_2$ be the greatest positive integer so that $\displaystyle S_{k_2}+n \le S_{365}$. Note: $\displaystyle S_1 + n \le S_1+364 \le S_{365}$. So, for all $\displaystyle k_1 \le i \le 365$ and for all $\displaystyle 1 \le j \le k_2$, $\displaystyle n < S_i \le S_{365}$ and $\displaystyle n < S_{j}+n < S_{365}$. There are $\displaystyle S_{365}-n$ positive integers in that range and there are $\displaystyle 365-k_1+1$ terms of the form $\displaystyle S_i$ and $\displaystyle k_2$ terms of the form $\displaystyle S_j+n$. So, if $\displaystyle S_{365}-n < 366-k_1+k_2$, then by the pigeonhole principle, there must exist $\displaystyle n<S_i\le S_{365}$ and $\displaystyle n<S_j+n\le S_{365}$ such that $\displaystyle S_i = S_j+n$. You should be able to show that for any choice of $\displaystyle n$, $\displaystyle S_{365}-n < 366-k_1+k_2$.

6. ## Re: Combinatorics Pigeonhole problem

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.

7. ## Re: Combinatorics Pigeonhole problem

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.

8. ## Re: Combinatorics Pigeonhole problem

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.
$\displaystyle S_k-S_j=229$ that means that from the end of the $\displaystyle j^{\text{th}}$ day to the end of the $\displaystyle k^{\text{th}}$ day there were 229 problems solved.

Because $\displaystyle 365+365=730$ and $\displaystyle 500+229=729$ would it work for $\displaystyle 230~?$

9. ## Re: Combinatorics Pigeonhole problem

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

10. ## Re: Combinatorics Pigeonhole problem

Originally Posted by SlipEternal
But, you don't care about any of the $\displaystyle S_j$ where $\displaystyle S_j \le n$ since all of the $\displaystyle S_k+n > n$. So, count the number of $\displaystyle S_i$'s where $\displaystyle S_i > n$ and the number of $\displaystyle S_j$'s where $\displaystyle S_j + n \le S_{365}$ and you will find that for any $\displaystyle 230 \le n < 365$, the number of those is greater than $\displaystyle 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.

11. ## Re: Combinatorics Pigeonhole problem

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

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

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

Case 4: $\displaystyle S_1 \le 4, S_2>4$. Then there are six numbers: $\displaystyle S_2,\ldots, S_7$ that are greater than 4. But, still, $\displaystyle 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.

12. ## Re: Combinatorics Pigeonhole problem

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

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

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

Case 4: $\displaystyle S_1 \le 4, S_2>4$. Then there are six numbers: $\displaystyle S_2,\ldots, S_7$ that are greater than 4. But, still, $\displaystyle 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.

13. ## Re: Combinatorics Pigeonhole problem

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.