5
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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 $\endgroup$ – Hagen von Eitzen Sep 20 '15 at 20:11
  • $\begingroup$ @HagenvonEitzen: You are correct. I will edit my post accordingly. $\endgroup$ – d125q Sep 20 '15 at 21:30
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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=49\;.$$

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Deepak Gupta Sep 20 '15 at 20:47
  • $\begingroup$ @Deepak: No problem: I almost changed it to that myself before posting, until I realized that I needed $k=0$. $\endgroup$ – Brian M. Scott Sep 20 '15 at 20:50

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.