Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
True, False, and Random (2015) (nautil.us)
40 points by tosh on May 1, 2021 | hide | past | favorite | 4 comments


This seems simpler to me:

First, an observation: For a given question X, if you ask a god

  G(X) = "Would you say 'da' if I asked you X?"
then, if the god is T or F, 'da' means X is true. (For an R, we can't say anything with certainty.)

Then, the remarkable thing is, if you pose Q1 = G("Is C the R?")@A, then 'da' (case 1d) means we could have TFR, FTR (if A is not R), or RTF, RFT (if A is R). Remarkably now, we know with certainty that B is not R! So, we can ask B something: Q2 = G("Is A the R?")@B. If 'da' (case 1d2d), then we have RTF or RFT, if 'ja' (case 1d2j), we have TFR or FTR.

Finally, note that DY = "Does 'da' mean yes?" yields 'da' from a T, but 'ja' from an F. So, in case 1d2d, ask Q3 = DY@C, and if 'da' (case 1d2d3d) we have RFT, if 'ja' (case 1d2d3j) we have RTF, while in case 1d2j, ask Q3 = DY@A, and if 'da' (case 1d2j3d), we have TFR, while 'ja' (case 1d2j3j) gives FTR.

Case 1j goes parallel, I think.

Some notes:

We have 12 possible scenarios (6 = 3x2x1 permutations of TFR, and 2 possible assignments of "da" and "ja" to yes and no), but only 8 (2^3 = 3 draws from {da, ja}) possible outcomes of the questions. That means that we cannot deduce both 1. who is who and 2. whether da means yes or no simultaneously! (And we don't figure out 2., with the above technique.)

Also, I am not sure whether this puzzle is solvable by asking a question to god A, B, and C in succession. (My technique above might involve skipping C (if he's the R) and asking either A or B two questions); and the solution in the article also.)


I think it's easiest to make a table of the responses you want first, and then look for the questions that get those responses. The result of the first question (WLOG assume it is to A):

  ABC
  ===
  TFR  da
  FTR  da
  TRF  ja
  FRT  ja
  RTF  __
  RFT  __
Like you said, if we get da we know B is not R, and likewise ja means C is not R. So we can ensure our next questions do not have any random (__) responses. Then you can easily find a pattern that identifies every god

  ABC
  ===
  TFR  da  da  da
  FTR  da  ja  ja
  TRF  ja  da  da
  FRT  ja  ja  ja
  RTF  __  da  ja
  RFT  __  ja  da
You can now mechanically come up with appropriate questions that produce each column.

> whether this puzzle is solvable by asking a question to god A, B, and C in succession

It's not. The 8 responses have to be mapped onto the 6 permutations of ABC. If A, B, C are asked in succession, one question will always be to R, and which permutation we map to cannot depend on the answer to that question. For example, if ja ja ja maps to TFR, ja ja da must too. That means for each of the 6 permutations, at least 2 responses must map to it. But that would require 12 possible responses.

By the same argument, only the first question can be to R. That means the solution is basically unique: use the first question to make sure the next questions are not to R.


> > whether this puzzle is solvable by asking a question to god A, B, and C in succession

> It's not.

That makes sense, thanks, yes.


This article desperately needs diagrams




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: