7
$\begingroup$

Your friend has given you his list of 115 best Doctor Who episodes (in order of greatness). It turns out that you have seen 60 of them. Prove that there are at least two episodes you have seen that are exactly four episodes apart on your friend’s list

$\endgroup$
  • $\begingroup$ What does four episodes apart mean? $\endgroup$ – İbrahim İpek Jul 5 '19 at 12:23
  • $\begingroup$ What have you tried so far? $\endgroup$ – Magma Jul 5 '19 at 12:25
  • $\begingroup$ If "four episodes apart" means that there are four episodes between them on the list, then there is a single counterexample to the statement. $\endgroup$ – Magma Jul 5 '19 at 12:28
  • 1
    $\begingroup$ This looks unambiguous to me. Equivalently: Given $60$ integers $(x_1,\ldots,x_{60})$ in the range $\{1,2,\ldots,115\}$, prove that there exist $i$ and $j$ such that $x_i-x_j=4$. @Magma: I don't see a counter-example to this! $\endgroup$ – TonyK Jul 5 '19 at 12:32
  • $\begingroup$ @TonyK The counterexample would be to have watched all 60 episodes with ranks ending in $1, 2, 3, 4, 5$. $\endgroup$ – Magma Jul 5 '19 at 12:36
11
$\begingroup$

Two applications of the pigeon hole principle.

First: divide the numbers $1,\cdots, 115$ into four sets according to remainder on division by $4$. It is easy to see that these subsets have either $29$ or $28$ members each. We conclude that one of them (at least) must contain at least $15$ of the episodes you have seen.

Second: If all four of them contain $15$ of the ones you have seen, then in particular the subset with $28$ elements does. Easy to see that in that case, that subset must have two consecutive episodes you have seen. If the set of $28$ does not contain $15$ of the ones you have seen, one of the sets of $29$ must contain at least $16$ of the episodes you have seen and again we are done.

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

Partition the set $S=\{1,2,\ldots,115\}$ into $S_1\cup S_2 \cup S_3 \cup S_4$, where:

$S_1=\{1,5,9,\ldots,113\}$
$S_2=\{2,6,10,\ldots,114\}$
$S_3=\{3,7,11,\ldots,115\}$
$S_4=\{4,8,12,\ldots,112\}$

Now suppose that we have $T\subset S$ such that no two elements of $T$ differ by $4$. Then $T$ can't contain consecutive elements of $S_i$ for any $i$; so it can contain at most $15$ elements from $S_1,S_2$, and $S_3$, and at most $14$ elements from $S_4$. Hence $|T|\le 59$.

Conversely, if $|T|=60$, then $T$ must contain two elements differing by $4$.

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

I like the $\bmod 4$ answers, but here’s another alternative.

Partition the episodes into $14$ blocks of eight consecutive episodes each, plus three extra episodes. At least $57$ of your episodes are among the blocks of eight. By the Pigeonhole Principle, one of the blocks must include at least five of your episodes. Use either $\bmod 4$ arithmetic or brute force to show that five episodes in a block of eight must include two episodes exactly four places apart.

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

By exhaustion (there is likely a more elegant way of finding this), you can find that the most densely you can pack episodes you have seen, without having seen 2 episodes that are 4 episodes apart, is

SSSSNNNN, where S = seen, N = not seen.

This means, at best, you will have seen 4 episodes for every 8 in his list. However, if you continue this pattern of seeing 4 missing 4, you will find that the list will have 14 lots of SSSSNNNN (56 episodes seen, 112 episodes into the list) then ending with SSS, completing the list of 115 episodes, however seeing only 59. His list would have to be at least 116 episodes long to fulfill the not-4-episodes-apart criteria. Hence, there must be at least two episodes you have seen that are exactly four episodes apart on your friend’s list.

| cite | improve this answer | |
$\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.