Application of the pigeon hole principle

Question

There's a problem in my textbook that I'm having difficulties understanding. The solution given skips steps and is hard to decipher. The problem is as follows:

"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."

I don't know how to arrive at the conclusion of 14 games. Anyone who can help me understand this application of the pigeon-hole principle would be greatly appreciated, thank you.

Answer 1

Let $\{a_i\}_{i = 0}^{30}$ denote the number of games up until and including the $i$-th day of the month (put $a_0 = 0$). Given the conditions of the task, $\{a_i\}$ is an increasing sequence with all members distinct and $0 \leq a_i \leq 45$.

Now, consider the sequence $\{a_i + 14\}_{i = 1}^{30}$ (add $14$ to every member of the original sequence). It is also increasing with all members distinct, but with $14 \leq a_i + 14 \leq 59$. Together these sequences consist of $62$ integers between $0$ and $59$, so by the pigeonhole principle, two of them must be equal.

Since both the sequences $\{a_i\}$ and $\{a_i + 14\}$ have distinct members, there must be indices $j$ and $k$ with $j \ne k$ such that $a_j = a_k + 14$. This means that 14 games were played in the period between the $(k + 1)$-st and the $j$-th day.

Answer 2

Let $f(n)$ be the number of games played within the first $n$ days. Then we know that $f(0)=0$, $f(30)\le 45$ and $f(k+1)\ge f(k)+1$ for $0\le k<30$. If we can find $0\le i<j\le 30$ with $f(j)=f(i)+14$, this means that on days $i+1,\ldots, j$ a total of $14$ games are played and we are done.

Let $g(k)$ be the remainder of $f(k)$ modulo $14$. Then one of the $14$ possible values must occur at least $3$ times because $2\cdot 14<31$. So there are numbers $0\le a<b<c\le 30$ with $g(a)=g(b)=g(c)$. Then $f(b)-f(a)$ and $f(c)-f(b)$ are both multiples of $14$ and are both positive. If neither of them equals $14$, then $f(c)-f(b)\ge 28$ and $f(b)-f(a)\ge 28$ so that $f(c)\ge 56+f(a)\ge56$, which is absurd. We conclude that $f(b)-f(a)=14$ or $f(c)-f(b)=14$ (or both).

Remark: The problem statement is not "tight" in the following sense: The above solution works also if we allow up to $55$ games during the month; or alternatively if we replaced $14$ with any number $\in\{12,\ldots,15\}$.

Answer 3

For $k=0$ through $30$ let $g_k$ be the total number of games played up through day $k$. Then

$$0=g_0<g_1<g_2<\ldots<g_{30}\le 45\;.$$

Now let $h_k=g_k+14$ for $k=0,\ldots,29$, so that

$$14=h_0<h_1<h_2<\ldots<h_{29}=g_{29}+14<g_{30}+14\le 45+14=59\;.$$

Note that $g_1\ge 1$, and $h_{29}\le 58$.

If we can find $k$ and $\ell$ such that $h_k=g_\ell$, we’re in business, because then $g_k+14=g_\ell$, meaning that $14$ games are played on days $k+1$ through $\ell$.

There are $30$ different numbers $h_0,\ldots,h_{29}$, all lying in the range from $14$ through $58$ inclusive, and $30$ different numbers $g_1,\ldots,g_{30}$, all lying in the range from $1$ through $45$ inclusive. Altogether, then, we have $60$ numbers in the range from $1$ through $58$, and the pigeonhole principle ensures that at least two of them must be the same. The numbers $h_k$ are all distinct, and the numbers $g_\ell$ are all distinct, so some $h_k$ must be equal to some $g_\ell$: there must be $k$ and $\ell$ such that $h_k=g_\ell$.