# Question prove pigeonhole principle - Need an explanation [Full answer provided]

Training for game throughout 11 weeks, practicing at least 1 game per day and max 12 games per week Proof that there is number of days sequence that equal to 21 games

$$x_{i}$$ sum of number of games until day $$i$$

$$1\leq x_{1}< x_{2}..\leq x_{77}= 12*11 =132$$

we need to find $$x_{i} - x_{j} = 21$$ or $$x_{j}=x_{i}+21$$ then we can claim that sequence of days sum are 21 games

$$22\leq x_{1}+21< x_{2}+21..\leq x_{77}+21=153$$

{$$x_{1},x_{2},..,x_{77}$$}, {$$x_{1}+21,x_{2}+21,..,x_{77}+21$$} we have 154 numbers. the sum can range from 1 to 153 so there is 154 cells and 153 pigeon

so, $$\left \lceil \frac{154}{153} \right \rceil = 2$$ we get two equal number in same cell

My question:

• Why 21 was added to the inequality ?
• Becuase you want to prove there is an $x_j = x_i + 21$. And we do that bylooking at the ranges of all possible $x_j$ and at the range of all possible $x_i + 21$ we seeing if there must be some overlap. If the range of $x_j$ is $1$ through $132$ then the range if $x_i +21$ is $22$ through $153$. – fleablood Aug 25 '20 at 18:30

If there is an $$i,j$$ such that $$x_i-x_j = 21$$ then $$\{x_i,x_j\}\cap\{x_i+21,x_j+21\}$$ will be non-empty.
Or, the number of members of $$\{x_i,x_j\}\cup\{x_i+21,x_j+21\}$$ will be less than the number of sum of the number of members of each set.
Contrariwise, if the number of members of the set $$\{x_1,\cdots, x_{77}\}\cup \{x_1+21,\cdots, x_{77}+21\}$$ is less than $$77+77$$ then there is at least one member of each subset that are the same.
• why $x_{i}−x_{j}=21$ can't be found in the first inequality ? – Mostfa shma Aug 25 '20 at 18:10
• How do you intend to compare all possible $i,j$ pairs to show that at least one is equal? This is a shot-gun approach, that allows us to check the set en-masse. – Doug M Aug 25 '20 at 18:11
• assuming $x_{6}=42 x_{3}=21, 6=i, 3=j$ then what are the sequence elements in $x_{i}-x_{j}$? – Mostfa shma Aug 25 '20 at 18:17
• They aren't ordered in sequence. You have $x_6-x_5, x_6- x_4, x_6-x_3, x_5-x_4, x_5-x_3, x_4 -x_3$. But we don't just have $x_6$ through $x_3$ we have $x_77$ through $x_1$ so that is $\frac {77*76}2$ possible $x_j - x_i$ and there is no need that we can tell than any of them have to be $21$. The smallest they can be is $1$ and the largest is $131$ so they must double up we have no reason that any of them must be $21$. – fleablood Aug 25 '20 at 18:38