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:
Post a Comment