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 !
Suppose that denotes the total number of problems done at the end of the day.
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?
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 problems. For , Plato's argument finds the interval. Suppose . Let be the number of problems Peter does on the -th day of the year. Obviously, for all . Also . So, .
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 , .
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.
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.
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 and , 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: . 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.