0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ If $1\le a_j\le 45$, then $1\le a_j\le 59$. If $15\le a_j+14\le 59$, then $1\le a_j+14\le 59$. So, we can say that $1\le a_j,a_j+14\le 59$. $\endgroup$ – mathlove Nov 22 '17 at 7:17
  • $\begingroup$ Thank you @mathlove, that makes sense, but is there a visual way to see that we are filling 59 pigeonholes with 60 pigeons(in the context of this problem)? $\endgroup$ – user3252 Nov 22 '17 at 7:24
  • 1
    $\begingroup$ @user32523850925 the pigeons are the sixty numbers from the two sequences $\{a_i\}_1^{30} \cup \{a_i+14\}_1^{30}$ and the pigeonholes are the set of numbers from $1$ to $59$. $\endgroup$ – Anurag A Nov 22 '17 at 7:30
  • $\begingroup$ @AnuragA I think im looking at this very wrong, but the way im seeing it is: if we choose 1,2,3,...,30 and 1+14, 2+14,..., 30+14, we have not selected all the numbers from 1 to 59? We only selected the range 1-45 $\endgroup$ – user3252 Nov 22 '17 at 7:43
  • 2
    $\begingroup$ We only selected the range $1-45$, means that we filled only those pigeonholes numbered from $1$ to $45$. The other pigeonholes are very much there, it's only that they are not filled. The pigeonhole principle only says that "some box contains more than two pigeons". It does not say that some boxes have to be empty, or some boxes cannot have more than one pigeonhole etc. $\endgroup$ – астон вілла олоф мэллбэрг Nov 22 '17 at 7:56
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.