Problem A. 874. (February 2024)
A. 874. Nyihaha and Bruhaha are two neighbouring islands, both having \(\displaystyle n\) inhabitants. On island Nyihaha every inhabitant is either a Knight or a Knave. Knights always tell the truth and Knaves always lie. The inhabitants of island Bruhaha are normal people, who can choose to say whatever they want. When a visitor arrives on any of the two islands, the following ritual is performed: every inhabitant points randomly to another inhabitant (independently from each other with uniform distribution), and says ``He is a Knight'' or ``He is a Knave''. On island Nyihaha, Knights have to tell the truth and Knaves have to lie. On island Bruhaha every inhabitant says either ``He is a Knight'' or ``He is a Knave'' with probability \(\displaystyle 1/2\) independently from each other. Sinbad arrives on island Bruhaha, but he does not know whether he is on island Nyihaha or island Bruhaha. Let \(\displaystyle p_n\) denote the probability that after observing the ritual he can rule out being on island Nyihaha. Is it true that \(\displaystyle p_n \to 1\) if \(\displaystyle n \to \infty\)?
Proposed by Dávid Matolcsi, Berkeley
(7 pont)
Deadline expired on March 11, 2024.
Let's form a directed graph from the inhabitants of the island that indicates who points to whom. The out-degree of all the vertices is 1. Let's put 0's on the edges that correspond to someone saying 'Knight', and let's put 1's on the edges corresponding to someone saying 'Knave'. If it's possible to assign 0's and 1's on the vertices such that \(\displaystyle a+x=b\) mod 2 is true for all directed edges (\(\displaystyle a\) and \(\displaystyle b\) are the values assigned to the vertices, and \(\displaystyle x\) is the value assigned to the edge), then Sinbad cannot be sure that he is not on island Nyihaha. Indeed, if \(\displaystyle A\) is calling \(\displaystyle B\) a Knight, than they have to be of the same type, while if he is calling \(\displaystyle B\) a Knave, then they have to be of different type.
Such an assignment exists if and only if every directed cycle in the graph includes an even number of 1's. On the one hand, an odd number of 1's in a cycle means this cycle cannot be labeled correctly with 0's and 1's. On the other hand, if no such cycle exists, then we can pick an arbitrary vertex in each connected component, assign an arbitrary value, and then assign every other value according to the values written on the edges.
All the directed cycles in the graph must be disjoint from each other, since all the out-degrees are 1. On the other hand, in a single cycle the number of 1's has a \(\displaystyle 1/2\) chance of being even: let's assign values randomly to the edges in the cycle, and the last one will decide the parity of the 1's. These imply that if the number of cycles is \(\displaystyle t\), then there is a \(\displaystyle 1/2^t\) chance that all the cycles contain an even number of 1's.
Therefore, if the graph created from the answers of inhabitants of Bruhaha contains \(\displaystyle t\) cycles, then there is a \(\displaystyle 1/2^t\) chance that the answers could also be the answers of the inhabitants of Nyihaha.
We will prove that for every \(\displaystyle t\) the chance that there are at least \(\displaystyle N\) cycles in the graph of \(\displaystyle n\) points goes to 1 as \(\displaystyle n\) goes to infinity.
This will prove that the answer to the question in the problem is affirmative. For a given \(\displaystyle \varepsilon>0\) we can find \(\displaystyle N\) such that \(\displaystyle 1/2^t<\varepsilon/2\), and also a \(\displaystyle N\) such that for \(\displaystyle n>N\) the chance that there at least \(\displaystyle T\) cycles in the graph is less, than \(\displaystyle \varepsilon/2\). Therefore, the probability that Sinbad cannot rule out that the answers are from Nyihaha is less then \(\displaystyle \varepsilon/2+1\cdot\frac{1}{2^t}<\varepsilon\). This proves that \(\displaystyle p\) goes to 1 as \(\displaystyle n\) goes to infinity (by the definition of convergence).
Now we will prove that the probability of having at least \(\displaystyle t\) cycles indeed goes to infinity as \(\displaystyle n\) goes to infinity (for every fixed \(\displaystyle t\)).
Since the inhabitants of Bruhaha point independently from each other, the order of their answers is irrelevant. Let's consider the following order: we start from an arbitrary inhabitant, and then follow with the person he is pointing to. We keep on doing this until we get to somebody who has already answered. Then we continue with another inhabitant chosen randomly, and follow the chain of their answers. We repeat this process until everybody has answered.
We will divide the whole process into sections. We say that an Event happens in a section of length \(\displaystyle k\), if nobody of these \(\displaystyle k\) inhabitants points at somebody who has already answered before the section, but somebody from the second \(\displaystyle k/2\) points at somebody from the first \(\displaystyle k/2\) of the section.
Whenever an Event happens in a section, there exists inhabitant \(\displaystyle A\) in the second half of the section who points at inhabitant \(\displaystyle B\) from the first half of the section. If a chain goes from \(\displaystyle B\) to \(\displaystyle A\), we have found a cycle from the inhabitants the section. Otherwise a new chain had to be started in the section, which means that somebody from the section pointed at somebody who has already answered, however, that person also must be in the section by the definition of the Event, therefore we get a cycle again. Thus, an Event guarantees a cycle in the section.
Suppose that \(\displaystyle r\) people have already pointed before a section of \(\displaystyle k\) people. The probability of nobody pointing to an earlier inhabitant is \(\displaystyle (1-\frac{r}{n})^k\). The conditional probability of nobody pointing to the first section is \(\displaystyle (1-\frac{k/2}{n-r})^{\frac{k}{2}}\). Therefore, the probability of the Event in this section is
\(\displaystyle \left(1-\frac{r}{n}\right)^k\left(1-\left(1-\frac{\frac{k}{2}}{n-r}\right)^{\frac{k}{2}}\right)\ge \left(1-\frac{r}{n}\right)^k\left(1-\left(1-\frac{\frac{k}{2}}{n}\right)^{\frac{k}{2}}\right).\)
Let's choose the length of the sections to be \(\displaystyle \sqrt{n}, \frac{\sqrt{n}}{\sqrt{2}}, \frac{\sqrt{n}}{\sqrt{3}} \ldots\), until we reach \(\displaystyle n\). The number of inhabitants before the \(\displaystyle m^{\text{th}}\) section is
\(\displaystyle r=\sqrt{n} \sum_{k=1}^{m-1} \frac{1}{\sqrt{k}}\le \sqrt{n} \left(1+\sum_{k=2}^{m-1} \frac{2}{\sqrt{k-1}+\sqrt{k}}\right)=\sqrt{n}\left(1+2\sum_{k=2}^{m-1} (\sqrt{k}-\sqrt{k-1})\right) < 2\sqrt{n}\sqrt{m}.\)
Therefore \(\displaystyle \frac{r}{n} < \frac{2\sqrt{m}}{\sqrt{n}}\).
This means that the probability of an Event in the \(\displaystyle m^{\text{th}}\) section is at least
\(\displaystyle \left(1-\frac{2\sqrt{m}}{\sqrt{n}}\right)^{\frac{\sqrt{n}}{\sqrt{m}}}\left(1-\left(1-\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}\right).\)
We will only work with sections for which \(\displaystyle m\le \sqrt{n}\). It is well known that \(\displaystyle (1-x)^{\frac{1}{x}}\to e^{-1}\) as \(\displaystyle x\to 0\). If \(\displaystyle n\) is large enough, then \(\displaystyle \frac{2\sqrt{m}}{\sqrt{n}}\) will be arbitrarily small, thus \(\displaystyle (1-\frac{2\sqrt{m}}{\sqrt{n}})^{\frac{\sqrt{n}}{\sqrt{m}}}\) can be arbitrarily close to \(\displaystyle e^{-\frac{1}{2}}\). We will only use the fact that this is larger than \(\displaystyle 1/2\) (since \(\displaystyle e<4\)).
Therefore the probability of an event is at least
\(\displaystyle \frac{1}{2} \left(1-\left(1-\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}\right).\)
Let's estimate the subtrahend inside the brackets from above:
\(\displaystyle \left(1-\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}\le \frac{1}{\left(1+\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}}\le\frac{1}{1+\frac{1}{4m}},\)
where the second estimation is the consequence of Bernoulli's inequality (i.e. \(\displaystyle (1+x)^n\ge 1+xn\) if \(\displaystyle n\) is natural and \(\displaystyle x\ge -1\) real):
\(\displaystyle \left(1+\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}\ge 1+\frac{1}{4m}.\)
Finally,
\(\displaystyle \frac{1}{1+\frac{1}{4m}}\le 1-\frac{1}{5m},\)
therefore, the probability of an Event is at least
\(\displaystyle \frac{1}{2}\left(1-\left(1-\frac{1}{5m}\right)\right)=\frac{1}{10m}.\)
Having Events in the sections are independent from each other. Therefore if we take residue \(\displaystyle d\) mod \(\displaystyle t\), the probability that no Event will occur in a section with a number that is \(\displaystyle d\) mod \(\displaystyle t\) up to \(\displaystyle m=\sqrt{n}\) can be estimated as
\(\displaystyle \prod_{j=0}^{\frac{\sqrt{n}}{t}} \left(1-\frac{1}{10(jt+d)}\right)\le \sqrt[10t]{{\prod_{i=10t+1}^{10\sqrt{n}}} \left(1-\frac{1}{i}\right)}=\sqrt[10t]{\frac{10t}{10\sqrt{n}}}=\frac{\sqrt[10t]{t}}{\sqrt[20t]{n}}.\)
Therefore the probability that an Event will occur for every residue class is at least
\(\displaystyle \left(1-\frac{\sqrt[10t]{t}}{\sqrt[20t]{n}}\right)^t\ge 1-\frac{t\sqrt[10t]{t}}{\sqrt[20t]{n}}\)
(we have applied Bernoulli's once more).
Since \(\displaystyle t\) is fixed, then
\(\displaystyle 1-\frac{t\sqrt[10t]{t}}{\sqrt[20t]{n}}\to 1\)
as \(\displaystyle n\to \infty\) Thus we have proved that as \(\displaystyle n\to \infty\), the probability of at least \(\displaystyle t\) Event occuring, i.e. having at least \(\displaystyle t\) cycles in the graph goes to 1, which was our aim.
Statistics:
7 students sent a solution. 7 points: Wiener Anna. 4 points: 1 student. 3 points: 1 student. 2 points: 1 student. 1 point: 1 student. 0 point: 2 students.
Problems in Mathematics of KöMaL, February 2024