MathDB

Nyihaha and Bruhaha are two neighbouring islands, both having

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 tell the truth or lie. When a visitor arrives on any of the two islands, the following ritual is performed: every inhabitant points randomly to another inhabitant (indepently from each other with uniform distribution), and tells "He is a Knight" or "He is a Knave'". On sland Nyihaha, Knights have to tell the truth and Knaves have to lie. On island Bruhaha every inhabitant tells the truth with probability

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

p_n

denote the probability that after observing the ritual he can rule out being on island Nyihaha. Is it true that

p_n\to 1

n\to\infty

?
Proposed by Dávid Matolcsi, Berkeley

Problem Statement