This is an aside, but somewhat similar in spirit.

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.

And read this, too: http://www.ams.org/notices/201011/rtx101101454p.pdf

Wow Peter, thanks for that. I like their analysis.

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, downloaded. I have to read the paper I quoted a few more times before I grok it fully. Perhaps it will be clearer after reading the one you cite, which appears most intriguing.

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.

Thanks oh so very much! :)

There's some discussion here:

http://math.stackexchange.com/questions/6860/the-hangmans-no...

Hm... that is indeed a weird problem. If you don't get tested on Monday, that is a surprise, because you expect to get tested on Monday. Then if you don't get tested on Tuesday, that is surprising, because you've inductively determined that Wednesday through Friday are ineligible. The rest of the days follow the same logic.

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.

The trick resides in how you can ask questions like "if and only if" which in my opinion are really multiple questions masked as one. For example you can formulate iff as "(not q or p) and (not p or q)" where the "not" refers only to the term directly to its right. This is far from a simple assertion like "is it true that if the earth is round then I am a knight?" because you are also asking "is it true that if I am a knight then the earth is round" and thus get the chance to ask two questions in one.

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

Asking compound questions isn't the same as asking multiple questions because you can only ever get one bit of information out of each question.

Not exactly because you can combine as many questions as you like and get an answer about whether one of them or all of them is correct, furthermore if you can ask question in first order logic, like "for all x is y true?" as opposed to just "if x then y?" The wording would be come awkward very quickly but you can gain an almost unlimited amount of information from compound questions. I wouldn't be surprised if there were a solution to this problem involving only two questions or even one, though at the moment I don't have the time to work through it so don't take my word for it.

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

If you take an information theory point of view, then a single question could provide more than a single bit of information, but it never will on average (for some suitable meaning of "average"). If I'm speaking to 1 of 1024 possible people and I ask "Are this particular woman?" then 1 time out of 1024 I will learn 10 bits of information, but 1023 out of 1024 times I will learn approximately zero bits of information.

Sam Hughes implemented this puzzle in Javascript to demonstrate how the solution works, and why some other proposed ones don't: http://qntm.org/gods

Not impossible but makes it slightly harder to do IFF and "is exactly one of these true"

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.

>Suppose that you can’t remember whether Pluto is a dwarf planet, and you need to find out by asking someone nearby—but you don’t know whether that person is a knight or a knave. What’s the one yes-no question you can ask to figure out whether Pluto is a dwarf planet?

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

It's easier if you see it as logical operations, rather than language. A iff B has the same meaning as A == B, but with the added twist that !B negates the answer in the example (knaves always lie). So let's take A = Pluto is a dwarf planet; B = you're a knight, then "are you a knight if and only if Pluto is a dwarf planet" has the formula (B && (A == B)) || !(!B && (A == B)), which after a bit of simplifying you can see is the same as A == True || !(A == False), or A == True.

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.

"If and only if" sounds strange to me too. Like asking if he's a knight when Pluto is a dwarf planet. And on second reading it looks like an awkward way to say And...

I think "Is one and only one of [A, B] true?" would be better. Or, (A ^ B).

There is no assumption. There is just "A if-and-only-if B" where A and B are both true and therefore by definition the whole statement is true.

I heard that Norman Steenrod was pacing back and forth in Fine Hall thinking about this puzzle, until he solved it. This was before it was attributed to Boolos, according to my sources. The author might have been Mark Kac, or it might have been communicated to Steenrod through Mark Kac, I was told.

I thought you had to ask exactly one question to each god. This solution uses god B twice.

"Each question must be put to exactly one god" means you can't ask one question to all of them and get three answers. One question, one answer.

good catch. regardless of the result of the 2nd question you need to ask B another question.

The article presents a good technique for handling situations, but I can't help but feel the solution breaks a rule. You are supposed to only be able to ask a single question to each god, but a biconditional question is really two different questions. You can see this simply from the structure of the English question (as well as in the conversion to NAND logic):

> “Does ‘da’ mean ‘yes’ if and only if you are True and if and only if B is Random?”

While you can construct the answer to "Does 'da' mean 'yes' if and only if you are True?" from "Does 'da' mean 'yes' if you are True" and "Does 'da' mean 'yes' only if you are True", you cannot construct the answers to "Does 'da' mean 'yes' if you are True" and "Does 'da' mean 'yes' only if you are True" from "Does 'da' mean 'yes' if and only if you are True?" alone.

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

I'm not arguing that there is a solution that meets all of the constraints of the problem, just that this particular solution does not seem to meet the constraints described.

I'm sorry if I was unclear but I did understand that and was responding to that particular notion. I was attempting to demonstrate that the "and" does not imply the question is now two (or more) questions. Perhaps I can be clearer:

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.

You make fair points. Our disagreement seems to only be about the interpretation of the rules.

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

How would you feel about the more conversational, "If I asked you if B were Random, would you say da?"

It's definitely better and much more subtle. Whether or not it is technically two questions per the description of the problem...I'm not sure :)

The article mentions law of excluded middle which doesn't hold in constructive logic so I wonder what exactly happens in the constructive setting.

Well, the part where it directly mentions excluded middle is the part where it cites Boolos commenting on just that.

That's not what I mean. What is the analog of the hardest puzzle in the constructive setting.