logical deduction - Past, Present and Future

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.

Answer

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.

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...)

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.

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 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.