The Hardest Logic Puzzle: A step-by-step guide to true, false, and random
nautil.us
nautil.us
In high school, ages ago, I remember discussing the following problem and never being satisfied with the solution. If someone could clarify the exact wording and source of the problem I'd appreciate it.
What I loosely remember is as follows. A teacher tells her students on a Friday that they are to have a test next week. However, she adds, they won't know the day before that they're going to have a test on the following day.
The students, being somewhat savvy, deduce that if it transpires that they don't get tested by the end of the following Thursday then they'd have to be tested on Friday, which would mean that they know this beforehand, so the test cannot possibly be on Friday. And so, inductively, cannot be on Thursday, and so on.
This "logic" is very unsatisfying, so I need to find out what the actual form and solution of the problem is.
This has bugged me for decades.
It reminded me of a great article I read years ago that dealt with the issue of self-referential paradox. In fact, at the time I tried applying the techniques therein towards the surprise examination, however I didn't get anywhere.
It's a paper by Noson Yanofsky entitled "A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points" (http://arxiv.org/abs/math/0305282)
I think you'll enjoy reading it. I read the paper on a long train ride loved working out how given "Ann believes that Bob believes that Ann believes that Bob has a false belief about Ann" asking "does Ann believe that Bob has a false belief about Ann?" results in a paradox. This is supposedly called Brandenburger’s Epistemic Paradox.
Anyway, thanks again for your reference.
Thanks again!
EDIT: Just started reading. Mind already blown by the clarity of the "limitation, not paradox" idea. Slowing down for a longer, deeper, read.
http://math.stackexchange.com/questions/6860/the-hangmans-no...
In effect if you just tell someone "you will have a surprise test next week", that is contradictory, since they can reasonably expect to have a test at any moment during the following week and the test can therefore never be surprising, just the absence of the test.
It's certainly still a tricky puzzle but you would need to understand the rules on what kinds of questions you are allowed to ask before starting
In binary terms, let's say you have one bit, 0 or 1 that represents a single propositional statement, "x or y" or "x and y" but with compound questions you can get as many bits as you want "(x or y) and (x and y) and (p and q)" so you can only ever get the truth value of the entire compound statement but you get far more than a single truth value
I had formulated my yes/no questions when I worked through this as "Is exactly one of these true: Ja means yes, X" Which makes Da yes and Ja no.
>"Are you a knight if and only if Pluto is a dwarf planet?"
>If the person’s a knight and Pluto is a dwarf planet, then you get the answer “yes,” since both statements on each side of if and only if are true, and knights always speak truly.
I don't get how this follows. Surely, the person being a knight or a knave is independent from whether or not Pluto is a dwarf planet so a real knight would say "no" either way since the assumption is bad and a knave would thus say "yes". Thereby, you have not determined whether or not Pluto is a dwarf planet but instead whether the person is a knight or a knave.
Please explain my error.
Very often logic formulas, when translated in English, sound absolutely bonkers, not least because the words if, and, or have pretty loose meanings in ordinary language.
I think "Is one and only one of [A, B] true?" would be better. Or, (A ^ B).
> “Does ‘da’ mean ‘yes’ if and only if you are True and if and only if B is Random?”
Note, in particular, that at the end of the three questions in the solution you still have no way of discerning whether 'da' does, in fact, mean 'yes'.
My primary point is that there is a difference between asking both the question "A" and the question "B" vs. asking the question "A and B". It is true that I can waste two questions asking both "A" and "B" to obtain the answer to "A and B" so in that sense I can see why one might feel "A and B" is two questions rather than one.
But really, the answer to "A and B" isn't really about the answers to "A" and "B" as much as it is about the relationship between them. If you ask "A and B", an answer of "yes" will tell you they are both true but an answer of "no" will not distinguish between whether A is false or B is false or both.
Alternatively, consider questions "A" and "B" again. A is either true or false. B is also either true or false. You don't know the truth value of either. How many questions does it take to determine the truth value of both questions, assuming A and B are independent and the value of one doesn't influence the value of the other? Well, you could ask "A and B" and if you get "yes" you're done but that rides on you being lucky. In fact, there is no way that you can differentiate all four possibilities with a single yes/no response; you need at least two. This isn't really a proof that "A and B" is a single question, of course, but intuitively if "A and B" were, as you say, "really two different questions" one would expect to be able to construct an "A and B" that does differentiate four different possibilities.
Or, from another angle, per your prior post would you say "are you and the god to your left both not Random?" is actually two different questions? How about (ignoring for the moment that this is an entirely useless question in this puzzle) "are you not Random and the god to your left not Random and the god to your right not Random?" Or "Are none of the three of you Random?" I can see no cause to say "Are none of the three of you Random?" (or, say, "does it rain here every day?") is any more than one question nor any way to differentiate this construct from the version using "and". I also see no reason why asking "are you not Random and is the god to your left not Random?" would be any more or fewer questions than "are you not Random and does 'da' mean 'yes'" or why that would be any different from an "if and only if".
Of course, there is the final, if somewhat less satisfying, point to make: the framing as a "question" is more for convenience and wider understanding but the common intention for puzzles like this (especially with Smullyan credited for the puzzle) is generally for you to choose a predicate and ask a god to evaluate it for you, with the god possibly running the output through a not gate before it gets to you.
>In fact, there is no way that you can differentiate all four possibilities with a single yes/no response; you need at least two.
This is why I would say that the question is actually two questions. Two separate truth values must first be produced, then combined with some operator to make a third (and possibly combined again) value, which is the answer given by the god.
If a god must parse your question down into individual propositions and then answer them in some order to resolve a larger statement, it might stop after the first proposition. I believe it's a valid interpretation of the rules anyway.