Results 1 to 13 of 13
Like Tree1Thanks
  • 1 Post By Plato

Math Help - Combinatorics Pigeonhole problem

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    Paris
    Posts
    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 !
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by ivanpeter View Post
    [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?
    Last edited by Plato; November 18th 2013 at 03:22 PM.
    Thanks from johng
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    688
    Thanks
    281

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by johng View Post
    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<n<230, 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<S_i\le S_{365} and n<S_j+n\le S_{365} 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by johng View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by Plato View Post
    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.
    Last edited by SlipEternal; November 19th 2013 at 04:09 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by SlipEternal View Post
    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~?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by SlipEternal View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by Plato View Post
    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.
    Last edited by SlipEternal; November 19th 2013 at 06:31 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by SlipEternal View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Combinatorics Pigeonhole problem

    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 16th 2013, 03:20 AM
  2. a pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 11th 2010, 02:33 AM
  3. Pigeonhole Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 15th 2009, 05:31 PM
  4. Pigeonhole problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: October 18th 2008, 03:41 PM
  5. A pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 12th 2007, 11:22 AM

Search Tags


/mathhelpforum @mathhelpforum