8
$\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$

3 Answers 3

12
$\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
  • 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$ Commented Sep 20, 2015 at 20:11
  • $\begingroup$ @HagenvonEitzen: You are correct. I will edit my post accordingly. $\endgroup$
    – d125q
    Commented Sep 20, 2015 at 21:30
  • $\begingroup$ This means that 14 games were played in the period between the $(k+1)$-st and the $j$-th day. Can you please explain this part a little bit more? $\endgroup$
    – Avv
    Commented Jun 28, 2021 at 15:25
9
$\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$
4
  • $\begingroup$ 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? $\endgroup$ Commented Jan 22, 2021 at 23:22
  • $\begingroup$ and why did you use the argument $2.14 <31$ when June has $30$ days? $\endgroup$ Commented Jan 22, 2021 at 23:24
  • $\begingroup$ 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? $\endgroup$ Commented Jan 22, 2021 at 23:26
  • $\begingroup$ Why the numbers $a_1, \cdots, a_{30}$ are distinct and increasing. I don't get that please? $\endgroup$
    – Avv
    Commented Jun 27, 2021 at 21:16
4
$\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=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$.

$\endgroup$
10
  • $\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$ Commented Sep 20, 2015 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$ Commented Sep 20, 2015 at 20:50
  • $\begingroup$ Why the numbers $a_1, \cdots, a_{30}$ are distinct and increasing. I don't get that please? $\endgroup$
    – Avv
    Commented Jun 27, 2021 at 21:16
  • 1
    $\begingroup$ @Avra: $g_k$ is the total number of games played on days $1$ through $k$. If they play one game on day $1$, two games on day $2$, one game on day $3$, and $11$ games on day $4$, for instance, then $g_1=1$, $g_2=1+2=3$, $g_3=1+2+1=4$, and $g_4=1+2+1+11=15$. Notice that $g_4=g_1+14$. $g_4$ is the total number of games played in the first $4$ days, and $g_1$ is the number played the first day, so $g_4-g_1$ is the total number played on days $2,3$, and $4$. And $g_4-g_1=14$, so exactly $14$ games were played during that three-day period. In this example $j=1$ and $i=4$, and days $j+1$ through ... $\endgroup$ Commented Jun 28, 2021 at 19:09
  • 1
    $\begingroup$ ... $i$ are days $2,3$, and $4$. $\endgroup$ Commented Jun 28, 2021 at 19:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .