# Application of the pigeon hole principle

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.

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.

• Shouldn't you also use $a_0=0$ and $a_0+14$? That would make $62$ integers between $0$ and $59$ of course, but your answer actually shows that we can always pick the desired period in a way that does not include the first day (your $k+1$ is always $\ge2$). Apparently, the problem statement allows a lot of leeway – Hagen von Eitzen Sep 20 '15 at 20:11
• @HagenvonEitzen: You are correct. I will edit my post accordingly. – d125q Sep 20 '15 at 21:30

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\}$.

• what if we say there are consecutive days with 11 games played or with 9 games played? why would it be inconsistent? Where comes the value of $\{12,\ldots 15\}$ or the value of $55$ as tight bound. Can you please explain? – Muhammad Adeel Zahid Jan 22 at 23:22
• and why did you use the argument $2.14 <31$ when June has $30$ days? – Muhammad Adeel Zahid Jan 22 at 23:24
• and if $\exists_{ij} a_i = a_j + 14$ why does it warrant that there was a span of consecutive days when 14 games were played? – Muhammad Adeel Zahid Jan 22 at 23:26

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

$$0=g_0

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

$$14=h_0

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

• Actually, Brian, I realized my suggested edit also missed out on the case where k=0. Thank you for rejecting it and sorry for making an incomplete/incorrect suggestion. – Deepak Gupta Sep 20 '15 at 20:47
• @Deepak: No problem: I almost changed it to that myself before posting, until I realized that I needed $k=0$. – Brian M. Scott Sep 20 '15 at 20:50