Where did 33 come from in this pigeon hole principle problem?

Question

I have thought about this for some time and I can't justify how they got the number 33. For the $1\leq x_1<x_2<...<x_{20}\leq 33$, it should be $1 \leq x_1<x_2<...<x_{20} = 35$ because the total number of calls at the end of the last day should be 35.

However, if we continue the in the same way, then we arrive at 40 integers under 41 in which the pigeonhole principle does not help. Where did 33 come from, or is there a different way to solve this problem?

Answer 1

Here's how you can adapt the existing solution to work for 35 calls, which is a deeper application.

Include $ x_0 = 0$ (which makes sense because otherwise we're ignoring what Susan does on the first day).
As per before, we have
$0 \leq x_0 < x_1 < \ldots < x_{20} \leq 35.$
$6 \leq x_0 + 6 < x_1 + 6 < \ldots < x_{20} + 6 \leq 35+6 = 41. $

There are 42 integers (pigeons), which range from $0$ to $41$ (holes).

If the integers are distinct, then
$ \sum_{i=0}^{41} i = \sum x_i + \sum (x_i + 6) = \sum ( 2 x_i + 6)$.
However, observe that the LHS is odd and the RHS is even, so this is a contradiction.

Hence, (at least) 2 of the integers are not distinct, which means we have $x_i = x_j + 6$.

---

Notes

• The inclusion of $x_0$ would have allowed us to make the conclusion for 34 calls using PP directly.
• 36 and 37 calls are not possible. See below.
• For 38 calls, I have the counter example of 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 7, 1, 1

---

For 36 calls, we have 42 integers (pigeons) which range from 0 to 42 (holes).
If the integers are distinct, then consider their values mod 6.

• Holes: Mod 6, we have 8/7/7/7/7/7 holes.
• Taken mod 6, $x_i$, $x_i + 6$ pigeons are in the same mod 6 hole.
• Hence, each hole has an even number of pigeons.
• Hence, there are at most $8 + 6 + 6 + 6 + 6 + 6 = 38 $ pigeons, which is a contradiction.

---

For 37 calls, we have 42 integers (pigeons) which range from 0 to 43 (holes).

If the integers are distinct, then consider their values mod 6.

• Holes: Mod 6, we have 8/8/7/7/7/7 holes.
• Taken mod 6, $x_i$, $x_i + 6$ pigeons are in the same mod 6 hole.
• Hence, each hole has an even number of pigeons.
• Hence, there are at most $8 + 8 + 6 + 6 + 6 + 6 = 40 $ pigeons, which is a contradiction.

35 calls using the above formulation.

If the integers are distinct, then consider their values mod 2.

• Holes: Mod 2, there are 21/21 holes.
• Taken mod 2, the $x_i$ and $x_i + 6$ pigeons are in the same mod 2 hole.
• Hence, each hole has an even number of pigeons.
• Hence, there are at most $20 + 20 = 40$ pigeons, which is a contradiction.