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.
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 !
Note that . There are 365 different numbers there.
To each of those add 229, .
So now we have 730, sums in that collection,
But each is
Thus there are at least two of the numbers are equal or . How does that work?
Next, let be the smallest positive integer so that and be the greatest positive integer so that . Note: . So, for all and for all , and . There are positive integers in that range and there are terms of the form and terms of the form . So, if , then by the pigeonhole principle, there must exist and such that . You should be able to show that for any choice of , .
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.
But, you don't care about any of the where since all of the . So, count the number of 's where and the number of 's where and you will find that for any , the number of those is greater than . See my argument in post #5.
Case 1: . Then there are 3 number that are greater than 4. But then, , , . That means there are six values, all in the range . Now, only if . So, we consider only two cases: and . If , then are six values in the range , so there must be two that are equal. If , then are seven values in the range . Either way, at least two must be equal.
Case 2: . Then there are four numbers: that are greater than 4. But then, all must be less than or equal to since , so and , so . Again, you have seven values in a range of only 6 values.
Case 3: . Then there are five numbers: that are greater than 4. But then must both be less than or equal to . Again, there are seven numbers in a range of only six values, so at least two must be equal.
Case 4: . Then there are six numbers: that are greater than 4. But, still, , 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.