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 !
Combinatorics – Pigeonhole Principle Problem
combinatoricsdiscrete mathematicspigeonhole-principle
Best Answer
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.