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

• You should be able to solve it with some modification using the solution from Textbook, Problem 3.3.24 math.fau.edu/schonbek/probsol/ProbSolfa10midtermNotes.pdf – meta_warrior Nov 18 '13 at 15:21
• I still don't quite get it because in my case [500/229]=2 and the tn-tk and tm-tk won't work.Could you please right it down in more detail. – randomname Nov 18 '13 at 15:45
• Each day you add 1 or more problems.It would be a bummer if he solved 2 problems each day, because then the sum at each point would be even and you would never get 229. However since he solves no more than 500 a year there will be days when he solves only 1 problem. I dont know how to continue, perhaps this partial ansewer will somehow help you. – Adam Nov 18 '13 at 15:57
• Also, each day he cannot solve more than 500-364 problems because if he solved more then even if on all the rest of days he solved just one problem, the total would exceed 500. – Adam Nov 18 '13 at 16:07
• Well i was thinking that there should be at least 2 periods of days witch give the same remainder by mod 229. So p1-p2 or p1+p2 give 0 by mod229 or p1+p2 = 229 , 498 and so on.Obviously it can't be 0 because he plays at least 1 game per day but i don't see the problem with 498 . – randomname Nov 18 '13 at 16:29

## 2 Answers

Let $a_1$ be the number of combinatorics problems solved on the first day, $a_2$ be the total number of combinatorics problems solved on the first and second days, and so on. The sequence of numbers $a_1,a_2,...,a_{365}$ is an increasing sequence since each term of the sequence is larger than the one that precedes it and at least one combinatorics problem is solved each day. Since he solves no more than $500$ combinatorics problems for the year we know that $1\leq a_1\leq a_2\leq \cdots \leq a_{365}\leq 500$. The sequence $a_1+229$, $a_2+229$, and so on is also an increasing sequence. So $230\leq a_1+229\leq a_2+229\leq \cdots \leq a_{365}+229 \leq 729$. Each of the $730$ numbers, that is $a_1,a_2,...,a_1+229+a_2+229,...$ is an integer between $1$ and $729$. It follows that two of them are equal since no two of the numbers $a_1,a_2,...$ are equal and no two of the numbers $a_1+229,a_2+229,...$ are equal. There must exist an $i$ and a $j$ such that $a_i=a_j+229$. Thus on days $j+1$, $j+2$,..., $i$ there exists consecutive days when the student solves $229$ combinatorics problems.

• really nice and understandable solution . – Boris Morozov Mar 17 '14 at 17:00

Lets consider partial sums. $A(x)$ is a sum of problems after $x$ days. Now what is the remainder of $A(x)$ divided by $229$? $A(x)$ changes as days go by, there are only $229$ possible remainders and $365$ days - so there must be two days $x$ and $y$, where $A(x)$ and $A(y)$ have the same remainder. $A(x)$ and $A(y)$ represent sums of problems of two overlapping periods. $A(x)$ is the larger period (you can assume this). $A(x)-A(y)$ is divisible by 229 and is positive. $A(x)-A(y)$ also represents a sum of problems of a certain period (since the two periods are overlapping, just take the larger period and disregard the part of the larger period that is the smaller period.

In any $55$ days he must have solved at least $55$ problems, therefore in $310$ days he must have solved at most $500-55=445$ problems which is less than $458$. There are only $229$ remainders, but $310$ days therefore in the $310$ days, there must be two days $x$ and $y$ such that $A(x)-A(y)$ is divisible by $229$, we also know that it is smaller than $458$, therefore it has to be equal to $229$.

• I know that because 498 is not divisible by 229 and A_x-A_y is divisible by 229. – Adam Nov 18 '13 at 17:21
• That was supposed to be 2*229=458<500. – randomname Nov 18 '13 at 17:29