From my book Discrete Mathematics by Rosen I came across this problem:
"During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games."
The solution states that:
This part makes sense to me:
"Let $a_j$ be the number of games played on or before the jth day of the month. Then $a_1, a_2, . . . , a_{30}$ is an increasing sequence of distinct positive integers, with $1 \le a_j \le 45$."
This part confuses me:
" Moreover, $a_1 + 14, a_2 + 14, . . . , a_{30} + 14$ is also an increasing sequence of distinct positive integers, with $15 \le a_j + 14 \le 59$.
The $60$ positive integers $a_1, a_2,…,a_{30}, a_1 + 14,a_2 + 14,…,a_{30} + 14$ are all less than or equal to $59$. Hence, by the pigeonhole principle two of these integers are equal. Because the integers $a_j , j = 1, 2, . . . , 30$ are all distinct and the integers $a_j + 14, j = 1, 2, . . . , 30$ are all distinct, there must be indices i and j with $a_i = a_j + 14$. This means that exactly 14 games were played from day $j + 1$ to day $i$."
I can't understand why the author decided to create a new sequence adding 14 to each number and even with the fact that we have these 2 sequences, how are we able to use the pigeonhole principle?
Best Answer
Think of this not so much as a pigeon hole problem, but as a rat and rabbit hole problem. Rats and rabbits can't share holes with their own kind and $m$ rats and $k$ rabbits need to fit into $n < m+k$ holes. Then some holes are going to have a rat and rabbit bunking together.
So the 30 rabbits, $r_i$, are the number of games they will have practiced if they practice $14$ more than they have at this date the $i$th of Month. $r_i = a_i + 14$. $1+ 14 = 15\le r_i \le 45 + 14 = 59$. So the 30 rabbits must fit into holes numbered $15$ to $59$ and no two rabbits can share a hole (because no two $a_i$ are equal). There's plenty of holes to go around. That is not the issue.
The 30 rats, $b_i$, are the numbers of games they already have practiced on the $i $th of Month. $b_i = a_i$. $1 \le a_i \le 45$. So the $30$ rats must occupy the holes $1-45$. Again plenty of holes for all the rats. Not the issue.
So there are $59$ holes, $30$ rabbits and $30$ rats. So at least one rabbit and rat share the same hole number. That's the issue.
So there is some $r_j = b_i$ or $a_j + 14 = a_i$ so between $j$ and $i$ of the month they practiced exactly $14$ games.