2
$\begingroup$

This starts with a classic pigeonhole principle question, which has appeared on Mathematics Stack Exchange before, in various forms:

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 standard solution involves defining the total number of games played by the end of day $i$ (where $i$ ranges from 1 to 30) as $a_{i}$. Since at least 1 game is played each day, $a_{1}...a_{30}$ is strictly increasing, and we can say that $1 \leq a_{i} < 45$. To find out if 14 games over some series of consecutive days is possible, we add 14 to all elements of this inequality, which yields $15 \leq a_{i}+14 < 59$, a second strictly increasing sequence. Between the two lists, we have 60 values, but each value can only be an integer ranging from 1 to 59. Therefore, by the pigeonhole principle, there must be at least 1 duplicate value in the range. Since there cannot be a duplicate value within either strictly increasing list, the duplicates must be on different lists. Therefore, there is a sequence of days on which the team must play 14 games.


To me, this is a wholly unsatisfying answer. When reading the question, it seems like the 30 days should quite obviously be the pigeons, and we need to work out how many pigeonholes there are. Here's the approach I developed.


In this problem, we need to find possible values that have a difference of 14. Start by dividing all the values from 1 to 45 into 14 sets, where each set contains all the numbers from 1 to 45 which share a common congruence modulo 14. For example, set $1$ is $\{1, 15, 29, 43\}$, set 2 is $\{2, 16, 30, 44\}$, and set 3 is $\{3, 17, 31, 45\}$.

Solutions to pigeonhole principle problems often involve considering the worst-case scenario, so the next step is to try to see how many numbers from 1 to 45 could be chosen while managing to avoid 2 numbers with a difference of exactly 14.

When any of these sets is in an ascending arrangement (as shown above), any 2 consecutive elements will have a difference of 14. You can only choose the maximum number of elements from such a set in an ascending arrangement by choosing every other element. Therefore, the maximum amount of elements which can be chosen from a set with an even order $n$ is $n/2$, The maximum amount of elements which can be chosen from a set with an odd order $n$ is $\lceil n/2 \rceil$. We can use $\lceil n/2 \rceil$ as a formula for a set of any order, to determine the maximum amount of elements which can chosen without choosing 2 elements which differ by exactly 14.

Sets 1, 2, and 3, as shown above, are sets of order 4. The remaining 11 sets, $\{4, 18, 32\},\{5, 19, 33\},...\{14, 28, 44\}$ are sets of order 3. From the order 4 sets, you can choose a maximum of $\lceil 4/2 \rceil=2$ elements without having any 2 differ by exactly 14. From the order 3 sets,you can choose a maximum of $\lceil 2/2 \rceil=2$ elements without having any 2 differ by exactly 14.

Therefore, from the set of integers from 1 to 45, we can choose at most $(3)(2)+(11)(2)=28$ elements where no 2 differ by exactly 14. They aren't hard to find, either. For example, choosing the numbers 1 through 14, avoiding the numbers 15 through 28, and then choosing the numbers 29 through 42 gives you 28 numbers, none of which differ by exactly 14. Also note that choosing just 1 more value means you must choose a number that differs from an already-chosen number by 14.

We now know that we can choose a maximum of 28 different values from this range in such a way that any 2 value do not differ by exactly 14. Since we're choosing 30 values, there must be at least 1 pair of values that differ by exactly 14.


I prefer this approach, as it doesn't add extra sets or values outside the original range, and in the process, you learn exactly the maximum amount of values you can choose in a range without having a specific difference.

I've also found an important difference in these 2 approaches. What happens if we keep the original question, but change it to ask about, say, consecutive days where the team must play 16 games.

If you use the standard approach, you still get 60 values as the pigeons, but a range of possible values from 1 to 61 as the number of pigeonholes. This suggests that we can't apply the pigeonhole principle to this problem.

If you use the approach I developed, you work out that you can choose a maximum of $(13)(\lceil 3/2 \rceil)+(3)(\lceil 2/2 \rceil)=29$ different integer values (such as 1 through 16 and 33 through 45) from 1 to 45 without having any 2 differ by exactly 16. By the pigeonhole principle, it is impossible to choose 30 values from 1 to 45 without some 2 of those values having a difference of 16.


Here's my question: Both of these can't be right. What is the reason for the different answers? Is my approach flawed somehow? If so, how? Am I missing some assumption for the standard approach which doesn't apply to 16?

$\endgroup$
1
$\begingroup$

I think your approach is quite neat, and can be made a bit more efficient as follows (it starts getting hard to make it an explicit pigeonhole approach, though that is in the background).

First observe that if you take the $a_i$ as defined, and if the $14$-match criterion is not met, then if $a_i\equiv a_j \bmod 14$ we have that $a_i$ and $a_j$ must differ by at least $28$. So we can't have $a_i\lt a_j \lt a_k$ in the same residue class as this would imply $a_k\gt 56$. We therefore have at most two representatives of each residue class, and just $14$ classes. That allows numbers to cover at most $28$ days. Note that $28$ is possible because $14+28=42$ and the last residue class can have two representatives.

For $16$ the same applies - two residues only can be chosen from each class. But $45-32=13$ and the residue classes corresponding to $14,15,16$ can only have one representative - hence the maximum number of days is $2\times 13+3=29$ as you observe.

I think there are sometimes contortions in using the pigeonhole principle when really what is happening is a simple counting argument (underneath they are the same thing really, but proofs get unhelpfully formalised and made more complicated than they need to be). That said there is nothing wrong with the original proof - as you have shown it doesn't give the sharpest result.

$\endgroup$
1
$\begingroup$

That the standard approach fails in proving that there will be consecutive days with a total of 16 games does not mean it proves there aren't such a set of days, so the only (but quite important) thing you've realised is that your method enables you to prove a stronger result.

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