Combinatorics: A problem of 2 Discs

Question

Two disks, one smaller than the other, are each divided into 200 congruent sectors. In the larger disk, 100 of the sectors are chosen arbitrarily and painted red; the other 100 sectors are painted blue. In the smaller disk, each sector is painted either red or blue with no stipulation on the number of red and blue sectors. The small disk is then placed on the larger disk so that their centers coincide. Show that it is possible to align the two disks so that the number of sectors of the small disk whose color matches the corresponding sector of the large disk is at least 100.

The way I attempted at this problem was that I first tried to paraphrase the question (this I often try to do), and perhaps rephrase the problem overall. One could think of 200 slots, and below each slot is another slot (200 more slots). Now, of the first 200 slots, 100 are red and 100 (the remaining) are blue. The other 200 slots below each of the former are either red or blue. It must be shown that at least 100 of these slots are paired above and below as either Red-Red or Blue-Blue. The problem is supposedly solved involving the usage of the pigeonhole principle (strong form). As hard as I tried however, I could not seem to resolve the problem. Moreover, I found a flaw in the alternate model I constructed of the question. It is possible that each of the 100 red slots and 100 blue slots get paired with the opposite color. Hence it cannot be guaranteed that at least 100 matches be made since a construction of the mismatch does exist. This error occurs due to the fact that, initially, we were discussing about circles (and they can be rotated freely to avoid mismatches, unlike slots that are fixed in place). If someone could please give reason to this problem, I would be much obliged. That you in advance.

Answer 1

Let us consider first just a single sector of the smaller disk, and the number of times it lines up successfully across all the possible configurations of the disks. As the small disk is rotated, there must be exactly 100 times that it lines up with a sector of the larger disk of the same colour, since there are 100 sectors of each colour on the large disk.

This reasoning applies for all the 200 sectors of the smaller disk. If we hence sum up all the individual instances of a match across the 200 possible configurations, we must get exactly $$100 \times 200 = 20,000$$ matches. As mentioned, there are 200 possible configurations (to see this, we can fix the larger disk in place and rotate only the smaller disk). Hence, we can use the strong form of the pigeonhole principle to complete the proof.

Let $$q_1, q_2,q_3,\ldots,q_{200}$$ be the numbers of matches on each of the 200 configurations. We know that they sum up to 200,000, and hence this is equivalent to sharing 20,000 items between 200 boxes. Since $$20,000 > 19,801 = 200 \times (100 - 1) + 1$$ by the strong form of the pigeonhole principle we know that at least one box must have at least 100 items, and so, back in the original question, at least one configuration must have at least 100 matches. Hence it is always possible to match at least 100 sectors of the small disk each to one of the same colour on the large disk.

Answer 2

A probabilistic proof:

Suppose we spin the smaller disk at random in such a way that the sectors on the two disks align exactly, so that each of the $200$ possible alignments of the two disks are equally likely. Number the sectors on the smaller disk from $1$ to $200$ and define random variables $X_i$ for $1 \le i \le 200$ by $$X_i = \begin{cases} 1 \qquad \text{if sector i on the small disk matches the sector on the larger disk} \\ 0 \qquad \text{otherwise} \end{cases}$$ Since there are equal numbers of red and blue sectors on the outer disk, $P(X_i = 1) = 1/2$ regardless of the color of sector $i$ on the smaller disk. The total number of matching sectors is $\sum_{i=1}^{200} X_i$, and by linearity of expectation, $$E \left( \sum_{i=1}^{200} X_i \right) = \sum_{i=1}^{200} E(X_i) = 200 \cdot \frac{1}{2} = 100$$ so we must have $\sum_{i=1}^{200} X_i \ge 100$ for at least one alignment; otherwise we would have $E(\sum_{i=1}^{200} X_i) < 100$.