Monday, November 09, 2009

The harder hardest logic puzzle where Random can randomly say 'ja', 'da' or remain silent cannot be solved in two questions. This is not too difficult to prove.

Let the gods be arranged ABC. When the gods are in arrangement W and a question P is posed to god A we write P_W(A) for the response (an element of {y,n,s} -- (y)es, (n)o, (s)ilent).

Claim. It is not possible to solve the version of the hardest logic puzzle ever where Random randomly remains silent, answers `yes' or answers `no' in two questions.

Proof. Assume (to reach a contradiction) that it is possible, then there is a procedure for solving it in two questions. Let Q be the first question that is asked in this procedure and without loss of generality assume it is addressed to god A. There are 4 possible arrangements of T, F and R such that A \neq R and only 3 possible responses. Hence there must be two different arrangements U and V with A \neq R such that Q_U(A) = Q_V(A). Let X = RTF, Y = RFT. Then we can choose Random's responses so that Q_U(A) = Q_V(A) = Q_X(A) = Q_Y(A) = D. But then after asking Q and receiving response D all we know is that the arrangement is one of U, V, X, Y. Thus the second question must distinguish 4 possibilities with one question which is impossible.

No comments: