18
$\begingroup$

There are 3 gods, named Past, Present and Future, who all look identical. They sit in a throne room, with one in the middle, the others on the right and left. You are allowed to ask them a series of yes/no questions in order to discern their identities. Present will answer truthfully, Past will truthfully answer the previous question you asked, and Future will truthfully answer the next question you plan to ask.

In order to avoid paradoxes (which would destroy the universe), you must follow these rules:

  • You must write down all the questions you plan to ask before entering the throne room, in the order you plan to ask them, and not deviate from this plan.
  • The only questions allowed are "Is the statement $P$ true?", where $P$ is a boolean function of statements like "The god at [position] is [name]" or "You are [name]". (Examples: "Are you Future?", "Is the God on the right Past?", "Is the middle God either Past or Present?" "Is one of you or the left god Future?").
  • Though what questions you ask must be preplanned, who you ask those questions to may be decided dynamically.
  • If your first question is directed at Past, she will answer yes/no randomly. Same when your last question is directed at Future.
  • The pronoun "you" refers to the person considering the question, not the person it was originally asked: if you ask Present, "Are you Past?," she will respond "No", and if your next question is directed at Past, she will respond "Yes."

What is the fewest number of questions you must ask to determine their identities, and how do you do this? (There is a solution, and it can proved optimal).

I got this puzzle from William Wu's puzzle website. You may also consider the "time is a flat circle" variant, where Past will answer your last question when your first question is directed at them, and Future will similarly wrap around to the first question you asked.

$\endgroup$
  • 4
    $\begingroup$ Wow, brilliant puzzle! $\endgroup$ – Rand al'Thor Mar 28 '15 at 22:26
  • $\begingroup$ Do the questions all have to be different from each other? $\endgroup$ – Rand al'Thor Mar 28 '15 at 23:05
  • $\begingroup$ The questions do not have to be all different. $\endgroup$ – Mike Earnest Mar 28 '15 at 23:24
5
$\begingroup$

Necessity of Changing the Addressee

To solve the riddle in three questions it is essential to remember that the rules allow to choose the addressee of the question (but not the question) depending on the outcome of the question. For if the order of questions is fixed then the problem cannot be solved in three questions. To show this, assume we're asking Left first and Right last (any other order is equivalent). Then ? denotes a random answer:

Left/Middle/Right   | L M R
--------------------+------
Past/Present/Future | ?   ?
Past/Future/Present | ?
Present/Past/Future |     ?
Present/Future/Past |
Future/Past/Present |
Future/Present/Past |

To distinguish the case Past/Present/Future from the other cases we would need an answer "Yes" in this one case and "No" in all other cases (or the reverse). If the answer is "No", we have only 2 questions remaining, which can only differentiate 4 cases, but 5 remain, making it impossible to solve in three questions if the question order is fixed.

Sufficiency of Changing the Addressee

So we need to ask questions in a manner that we will put the last question to Past or Present but not to Future. The second question needs to determine whether we put our first question to past: if we did then the answer to the first is useless and unneccessary, otherwise it serves to disambiugate the other cases:

Left/Middle/Right   | L M
--------------------+----
Past/Present/Future | ? Y
Past/Future/Present | ? Y
Present/Past/Future | Y N
Present/Future/Past | Y N
Future/Past/Present | N N
Future/Present/Past | N N

Then we need to choose the addressee of the third question such that it disambiugates between the remaining cases. (That this is the optimal solution is obvious, since with three boolean questions one can disambiugate at most 8 cases - in this case indeed only 6 because Past answers at random if asked first. With two questions one could disambiugate only four cases, which would be insufficient - though with head-exploding questions nine cases could be disambiugated...)

Partitioning Questions

That only helps to deal with 1. the possibility of hitting Past on the first question and 2. how to avoid hitting Future with the third question. However, they still might not answer the question they are supposed to answer: for Future, the next (2nd or 3rd) question must contain the question that must be answered on the previous (1st or 2nd) question; for Past, the previous (1st or 2nd) question must contain the question that must be answered for the next (2nd or 3rd) question:

        | 1 2 3
--------+------
Past    | - 1 2
Present | 1 2 3
Future  | 2 3 -

Hence the questions must be patterned as follows:

  1. ( are you Present and [question 1] ) OR ( are you Past and [question 2] )
  2. ( are you Present and [question 2] ) OR ( are you Future and [question 1] ) OR ( are you Past and [question 3] )
  3. ( are you Present and [question 3] ) OR ( are you Future and [question 2] )

Thus when e.g. Future is asked second, they will provide the answer to question 3, which will be exactly the answer that present would give of question 2.

The Questions

Now we know that a solution is possible, but still must determine which questions to ask. Due to the pattern rule above we can start by considering the present case only. Consider again the response table given above, then we want the following pattern:

Left/Middle/Right   | 1 2 3
Past/Present/Future | ? Y Y
Past/Future/Present | ? Y N
Present/Past/Future | Y N Y
Present/Future/Past | Y N N
Future/Past/Present | N N Y
Future/Present/Past | N N N

The first question, asked to L, can be "is L Present?" to give the desired pattern. The second question, asked to Middle, can be "Did I ask Past my first question?". Together these tell us whether L is Past, Present or Future. This has two consequences:

  1. we must avoid asking Future the last question. Thus if L is Future then we can ask either M or R (let's say M), but if L is not Future then we must ask L.
  2. the content of the last question must disambiugate between M and R. But the questions must be fixed beforehand, but L can be anything, and we don't want to ask for L again. So we could ask e.g. "Is M Past OR (Is L Past AND M Present)": if L is already Past then we ask for Present instead, otherwise we ask for Past; or we could ask if M is "earlier" than R. (The final questions would be of significantly simpler form if we could pick not only the addressee but also the question.)

The Solution

The following three questions shall be asked:

1. To Left: are you Present? [*]
2. To Middle:
( are you Present AND I asked Past my first question ) OR ( are you Future AND Left is Present ) OR ( are you Past AND ( (Left is Past AND Middle is Present) OR (Middle is Past) ) )?
3. To Middle if previous both answered with "No", to Left otherwise:
( you are Present AND ( (Left is Past AND Middle is Present) OR (Middle is Past) ) ) OR ( are you Future AND I asked Past my first question )?

[*] according to the pattern there should be OR ( are you Past AND I asked Past my first question ), but that drops away since that applies only if question 2 is addressed to Past, but then the first question can't have been addressed to Past.

$\endgroup$
  • $\begingroup$ Goodness gracious, well done! Brilliant analysis, especially recognizing the need for conditional questioning! $\endgroup$ – Mike Earnest Apr 11 '15 at 21:16
  • $\begingroup$ I wonder what strengthening of the conditions regarding the past's first question and the future's last question would be required to make the puzzle solvable with three questions if the sequence of who was asked needed to be fixed? For example, if one had overheard that the previous visiter's last question was answered "no", but didn't hear who or what was asked, and didn't have to answer until one overheard that the next question was answered "yes" [but again didn't hear who or what], and if questions could inquire of whom the questions were asked, would that suffice? $\endgroup$ – supercat Apr 30 '15 at 22:25
7
$\begingroup$

Because the answers can only be Yes/No (binary) and there are 6 possible seating arrangements, 3 questions are needed to differentiate the arrangements.

Here is my solution with "time in a circle"

Q1: asked to Left: Is the one on the Left seat Present and are you either Present or Future?

Q2: asked to Middle: Is the one on the Middle seat Present?

Q3: asked to Right: Is the one on the Middle seat Past?

Answers and seating arrangement from left to right:

No, No, No = Past, Future, Present

No, No, Yes = Future, Past, Present

No, Yes, No = Past, Present, Future

Yes, No, No = Present, Future, Past

Yes, No, Yes = Present Past, Future

Yes, Yes, Yes = Future, Present, Past

No, Yes,Yes and Yes, Yes, No are paradoxes.

Not Time in a Circle

In the case where time is not a circle, a fourth question is needed.

Q1: asked to Left: Is the one on the Left seat Present and are you either Present or Future?

Q2: asked to Middle: Is the one on the Middle seat Present?

Q3: asked to Right: Is the one on the Middle seat Past?

Q4: asked to Right: Is the one on the Left seat Present?

The answers and seating arrangements are:

? Y N ? = Past, Present, Future

? N N N = Past, Future, Present

Y N Y ? = Present, Past, Future

Y N N Y = Present, Future, Past

N N Y N = Future, Past, Present

Y Y Y N = Future, Present, Past

Q4 can be asked to Left instead, which moves the ? to the end of the last 2 arrangements. This might be clearer with Left giving all the ambiguous answers.

$\endgroup$
  • $\begingroup$ Man, verifying these solutions is exhausting... But this one is a winner! And is of course optimal! +1, but I'm going to wait on accepting, since the variant where time is not a circle is strictly harder, and still unsolved $\endgroup$ – Mike Earnest Mar 29 '15 at 1:13
  • $\begingroup$ As for the linear time solution, your method still works, but it can be done in 3 questions. $\endgroup$ – Mike Earnest Mar 29 '15 at 18:23
2
$\begingroup$

I'm not sure if the lowest number, or how to prove it optimal, but I can do it in

6

questions.

Answer:

Q1. ask anybody a universally true statement (i.e. is true=true?) just to set-up the problem Q2,Q3,Q4. Ask persons 1,2,3 alternating between false and true statements, starting with a false one
Whoever responded correctly to their question is the present god
Q5,Q6. Pick one of the remaining gods and ask him twice "are you future?"
if the first answer is 'Yes', then that is the future and the other is the past god, otherwise vice versa.

$\endgroup$
  • $\begingroup$ This isn't allowed! Check the 2nd bullet point in the OP for the class of questions you're allowed to ask. $\endgroup$ – Rand al'Thor Mar 28 '15 at 23:53
  • $\begingroup$ @randal'thor This is allowed; an example of a universally true statement would be (Left is Past) OR (Left if Present) OR (Left is Future), which is a boolean function of the basic allowed statements. $\endgroup$ – Mike Earnest Mar 29 '15 at 0:23
  • $\begingroup$ @MikeEarnest Oops, my mistake! Luckily I didn't DV. (I believe you don't have enough rep to see my now-deleted answer?) $\endgroup$ – Rand al'Thor Mar 29 '15 at 0:25
  • $\begingroup$ @SpencerKerr Looks right to me! However, it can be done with fewer, even when time is not a circle. $\endgroup$ – Mike Earnest Mar 29 '15 at 0:53
1
$\begingroup$

In the "time is a flat circle" variant, it can be done in 4 questions, although I do not know whether this is optimal.

The questions are:

Are you Present? (to left god)
Are you Present? (to middle god)
Are you Present? (to right god)
Are you or the god on the left Future? (to right god)

If you consider each arrangement of the gods, it can be seen that the resulting responses are unique:

Past Present Future | N Y Y N
Past Future Present | N N Y N
Present Past Future | Y N Y N
Present Future Past | Y N N N
Future Past Present | N N Y Y
Future Present Past | N Y N N
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.