4
$\begingroup$

This is a problem based on pigeon hole principle.

A tennis player has three weeks to prepare for a tennis tournament. She decides to play at least one set every day but not more than 36 in all. Show that there is a period of consecutive days during which she will play exactly 21 sets.

Can some one please help me to solve this problem.

$\endgroup$
4
$\begingroup$

Let $r_i$ be the number of sets played up to and including day $i$. So

$0 = r_0 < r_1 < r_2 < ... < r_{21} \leq 36$

So there are 37 pigeonholes - possible values - for the 22 pigeons - the $r_i$.

However, we are looking for pairs $i, j$ with $r_j = r_i + 21$ - since such a pair would tell us that 21 sets were played on days $i+1$ through to $j$. So if we assume there are no such pairs, we can "combine" the pigeonholes $i$ and $i + 21$. So we have the following pigeonholes:

$\{0 \text{ or } 21\}, \{1 \text{ or } 22\}, ..., \{15 \text{ or } 36\}, \{16\}, ... \{20\}$.

And we have 22 pigeons, 21 pigeonholes, giving a contradiction.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

This is very similar to the How are the pigeonholes calculated in this pigeon-hole problem?

To answer this specific question - using the same logic and process from the reference answer above:

$1 < r_1 < r_2 < r_3 \ldots < r_{21} \le 36$

Doing $r_i+21$:

$22 < r_1+21 < r_2+21 < r_3+21 \ldots < r_{21}+21 \le 57 \,(=36+21)$

$r_i$ is 21 values and $r_i+21$ is 21 values.

So we have 42 pigeons and 57 pigeonholes.

Edited to correct my calculation of pigeonholes. I then don't see how to solve the question and also note the difference between my number of pigeons/pigeonholes and the other answer.

I also note that if she runs once every day and twice on the last day she will have run 22 times - which is not exactly 21 times.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It seems to me that there are $57$ pigeonholes, not $41$. Where do you get $41$ from? $\endgroup$ – Christopher Sep 16 '14 at 11:46
  • $\begingroup$ You are correct - which I think invalidates the logic - back to the drawing board.... $\endgroup$ – AndyL Sep 16 '14 at 13:37

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.