Sunday, October 01, 2006

Gods: { A, B, C} = { Mr. True, Mr. False, Mr. Random }

Given a question Q, let E(Q) be the question
"If I asked you Q, would you say ja?"

Lemma 1: If we ask Mr. True or Mr. False E(Q), a
response of ja means the true answer to Q is yes
and a response of da means the true answer to Q is
no.

Proof: Both a double positive and a
double negative make a positive.


Lemma 2: If we have determined that a particular
God is not Mr. Random and have two questions
remaining, we can determine the identities of all the
Gods.

Proof: Without loss of generality, assume that A is
not Mr. Random. Ask A the following two questions:

(1) E("Is A Mr. True?"),
(2) E("Is B Mr. Random?").

By Lemma 1, A's response to (1) will determine A's
identity and then A's response to (2) will determine
the identity of both B and C.


Using these Lemmas, we can make quick work
of the puzzle.

Ask B the question E("Is A Mr. Random?"). If B says ja,
then either B is Mr. Random or A is Mr. Random (by Lemma 1).
Hence C is not Mr. Random. If B says da, then either B is
Mr. Random or A is not Mr. Random (by Lemma 1).
Hence A is not Mr. Random. Whence B's response to our
first question determines that a particular God is not
Mr. Random. Now Lemma 2 finishes the job.

No comments: