Borgs, Cylons, and Droids
This riddle (for the Hardest Variant) is one of the most challenging logic puzzles you'll find (not just on website, but anywhere, AFAIK). As with all the "Identify the Liar" riddles, this riddle has the same theme of identifying truth-tellers versus liars by posing question(s) to them and hearing their responses.There are two common toggles that can appear to make the task of identifying who is who even harder:
- The people who you must identify honest versus dishonest do not speak English.
- In addition to some people always being honest and other always dishonest, there is an additional possibility that some people will answer questions Randomly; so that responses from these people can be either honest or dishonest.
In terms of the second toggle, it turns out that including the Random option makes things quite difficult -- even harder than dealing with the presence of a dishonest person, as at least the dishonest person will answer questions consistently. Furthermore, nothing is known about how a person who answerly Randomly will answer, e.g. we don't know if they alternate between honest vs. dishonest, or if they flip a coin with %50 probability each time, or any other strategy for choosing when to answer honestly and when to answer dishonestly. Mathematically, this means that we assume that nothing is known about the distribution from which the Random person is choosing to answer each question.
Based on the two toggles above, there are four possible settings, based on whether or not the people speak English (or are "Alien"); and whether or not the option to answer Randomly is allowed. The hardest scenario is of course the (Alien, Random) combination, but you'll likely want to warm up with one of the easier variants first.
|
Choose difficulty level: |
English, No Random (Easiest) | Alien, No Random (Medium) | English, With Random (Medium) | Alien, With Random (Hardest) |
PHB_HARD_LONG_STORY
- You are the engineer on a starship which has strayed into a asteroid field. As you report to the bridge to communicate the damage sustained thus far, you find everyone there is unconscious (likely from a direct hit by a large asteroid just moments earlier).
- As ship engineer, you are unable to navigate safely out of the asteroid field; so you transmit an emergency distress call for any nearby ships that may be able to help.
- In response to your distress signal, you are relieved that a small ship with three alien creatures is in the vacinity and able to dock to your larger starship and come on board.
- As part of your intergallactic school training many years ago, you studied about all the alien creatures in the universe, and know enough to recognize the three alien creatures as one Borg, one Cylon, and one Droid. You also remember that these three types of creatures are unique in that:
- One type will always answer questions honestly
- One type will always answer questions dishonestly
- One type will answer questions randomly (sometimes honestly, sometimes dishonestly)
- You must assign the three aliens to three crucial stations:
- Captain: Who must coordinate between everyone else on the bridge, and be trusted to relay information and instructions honestly.
- Navigator: Who must be relied upon to respond to direction queries reliably.
- Pilot: Who never speaks, and is only required to perform the actions instructed of them.
- While the aliens are able to understand your language, they are unable to speak it -- indeed, they don't have the ability to speak at all. Instead, they communicate only through gestures. It's been a long time since you learned about their gestures -- you only remember the gestures for "Yes" and "No" (one involves tipping your head to the Right, and the other is tipping your head to the Left) -- but you cannot remember which gesture is which!
- You only have enough time to ask three questions to the aliens (which must be Yes/No questions, since this is the only thing you're even able to at least partially understand). From these questions, you must determine the associations of:
{Borg, Cylon, Droid} ↔ {Honest, Dishonest, Random}.
The Honest creature you will assign to be Captain, the Dishonest creature you will assign as Navigator (you'll know to reverse all of its responses to your questions), and the creature that responds Randomly will be assigned as Pilot. - The aliens know who each other are and are aware of each type's tendencies (Honest vs. Dishonest vs. Random) when answering questions.
- You may direct your three Yes/No questions to any alien(s) of your choosing. For example, you could direct all three questions to the same alien; or you could ask each alien one question; or anything in between.
- Your questions must be valid Yes/No questions; e.g. questions that do not have an absolutely correct response (e.g. questions that aren't about a factual statement or paradoxical questions) are not permitted.
- You need not choose all three questions (and to whom you will be asking them) ahead of time -- i.e. your next question can depend on the answer you received for your previous question.
- For your first question: What is the question and to which alien (Borg, Cylon, or Droid) you are directing it.
- For your second question: For each possible response you received for your first question, you need to specify what to do next -- namely, what is your 2nd question and to which alien (Borg, Cylon, or Droid) you are directing it.
- For your third question: For all possible responses you received for your first two questions, you need to specify what to do next -- namely, what is your 3rd question and to which alien (Borg, Cylon, or Droid) you are directing it.
{Borg, Cylon, Droid} ↔ {Honest, Dishonest, Random}.
- There are two sources of uncertainty: The association of head-tilt direction {Left, Right} ↔ {"Yes", "No"}, and the association of {Borg, Cylon, Droid} ↔ {Honest, Dishonest, Random}. A correct strategy will not be able to resolve both (and, in particular, the riddle only requires you to resolve the latter).
- You must use the fact that the alien types know each other's tendencies.
- Your question(s) can (and must) be understandable to the aliens, but not to you. Namely, at least some of your questions must refer to the aliens' language for Yes/No, e.g. "Is tipping your head Left the correct response to the question 'Does 2 plus 2 equal 5?'?"
- Some of your questions must involve hypothetical scenarios, e.g. "If you were X, then would you answer Y if I asked you Z?"
Succinct Answer: The following is one possible strategy:
- First Question: (Directed to the Borg) If I were to ask you if Cylons answer questions Randomly, would you respond by tipping your head Left?
- Second Question: The target of your question will depend on the answer to your first question:
- Case 1: Borg responded with Left head tip: (Directed to Droid) If I were to ask the alien type that always responds Honestly: "Is it true that Droids answer questions Randomly?", then would their response be to tip their head to the Left?
- Case 2: Borg responded with Right head tip: (Directed to Cylon) If I were to ask the alien type that always responds Honestly: "Is it true that Cylons answer questions Randomly?", then would their response be to tip their head to the Left?
- Third Question: (Directed to same alien type as second question) If I were to ask you if Borgs answer questions Randomly, would you respond by tipping your head to the Left?
(Left, Left, Left): Borg = Random, Cylon = Honest, Droid = Dishonest.
(Left, Left, Right): Borg = Honest, Cylon = Random, Droid = Dishonest.
(Left, Right, Left): Borg = Random, Cylon = Dishonest, Droid = Honest.
(Left, Right, Right): Borg = Dishonest, Cylon = Random, Droid = Honest.
(Right, Left, Left): Borg = Random, Cylon = Honest, Droid = Dishonest.
(Right, Left, Right): Borg = Honest, Cylon = Dishonest, Droid = Random.
(Right, Right, Left): Borg = Random, Cylon = Dishonest, Droid = Honest.
(Right, Right, Right): Borg = Dishonest, Cylon = Honest, Droid = Random.
Succinct Explanation: The first question allows you to rule out exactly one alien type from being the type that answers questions Randomly:
If Borg tips head Left: Then the Droids do not answer questions Randomly.
If Borg tips head Right: Then the Cylons do not answer questions Randomly.
Notice that the strategy then has you direct your 2nd question to the alien type that you know does not answer questions Randomly. Your 2nd question is worded in such a way that an Honest alien type would respond one way (with a head tip Right), and a Dishonest alien type would respond the other way (with a head tip Left). Thus, you know the exact association of the alien type to which you directed your 2nd question. In your final question, you need only distinguish between two possible cases for the remaining two alien types (e.g. determine which of the remaining two types answers questions Randomly). You direct your last question to the same alien type as your second question (since you now know exactly how they will answer), and this allows you to associate the final two alien types.
Longer Explanation: As with the Opposite Twins riddle, we first rule out the possibility of learning everything from your three questions. Namely, there are two sources of uncertainty:
- The association of head-tilt direction {Left, Right} ↔ {"Yes", "No"}
- The association of {Borg, Cylon, Droid} ↔ {Honest, Dishonest, Random}
For example, denoting: "B=Borg", "C=Cylon", "D=Droid", "H=Honest", "L=Dishonest (Liar)", and "R=Random"; the 12 possible universes could be enumerated e.g. as follows:
1L. {Left="Yes", (B, C, D) = (H, L, R)} 1R. {Right="Yes", (B, C, D) = (H, L, R)}
2L. {Left="Yes", (B, C, D) = (H, R, L)} 2R. {Right="Yes", (B, C, D) = (H, R, L)}
3L. {Left="Yes", (B, C, D) = (L, H, R)} 3R. {Right="Yes", (B, C, D) = (L, H, R)}
4L. {Left="Yes", (B, C, D) = (L, R, H)} 4R. {Right="Yes", (B, C, D) = (L, R, H)}
5L. {Left="Yes", (B, C, D) = (R, H, L)} 5R. {Right="Yes", (B, C, D) = (R, H, L)}
6L. {Left="Yes", (B, C, D) = (R, L, H)} 6R. {Right="Yes", (B, C, D) = (R, L, H)}
Meanwhile, the universe of possible responses only has 8 (=2^3) elements:
A. {Left, Left, Left} B. {Right, Right, Right}
C. {Left, Left, Right} D. {Right, Right, Left}
E. {Left, Right, Left} F. {Right, Left, Right}
G. {Left, Right, Right} H. {Right, Left, Left}
This means that information theoretically it is not possible to learn all of the unknown information. That is, even if we try to map the 8 possible responses A-H to all the possible universes {1L, 1R, 2L, ..., 12L, 12R}, there simply is not enough variations in the responses (8 total) to cover all possible universes (12 total). Thus, by a pure Counting Argument, this means that some of the 8 possible responses must map to more than one possible universe (For example, notice from the Succinct Answer that response type "A: (Left, Left, Left)" maps to universes 5L and 5R). In order to make the riddle even possible, the only way to do this is if, for the cases that a possible response (A-H) corresponds to more than one possible universe, it must be that the inability to distinguish between those two universes does not hinder your ability to associate: {Borg, Cylon, Droid} ↔ {Honest, Dishonest, Random}.
For example, notice that distinguishing Universe 1L versus Universe 1R is not required in terms of solving the riddle, since both of these universes have the same associations in terms of {Borg, Cylon, Droid} ↔ {Honest, Dishonest, Random}. Namely, while these two universes are different in terms of the associations of head-tilt direction {Left, Right} ↔ {"Yes", "No"}, they happen to agree on which alien type is Honest, which is the Liar, and which is Random.
Meanwhile, the same principle is true for Universes (2L,2R), (3L,3R), (4L,4R), (5L, 5R), and (6L,6R). Namely, whenever we must map multiple universes to the same response (A-H), it must be the case that there are at most two such universes that map to the same response, and these two must be grouped as stated (e.g., same numeric value, and with each possible "L=Yes" or "R=Yes").
So just based on the logic above, it might not be too hard to come up with questions that allow you to partition things so that each set of possible responses A-H nicely maps to 1 or 2 possible universes (where universes are grouped together by the "L" and "R" variants attached to a number, as above). Indeed, this is essentially is the problem you must solve in the "English, With Random" variant. However, to do this in the present setting (where you cannot distinguish "Yes" versus "No"), the solution requires not just coming up with the mappings, but also coming up with clever questions that allow you to identify the mappings. This requires some work, but ultimately it comes down to two main insights:
- Insight I: Your questions must involve hypothetical scenarios, e.g. "If you were X, then would you answer Y if I asked you Z?"
- Insight II: Your questions must refer to the aliens' language for Yes/No, e.g. "If I were to ask you Z, would you respond by tipping your head Left?"
Longest Explanation: The following describes my own thought processes when I solved this riddle.
We will use the notation from above, where we have labelled the 8 possible responses to your 3 questions as A-H, and we have labelled the 12 possible universes as 1-6 (where we combine the L vs. R variants of each universe). Therefore, from an information-theoretic perspective, any correct solution must distribute these six possible universes 1-6 amongst the 8 possible responses A-H. (Notice that this leaves two extra "bits" of information, i.e. a correct solution must have that any possible response has no more than one Universe assigned to it; but there could be (up to) two responses that both correspond to the same Universe - and indeed, the correct solution above has this redundancy, as responses A and H both map to universe 5; and responses D and E both map to universe 6).
My first attempt was to start by ignoring the actual questions I'd be asking (and to whom I'd ask them), and start by simply assigning the 6 possible Universes to the 8 possible responses. Knowing that I couldn't learn all 12 possible bits, my goal was to assign things so that sometimes (at most twice) I could discern the association {Left, Right} ↔ {Y, N}, but in the other (at least six) cases I couldn't discern the association {Left, Right} ↔ {Y, N}. For example, perhaps for responses A = (Left, Left, Left) and B = (Right, Right, Right), I might learn not only the association of {Borg, Cylon, Droid} ↔ {Honest, Dishonest, Random}, but also learn the association of {Left, Right} ↔ {"Yes", "No"}; but then in the other 6 cases, I would only learn the first association.
So thinking about just making the mappings of the 8 responses to the 6 universes, I decided to draw a table of possible mappings that would map each possible response to a universe, in such a way that:
- Each response A-H was mapped to at most onepossible universe.
- Every possible universe 1-6 was mapped to by (at least) one response.
When I first solved this riddle, I had not explicitly identified the two key insights, as mentioned at the end of the "Longer Explanation" section above. In particular, without the second key insight (using the Left/Right head-tipping in the question itself), I didn't realize that there were 8 possible responses. Indeed, if you don't use that second insight, you really only have 4 possible responses, whereby you can only distinguish responses based on whether e.g. the response to the second and third question is the Same or Different as the response to the first question. Namely, it doesn't really matter if the response to the first question is Left or Right, since I don't know what that would mean anyways. So without loss of generality, I assumed the response to the first question was Left, and then I looked at the four possible responses to the next two questions.
|
The entire discussion contained in this block (with the pink background) corresponds to the (erroneous) assumption that there are only 4 possible distinct responses. Namely, that because we cannot distinguish {Left, Right} ↔ {"Yes", "No"}, that it doesn't matter what the response is to the first question; the only distinguishing bits in the responses is whether or not the responses to the second and third questions match the response to the first question. That is, without loss of generality, the discussion in this entire block assumes that the first question is directed to the Borg, who answers "Left". While this analysis is based on a faulty assumption, because it lacks the Insight II from above, I leave it here because: (1) This is the story of how I came to the solution, and this is the accurate depiction of that process; and (2) This process did lead to insights that eventually led me to the solution. |
Response (Function Domain/Input) | Universe (Function Range/Output)
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, Y, Y) | 1
(Left, Left, Left) /
\_ [Left=N] (N, N, N) | 1
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, Y, N) | 2
(Left, Left, Right) /
\_ [Left=N] (N, N, Y) | 2
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, N, Y) | 3
(Left, Right, Left) /
\_ [Left=N] (N, Y, N) | 4
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, N, N) | 5
(Left, Right, Right)/
\_ [Left=N] (N, Y, Y) | 6
----------------------------------------------------------------------------------------------
In sketching things out this way, I quickly recognized that there was a problem: The bottom two responses required me to learn the association of {Left, Right} ↔ {Y, N}, in order to distinguish between Universes 3 vs. 4 (3rd row) and Universes 5 vs. 6 (4th row). For example, once I ask the first two questions, then if I'm in the case that I observe responses as: (Left, Right); then the last question needs to not only segment cases {3, 4} from {5, 6}, but it also needs to segment the cases of Left = Yes vs. Left = No.
Another way to view the above table is that for the bottom two rows, because the separation of e.g. Universe 3 from that of 4 requires knowledge of the association of {Left, Right} ↔ {Y, N}; a more complete way to label these rows would be that for row 3, the two outputs are actually Universe 3L and 4R; and similarly for row 4, the outputs are actually 5L and 6R. [Meanwhile, the first row has outputs 1L and 1R, and the second is 2L and 2R; but this is not relevant for now.] But this is a problem, as this means that the table does not cover all possible Universes.
So, while the above doesn't work, it was helpful for:
1) Realizing that this wouldn't work, and that I probably needed a solution where I never learn the Association: {Left, Right} ↔ {Y, N}. Or perhaps more accurately, I realized that of the 12 universes, they likely needed to be paired up as they are above, so that e.g. if I were to construct a table representing the answer, each row would have the 'L' and 'R' variants of each Universe index, e.g. one row would have {1L, 1R}, one row would have {2L, 2R}, and so on.
2) I needed to first consider a simpler problem: where the association of {Left, Right} ↔ {Y, N} was already known.
So my next step was to do (2), namely, simplifying the problem so that the association of {Left, Right} ↔ {Y, N} was already known. See the "Long Explanation" section of the "English, With Random" version of this problem for a discussion of my thought process there.
After having solved the "English, With Random" variant,
PHBPHB
ENGLISH:
I realized that no matter what the first question (or any question, but just focusing on the first for now) is, and no matter which alien type {Borg, Cylon, Droid} you direct the first question to, the following facts are true:
- You can find a question so that the Honest and Dishonest response is the same.
- You can find a question so that the Honest and Dishonest response is different.
- No matter the question, you have no ability to control the response from the Random alien type.
As a result, I determined that there are two options for the first question:
- Ask a question for which the Honest and Dishonest responses will match. In this case, there is a 50-50 chance that the Random alien type will also respond the same way; and if this were to happen, your first question would be completely wasted (i.e. wouldn't convery any information).
- Ask a question for which the Honest and Dishonest responses will differ. In this case, the Random response will sometimes match the Honest alien type, and sometimes match the Dishonest alien type.
Now, returning to coming up with mapping the 8 possible responses to the 6 Universes, I applied the above reasoning to see how the first question could possibly help to distinguish which Universe we are in. Namely, thinking about how a question of type (2) above could help distinguish worlds, I can restate things as follows:
- No matter the question or response, Universes 5 and 6 (which correspond to Borg responding Randomly will remain an option
- If I ask a question as per option (2) -- and if I can understand the response -- I will be able to distinguish Universes {1, 2} vs. {3, 4}; whereby the first two happen if the response is True (Honest), and the latter two happen if the response is False (Dishonest).
Borg's Truth Table for question "Is 1+1=2?" (Borg responds "Left")
Left = YES || Left = NO
-------------------------------
1, 2, 5, 6 || 3, 4, 5, 6
Notice that Universes { 5, 6 } appear in both columns, corresponding to the fact that those are the two Universes in which the Borg answers Randomly. Meanwhile, Universes { 1, 2 } are in one column (it doesn't matter which column), since those both correspond the case that the Borg alien type answers questions Honestly, and Universes { 3, 4 } are in the opposite column, since those both correspond to the case that the Borg alien type answers questions Dishonestly.
Now, suppose we employed a strategy of asking all three alien types this same question -- e.g. "Is 1+1=2?". The above table was for the 1st question (directed to the Borg). We can create similar tables based on the responses to the next two questions, with the second question directed to the Cylon and the third to the Droid:
Cylon's Truth Table for question "Is 1+1=2?"
YES || NO
-------------------------------
3, 5, 2, 4 || 1, 6, 2, 4
Droid's Truth Table for question "Is 1+1=2?"
YES || NO
-------------------------------
4, 6, 1, 3 || 2, 5, 1, 3
Notice that the Q2/Cylon truth table has Universes { 2, 4 } in both columns (since those are the Universes in which Cylons respond Randomly), and the Q3/Droid truth table has Universes { 1, 3 } in both columns (since those are the Universes in which Droids respond Randomly).
But now there's a problem. Namely, the above truth tables can be combined to form the Combined Truth Table:
Response (Function Domain/Input) | Universe (Function Range/Output)
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, Y, Y) | ⊥
(Left, Left, Left) /
\_ [Left=N] (N, N, N) | ⊥
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, Y, N) | 2,5
(Left, Left, Right) /
\_ [Left=N] (N, N, Y) | 4,6
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, N, Y) | 1,6
(Left, Right, Left) /
\_ [Left=N] (N, Y, N) | 3,5
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, N, N) | 1,2
(Left, Right, Right)/
\_ [Left=N] (N, Y, Y) | 3,4
----------------------------------------------------------------------------------------------
This Combined Truth Table is problematic in (at least) three ways:
a) The top row (Left, Left, Left) doesn't map to anything
b) The other three rows do not satisfy Property (1) of being "Well-Defined" (i.e. each row, and even each "sub-row" within each row, maps to more than one Universe)
c) Each row is split into two cases (Left=Yes vs. Left=No), and it isn't clear that we can ask questions such that we'll be able to know which case we're in.
Of these problems, the glaring problem is (b). In order to attack this problem, I next ignored the whole motivation/setup of the riddle, and simply tried to distribute the numbers 1-6 in such a way that each row of the Combined Truth Table would have (at most) one number assigned to it. The only constraint I insisted on keeping is that when directing a question to someone, the two Universes that correspond to that alien type being Random must appear on both sides of its truth table -- e.g. Universes {5, 6} must appear on both sides of the Borg's truth-table. However, for example focusing on the Borg's truth table, based on the question "Is 1+1=2?", then this naturally groups together Universes {1,2} (which correspond to Borg answering Honestly) and {3,4} (which correspond to Borg answering Dishonestly). What if I abandoned this restriction, and was able to come up with some question that could instead group things as, e.g., {1,3} vs. {2,4}? While it might seem counter-intuitive that such a separation is possible, since { 1, 3 } correspond to Universes where Borg responds Honestly in the former and Dishonestly in the latter, I nevertheless ignored this for the moment (and indeed, I realized that it might be possible to find questions that could produce any desired grouping/separation. For example, the question could be: "Is the correct Universe one of: {1, 4, or 5}?")
Before concerning myself on what questions could be to produce any possible grouping/separation (and indeed if it is even possible to produce such questions), I set about pretending I could find questions for any possible grouping I wanted (again, except for the constraint that {5,6} must be present on both sides of Borg's truth table); and seeing if I could produce a Combined Truth Table that didn't suffer from issue (b) above.
With this new possibility in mind, my goal was to redo the truth-tables for Borg, Cylon, and Droid, such that the Combined Truth Table did not exhibit the flaws (a) and (b) above (flaw (c), I figured I'd deal with later).
For example, the following would do it:
Hypothetical Borg Truth Table (Borg responds "Left")
Left = YES || Left = NO
-------------------------------
1, 2, 5, 6 || 3, 4, 5, 6
Hypothetical Cylon Truth Table
YES || NO
-------------------------------
1, 5, 2, 4 || 3, 6, 2, 4
Hypothetical Droid Truth Table
YES || NO
-------------------------------
2, 5, 1, 3 || 4, 6, 1, 3
Notice the above truth tables combine to form the Combined Truth Table:
Response (Function Domain/Input) | Universe (Function Range/Output)
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, Y, Y) | 1,2,5
(Left, Left, Left) /
\_ [Left=N] (N, N, N) | 3,4,6
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, Y, N) | 1
(Left, Left, Right) /
\_ [Left=N] (N, N, Y) | 3
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, N, Y) | 2
(Left, Right, Left) /
\_ [Left=N] (N, Y, N) | 4
----------------------------------------------------------------------------------------------
_ [Left=Y] (Y, N, N) | 6
(Left, Right, Right)/
\_ [Left=N] (N, Y, Y) | 5
----------------------------------------------------------------------------------------------
Now, the good thing about the above Combined Truth Table is that it does successfully partition the 6 Universes, BUT only if: (i) We can distinguish Left = YES vs. Left = NO; and (ii) We can somehow guarantee we don't get the (Left, Left, Left) case.
Thus, this solution almost works for the "English, With Random" Variant, except that we'd need to argue how we could guarantee that (Left, Left, Left) doesn't occur; and also we'd still need to produce questions { Q1, Q2, Q3 } that would create the 3 truth tables above.
Now, at this point I realized that I likely wouldn't be able to overcome flaw (c), as per the info-theoretic arguments described at the top.
There were two key ah-ha observations that I came to, which can be viewed as matching upper and lower bounds.
Namely, focusing on the first question that gets asked (WLOG I ask Borg the first question):
Observation 1: (Upper-Bound): The best possible outcome (that is guaranteed, i.e. the outcome that does the best even in the worst-case scenario) based on the Borg's response to the first question is that 2 of the 4 Universes in {1,2,3,4} can be ruled out.
Explanation: If Borg = Random (i.e. if Borgs answer questions Randomly), then its response can be anything. In particular, this means that of the six possible Universes 1-6, no matter what the question is and no matter what the response is, I won't be able to rule out Universes 5 or 6 (which correspond to Borg = Random). Thus, the best that can be hoped for from the response to Q1 is to rule out some Universes amongst {1, 2, 3, 4}. Namely, the goal for Q1 is to identify a question such that the response partitions/separates out Universes amongst {1, 2, 3, 4}, so that if the response is, say, 'Left', then the subset of possible universes is {5, 6, A}, and if the response is 'Right', then the subset of possible universes is {5, 6, B}, for some subsets A,B ⊆ {1,2,3,4}. Note that since A ∪ B must equal {1,2,3,4}, the best I can hope for is to have |A| = |B| = 2 (since |A| + |B| ≥ |A ∪ B| = |{1,2,3,4}| = 4, and thus either |A| = |B| = 2, or one of |A| or |B| is at least 3, in which case when I get the response that corresponds to the larger of A vs. B, then I will have ruled out at most one Universe).
Observation 2: (Lower-Bound) Of the four Universes 1-4 (for which Borg ≠ Random), there DOES exist a question such that no matter the response ("Left" or "Right"), I will always be able to separate/rule out two of these four universes, even without (ever) knowing the association {Left, Right} ↔ {Y, N}. Namely, there is a question such that the response allows me to separate/rule out Universes 1-4:
Case Response="Left": { 1, 2, 5, 6} ⇒ I know Borg ≠ Dishonest
Case Response="Right": { 3, 4, 5, 6} ⇒ I know Borg ≠ Honest
While the above two observations were probably somewhere in my mind from the outset of trying to solve this riddle, they were not stated as clearly/explicitly. I think that they were loosely there, and inspired me to search for the possibility of a question in the line of Observation 2, i.e. such that no matter what the response, I could eliminate (at least one/some) Universes. Since I knew that I needed a question such that the response "Left" would eliminate some Universes, and "Right" would eliminate others, and this separation must happen without knowing the association {Left, Right} ↔ {Y, N}, I think it then dawned on me that "Left" (or "Right") must be part of the question itself.
Once I had this a-ha moment, it didn't take long to come up with a question such that the Borg's response would be to tip its head Left if Borgs answer questions Honestly, but woulr respond by tipping its head Right if Borgs answer questions Dishonestly. Namely, the question I came up with was:
Original Question 1 (addressed to the Borg): "If I were to ask the Honest alien type: 'Do Borgs respond to questions Randomly?', would they respond by tipping their head to the Left?"
Notice that, ignoring Universes 5 and 6, the truth table for the Borg's response to "Original Question 1" is:
| Response | Universe | Explanation |
| Right | 1,2 |
For Universes {1, 2}, Borg = Honest. Therefore: Case 1: Left=YES: Then Q1 is: "Is 'YES' the truthful response to the question 'Do Borgs respond to questions Randomly?'?". Since we are in the case that Borg = Honest, the Honest response to the inner question 'Do Borgs respond to questions Randomly?' is "NO." And, again since we're considering universes in which Borg = Honest, the Borg will answer Q1 Honestly, which means the Borg's response to the question will be "NO", which (for this case) corresponds to tipping their head Right. Case 2: Left=NO: Then Q1 is: "Is 'NO' the truthful response to the question 'Do Borgs respond to questions Randomly?'?". Since we are in the case that Borg = Honest, the Honest response to the inner question 'Do Borgs respond to questions Randomly?' is "NO." Which means the truthful response to Q1 is "YES" (since an Honest alien type would answer "NO" to the question: 'Do Borgs respond to questions Randomly?'). Since we're considering universes in which Borg = Honest, the Borg will answer Q1 Honestly, which means the Borg's response to the question will be "YES", which (for this case) corresponds to tipping their head Right. |
| Left | 3,4 |
For Universes {3, 4}, Borg = Dishonest. Therefore: Case 1: Left=YES: Then Q1 is: "Is 'YES' the truthful response to the question 'Do Borgs respond to questions Randomly?'?". Since the truthful response to the inner question: 'Do Borgs respond to questions Randomly?' is 'NO' (since Borg ≠ Random), the truthful response to Q1 is 'NO'. However, since Borg = Dishonest (for Universes 2 and 4), its actual response to Q1 will be 'YES', which corresponds to Left (since we are in the case Left=YES). Case 2: Left=NO: It can be argued similarly that Borg will also respond by tipping their head Left. |
So the above was the main intuition for how, without assigning/learning the Association {Left, Right} ↔ {Y, N}, I could separate Universes {1,2} from {3,4}, and know exactly which world I am in based on the response. [Of course, Universe {5,6} would be possible regardless of the response.]
Thus, after asking "Original Question 1", I would be in one of the two cases:
Case 1: Borg's response is Left head tilt. Possible Universes: { 1, 2, 5, 6}. Namely, I know Borgs do not answer questions Dishonestly (but Random and Honest are both still options).
Case 2: Borg's response is Right head tilt. Possible Universes: { 3, 4, 5, 6}. Namely, I know Borgs do not answer questions Honestly (but Random and Dishonest are both still options).
The next step was to think about what Q2 would be (and who to ask it to). At first, I thought I would always ask Q2 to the Cylon. But this approach was problematic. For suppose I am in Case 1 (Borg's response is "Left"), so that the possible Universes are { 1, 2, 5, 6}. Then notice that these possible Universes correspond to Cylon being one of: { Dishonest, Random, Honest, Dishonest} (respectively). Notice, in particular, that no matter the second question (and subsequent response), Universe 2 will NOT be able to be eliminated (since Cylon=Random for Universe 2). Then just thinking about how any question's response can possible have Left vs. Right responses partition the Universes {1, 2, 5, 6}: it will always be the case that '2' will be a possibility no matter the response. And then of the other three Universes {1, 5, 6}: (by pigeonhole principle) either the response "Left" or "Right" must include (at least) 2 of these 3. This means that whichever response (Left or Right) contains two of those three, plus counting Universe 2 which will also always be possible, then after the 2nd question, in some cases I might only be able to eliminate 1 Universe, leaving 3 possible/candidate Universes and only one question left to ask. I soon realized that eliminating just one of four Universes in Q2 wasn't going to cut it; I really needed to eliminate 2 of the 4 possible Universes.
I think at this point I started to firm-up (make concrete) and strengthen Observation 1 from above, as follows:
I reasoned that in order to eliminate 2 Universes -- whether it be in Q1, Q2, or Q3 -- it must be the case that 4 of the possible/remaining Universes have the alien type being questioned being a type that responds either Honestly or Dishonestly (but not Randomly).
Indeed, this is why the "Original Question 1" above worked (in terms of elminating 2 possible Universes): At the time, all 6 Universes were possible, and Borgs answer questions Honestly in two of those and Dishonestly in two others.
Restating this obserstation formally as a restatement of Observation 1 from above:
Observation 1': In order to (be guaranteed to) eliminate two Universes based on the response to some question, it must be the case that, amongst the Universes that are still possible candidates, the alien being questioned is Honest in two of them and Dishonest in two of them.
Notice that as an immediate corollary of this:
Corrollary: If after Q1 there are only 4 possible Universes remaining, then in order to (be guaranteed to) eliminate 2 of these 4 Universes, there must be one of the players you can ask who definitely does not answer questions Randomly.
But this corollary makes the "Original Question 1" above problematic, since no matter which response the Borg gives (Left or Right) after Q1, there does not exist any alien (Borg, Cylon, Droid) that is guaranteed not to answer questions Randomly.
This then got me thinking: Since (WLOG) I'm asking Borg my first question, no matter what happens, Universes {5, 6} will never be able to be eliminated as options. Thus, I'm stuck with partitioning/eliminating amonst: {1, 2, 3, 4}. And, I now know, that it isn't good to partition as {1, 2} vs. {3, 4}, since this doesn't allow satisfaction of the Corollary. Must the partitioning be this way? I.e. the question I had come up with for Q1 had Honest responses (i.e. Universes {1, 2}) being Right and Dishonest responses (i.e. Universes {3, 4}) being Left. But is there an alternate question that partitions things differently? Or more generally, can Observation 2 be expanded to:
Observation 2': Of the four Universes 1-4 in which Borgs are NOT the alien type that responds to questions Randomly, there DOES exist a question that -- Even without (ever) knowing the association {Left, Right} ↔ {Y, N} -- will allow for the partitioning/separation of Universes 1-4 (based on Left vs. Right response) in any possible way.
Namely, it need not be the case (as was seen for the "Original Question 1" above) that Universes {1, 2} are together (e.g. for "Right" responses) while Universes {3, 4} are together for the other (e.g. for "Left" responses). Indeed, there exist questions that can partition any groupings I want, e.g. {1, 3} for "Right" and {2, 4} for "Left".
Before attempting to prove Observation 2' constructively -- that is, coming up with specific questions that could partition the four Universes {1, 2, 3, 4} in any possible groupings of two Universes for "Left" responses and the other two for "Right" responses -- I first tried to think if (even if it were true) Observation 2' would lead to a solution of the riddle? I quickly determined that Observation 2' would be good enough. Namely, if Observation 2' were true, then I could make my first question partition the four Universes 1-4 as:
Borg's response is Left: { 2, 4, 5, 6} ⇒ I know Droids do NOT answer questions Randomly
Borg's response is Right: { 1, 3, 5, 6} ⇒ I know Cylons do NOT answer questions Randomly
I next tried to think if I could come up with a question that partitioned things as per above. In my initial musings on this problem, when I was first trying to make things easier and assume that the association {Left, Right} ↔ {Y, N} was either known or could be determined later, I had already realized that there are two flavors of questions: some that partition/separate alien types based on being Honest vs. Dishonest, but also questions that would separation/partitioning based on relative orderings of the arrangements (Borg, Cylon, Droid) ↔ (Honest, Dishonest, Random).
In particular, when thinking about asking Q1 to Borg, the 4 Universes {1,2,3,4} are partitioned/grouped as {1,2} vs. {3,4} when you're asking a question whose response will depend on whether Borgs respond Honestly vs. Dishonestly. However, if you instead ask a question based on the arrangement of (Borg, Cylon, Droid) being a rotation of (H,D,R) = (Honest, Dishonest, Random), as opposed to the opposite case of being a rotation of (H, R, D) = (Honest, Random, Dishonest). For a question that partitions things as per the rotation cases, this would correspond to partitioning the four Universes {1,2,3,4} as {1,4} vs. {2,3}. Thus, since I had already played with the idea earlier of making Q1 something like "are you arranged in an order that is a rotation of (H,D,R)?". A natural thing to have tried then, in terms of combining the new revelation of including 'Left' in the question itself, would have been something like:
Alternate Question 1 (addressed to Borg): "If I were to ask you if the arrangement of (Borg, Cylon, Droid) is a rotation of (H,D,R), would you respond by tipping your head 'Left'"?
While this likely could partition as {1,4} vs. {2,3}, this still is not a good partition, since it does not allow me to identify an alien type that I know is NOT the type that responds to questions Randomly. Indeed, the only partitioning of {1,2,3,4} that WOULD guarantee that, no matter the response, there would exist an alien type that I KNOW does not answer questions Randomly, would be if I could come up with a question to the Borg that partitions Universes 1-4 as: {1,3} vs. {2,4}.
With the confidence that I could already partition {1,2,3,4} in several ways, e.g. as {1,2} vs. {3,4} or {1,4} vs. {2,3}, I was reasonably confident that the desired partitioning of {1,3} vs. {2,4} might also be possible. It didn't take long to arrive at:
Final Question 1 (addressed to Borg): "If I were to ask you if Cylons respond to questions Randomly, would you respond 'Left'"?
Notice that the truth table for this response is:
| Response | Universe | Explanation |
| Left | 2,4 |
For Universes {2, 4}, Cylons = Random. Toggling on whether we are in Universe 2 or 4 (as this row claims to cover both), and whether we are in a world in which Left = YES vs. Left = NO, we consider the four possible cases: Case 1: (Left=YES, Uni. 2): Since we are considering the case of Universe 2, Borgs answer questions Honestly. Also, the honest answer to the question 'Do Cylons respond to questions Randomly?' is YES = LEFT (again because we are assuming Universe 2, and that Left = YES). Therefore, since Borgs answer questions Honestly in this case, the Borg will respond to Q1 by by tipping its head Left. Case 2: (Left=YES, Uni. 4): Since we are considering the case of Universe 4, Borgs answer questions Dishonestly. Also, the honest answer to the question 'Do Cylons respond to questions Randomly?' is YES = LEFT (again because we are assuming Universe 4, and that Left = YES). Therefore, if you were to ask the Dishonest alien type the question 'Do Cylons respond to questions Randomly?', they would lie and say 'NO', which in this case corresponds to tipping their head to the Right. However, since that is the actual response the dishonest alien type would provide, the Borg (who is the Dishonest type for Universe 4) will lie about this being the response it would give, and thus it will respond to your Q1 with a head tip to the Left. Case 3: (Left=NO, Uni. 2): Since we are considering the case of Universe 2, Borgs answer questions Honestly. Also, the honest answer to the question 'Do Cylons respond to questions Randomly?' is YES = RIGHT (again because we are assuming Universe 2, and that Right = YES). Therefore, an honest response to the question "Would you tip your head Left (i.e. 'would you respond 'No') if I were to ask you if Cyclons respond to questions Randomly?" would be "No", which in this case corresponds to tipping your head Left. Since Borgs are honest in this case, it would indeed respond to Q1 by tipping its head Left. Case 4: (Left=NO, Uni. 4): Since we are considering the case of Universe 4, Borgs answer questions Dishonestly. Also, the honest answer to the question 'Do Cylons respond to questions Randomly?' is YES = RIGHT (again because we are assuming Universe 4, and that Left = NO). Therefore, if you were to ask the Dishonest alien type the question 'Do Cylons respond to questions Randomly?', they would lie and say 'NO', which in this case corresponds to tipping their head to the Left. However, since that is the actual response the dishonest alien type would provide, the Borg (who is the Dishonest type for Universe 4) will lie about this being the response it would give, and insist that a head tip to the Left would NOT be their respond to the question 'Do Cylons respond to questions Randomly?'. Thus, they will respond 'NO' to your actual Q1, which for this case corresponds to tipping their head Left. |
| Right | 1,3 | For Universes {1, 3}, Cylons are NOT Random. A similar case analysis as was done above, toggling on Universes 1 vs. 3 and Left is YES vs. NO, shows that in all four cases, the Borg's response will be a head tip to the Right. |
Thus, based on the response to "Final Question 1", I successfully partition {1,2,3,4} as {1,3} vs. {2,4}; namely:
Borg's response is Left: { 2, 4, 5, 6} ⇒ I know Droids do NOT answer questions Randomly
Borg's response is Right: { 1, 3, 5, 6} ⇒ I know Cylons do NOT answer questions Randomly
Thus, depending on whether the Borg responds to by "Final Question 1" with a head tip to the Left or to the Right -- and note that I know their response (even though I won't learn the association {Left, Right} ↔ {Y, N} -- I'll direct my next question to the Cylon or Droid (whichever I know will not respond Randomly). Then, my second question can match the "Original Question 1" from above -- namely, it partitions/distinguishes amongst the four possible universes by separating an Honest versus Dishonest based on responses that tip heads Left versus Right. This will in turn allow me to know for sure if the alien type to whom I am directing my second question is the Honest or Dishonest type. Concretely, the second question is:
Case "Q1=LEFT" (i.e. Borg's response to Q1 was Left). Final Question 2 (addressed to the Droid): "If I were to ask the Honest alien type: 'Do Droids respond to questions Randomly?', would they respond by tipping their head to the Left?"
Case "Q1=RIGHT" (i.e. Borg's response to Q1 was Right). Final Question 2 (addressed to the Cylon): "If I were to ask the Honest alien type: 'Do Cylons respond to questions Randomly?', would they respond by tipping their head to the Left?"
As was already shown in the analysis above -- whether I am in Case "Q1 = Left" or "Q1 = Right" -- the alien type I address my second question to will respond with a head tip to the Left if it is honest, and to the Right if it is dishonest. In particular, as was shown above, for the case "Q1 = Left", I know the only possible Universes are: {2, 4, 5, 6}. And as was argued above, Q2 directed to the Droid would have a responses that partition these four universes as:
Droid's response is Left: Droids respond to questions Honestly ⇒ Universes {4, 6}.
Namely, I had already ruled out Universes 1 and 3 from the response to Q1, and the Droid responding to Q2 with a head tip Left means I can further rule out Universes 2 and 5 (where Droids are Dishonest).
Droid's response is Right: Droids respond to questions Dishonestly ⇒ Universes {2, 5}.
Namely, I had already ruled out Universes 1 and 3 from the response to Q1, and the Droid responding to Q2 with a head tip Right means I can further rule out Universes 4 and 6 (where Droids are Honest).
(An identical argument applies to the case "Q1 = RIGHT", where I instead will learn the exact identity of the Cylon based on its resonse to Q2, and furthermore know that only two universes remain as possibilities.)
Then not only does "Final Question 2" allow me to eliminate two of the four remaining Universes, in particular it allows me to know the exact identity (Honest vs. Dishonest) of the alien type to which I directed my second question.
The third question I will direct to the same alien to which I directed the second question (and whose identity, Honest vs. Dishonest, I know exactly). There are lots of possible questions I could use that would allow me to make the final distinction between the two remaining possible universes. For example, Q3 could be:
Final Question 3 (addressed to same alien type as Q2): "If I were to ask you if Borgs answer questions Randomly, would you respond by tipping your head Left?"
Then, the following provides the truth-table for the response to "Final Question 3", toggling based on whether the alien type you address your question to is Honest vs. Dishonest (which, as argued above, you know which case you're in), and based on whether Borg is indeed Random or not:
Case: Asking Honest, Response is Left: Borg is Random.
Explanation:
If Left=YES, then Q3 is: "If I were to ask you if Borg=Random, would you respond 'Yes'?". Then since the (honest) alien type you're asking tips their head Left (YES), this means that indeed Borgs respond to questions Randomly.
If Left=NO, then Q3 is: "If I were to ask you if Borg=Random, would you respond 'No'?". Since the (honest) alien type answers 'No' to Q3 (since we're in the case that they respond Left and that Left = NO), this means that they would respond YES to the question if Borg=Random; which means that indeed Borgs respond to questions Randomly.
Case: Asking Honest, Response is Right: Borg is Dishonest.
Explanation:
If Left=YES, then Q3 is: "If I were to ask you if Borg=Random, would you respond 'Yes'?". Then since the (honest) alien type you're asking tips their head Right (NO), this means that Borgs are NOT Random, which leaves as the only possibility that Borgs respond to questions Dishonestly.
If Left=NO, then Q3 is: "If I were to ask you if Borg=Random, would you respond 'No'?". Since the (honest) alien type answers 'Yes' to Q3 (since we're in the case that they respond Right and that Left = NO), this means that they would respond NO to the question if Borg=Random; which means that Borgs are NOT Random, which leaves as the only possibility that Borgs respond to questions Dishonestly.
Case: Asking Dishonest, Response is Left: Borg is Random.
Explanation:
If Left=YES, then Q3 is: "If I were to ask you if Borg=Random, would you respond 'Yes'?". Then since the (dishonest) alien type you're asking tips their head Left (YES), this is a lie, which means they would actually respond 'NO' if asked if Borg=Random. But again, since you're asking a dishonest alien type this question, a response of 'NO' to the question 'Is Borg=Random' is a lie, which means that indeed Borgs respond to questions Randomly.
If Left=NO, then Q3 is: "If I were to ask you if Borg=Random, would you respond 'No'?". Since the (dishonest) alien type answers 'No' to Q3 (since we're in the case that they respond Left and that Left = NO), this means that the honest response to Q3 should've been YES, i.e. that this alien type knows that they would respond 'NO' to the question "Is Borg=Random?". But since this alien type is dishonest, we know that their hypothetical response of 'NO' to the question "Is Borg=Random?" would be a lie, so we can conclude that indeed Borgs respond to questions Randomly.
Case: Asking Dishonest, Response is Right: Borg is Honest.
Explanation:
If Left=YES, then Q3 is: "If I were to ask you if Borg=Random, would you respond 'Yes'?". Then since the (dishonest) alien type you're asking tips their head Right (NO), this means in reality the truthful response to your Q3 is 'YES', i.e. this (dishonest) alien type would indeed answer the question 'Is Borg=Random' with a YES response. But a YES response to the question 'Is Borg=Random' actually means NO, if you are speaking to the alien type that responds dishonestly (which we are, for this case). Thus, Borg is NOT Random, which leaves as the only possibility that Borgs respond to questions Honestly.
If Left=NO, then Q3 is: "If I were to ask you if Borg=Random, would you respond 'No'?". Since the (dishonest) alien type answers 'Yes' to Q3 (since we're in the case that they respond Right and that Left = NO), this means that the truthful answer to your Q3 would have been 'NO'. Which means this alien type knows they would NOT respond 'NO' if asked the question 'Is Borg=Random'; i.e. they would respond YES to the question 'Is Borg=Random'. This means (again, since this alien type is dishonest) that the truthful answer to the question 'Is Borg=Random' must be NO; which means that Borgs are NOT Random, which leaves as the only possibility that Borgs respond to questions Honestly.
In summary, we map out the assignments of all possible responses to the three final questions:
| Response to Q1 | Possible Universes | Response to Q2 | Possible Universes | Response to Q3 | Possible Universes |
| Left (⇒ Borg is Random) | 6 ⇒ (B,C,D) = (R,L,H) | ||||
| Left (⇒ Droid is Honest) | 4,6 | ----------------------------------------------- | ------------------------------ | ||
| Right (⇒ Borg is Dishonest) | 4 ⇒ (B,C,D) = (L,R,H) | ||||
| Left (⇒ Droid is not Random) | 2,4,5,6 | ----------------------------------------------- | ------------------------------ | ----------------------------------------------- | ------------------------------ |
| Left (⇒ Borg is Random) | 5 ⇒ (B,C,D) = (R,H,L) | ||||
| Right (⇒ Droid is Dishonest) | 2,5 | ----------------------------------------------- | ------------------------------ | ||
| Right (⇒ Borg is Honest) | 2 ⇒ (B,C,D) = (H,R,L) | ||||
| Left (⇒ Borg is Random) | 5 ⇒ (B,C,D) = (R,H,L) | ||||
| Left (⇒ Cylon is Honest) | 3,5 | ----------------------------------------------- | ------------------------------ | ||
| Right (⇒ Borg is Dishonest) | 3 ⇒ (B,C,D) = (L,H,R) | ||||
| Right (⇒ Cylon is not Random) | 1,3,5,6 | ----------------------------------------------- | ------------------------------ | ----------------------------------------------- | ------------------------------ |
| Left (⇒ Borg is Random) | 6 ⇒ (B,C,D) = (R,L,H) | ||||
| Right (⇒ Cylon is Dishonest) | 1,6 | ----------------------------------------------- | ------------------------------ | ||
| Right (⇒ Borg is Honest) | 1 ⇒ (B,C,D) = (H,L,R) |