Two magicians are about to show the next trick. A circle is drawn on the board with one semicircle marked. Viewers mark 100 points on this circle, then the first magician erases one of them. After this, the second one for the first time looks at the drawing and determines from the remaining 99 points whether the erased point was lying on the marked semicircle. Prove that such a trick will not always succeed.
Problem
Source: 239 2015 S P7
Tags: Magician, combinatorics
30.01.2024 19:37
We will first prove the following lemma: Let \(A\) be an infinite set, such that each subset of size \(n\) is colored in one of \(k\) colors. Then there is an infinite set \(B\) \(\subseteq\) \(A\), such that each subset of size \(n\) is colored in the same color. Proof: We will induct on \(n\) For \(n = 1\), each element of \(A\) is colored in one of \(k\) colors, so at least one color occurres infinitely many times. For \(n > 1\), we will prove that for every \(m\), there exists \(|B| \geq m\). Let \(C\) be a large enough subset and $d_1=d_{2} \cdots = d_k = m$, be such that for every \(i\), if we have a subset \(B \subseteq C\), such that \(|B| = d_i\) and each subset of \(B\) is colored in color \(i\), then the required set of size \(m\) exists. Let \(a \in C\) and $c_1, c_2, c_3 \cdots$ be such that each set of \(a\) and \(n-1\) elements of \(c\) are colored in color \(x\). We can do this, because we've assumed the lemma for \(n-1\). Now we update \(C:=\) {$c_1, c_2, c_3 \cdots$}. If in the new set, there is a subset \(|B| = d_{x}-1\) then we are done, so we can set \(d_{x}:=d_{x}-1\). We repeat the process arbitrarily many times, while there isn't a \(d_{i} < n\). When we have a \(d_i < n\), then there is obviously a set of size \(d_i\) which follows the requirements, because it doesn't have subsets of size \(n\) and by induction the lemma follows. Back to the problem, let the marked half be red and the other blue. Assume FTSOC that the wizards have a working strategy. If the configuration has \(100\) points in the blue half, then there are \(99\) of them, such that if wizard \(2\) sees them, then they will answer blue. Let those points be \(P_1,P_2 \cdots P_{99}\). If we have a configuration with a point \(Q\) in red and \(P_1,P_2 \cdots P_{99}\) then wizard \(1\) won't delete \(Q\). For each such \(Q\) we can color it based on which point from the blue half is deleted from wizard \(1\). Applying the lemma for \(n=1\) and \(k = 99\), we get that there is an infinite set of points in the red half, such that for each point \(Q\) in it, in the configuration \(Q,P_1,P_2 \cdots P_{99}\), the same point is deleted by wizard \(1\). WLOG that point is $P_{99}$. Now if we take \(Q_1,Q_2\) from that infinite set and \(P_1,P_2 \cdots P_{98}\), then wizard \(1\) will delete a point in the blue half. We continue this process. Each time we prove that there is an infinite set of points in red half, such that if we take point \(Q_1,Q_2 \cdots Q_x\) from it and \(P_1,P_2 \cdots P_{100-x}\), then in that configuration wizard \(1\) will delete a point in the blue half. We do this by applying the lemma for \(n = x\) and \(k = 100-x\). Eventually, there is an infinite set of points in the red half, such that if wizard \(2\) sees any \(99\) of them, then they will answer the the blue half. But if we take \(Q_1,Q_2 \cdots Q_{100}\) from that set and give them to wizard \(1\), then no matter what point they delete, wizard \(2\) will answer blue. Contradiction!