The Hardest Logic Puzzle Ever | Hacker News Reader

The Hardest Logic Puzzle Ever

qntm.org

55 pointszatkin35 comments

Open articleView on HN

Hardly the hardest. Here's a harder:

http://justinpombrio.net/tell/prisoner-lightbulb.html

EDIT: Also, for anyone stuck on the three gods puzzle, the three sisters puzzle is a good stepping stone:

http://mathpuzzlewiki.com/index.php?title=Three_princesses

Is there a link for a solution to your variant (of the prisoners and lightbulb problem)?

The original problem is on a website that also contains the answer (in a red, dash bordered box) [1].

[1] - http://www.cut-the-knot.org/Probability/LightBulbs.shtml

I know the original problem. I'm curious how he obtains a deterministic solution for the version where the warden can switch the light-bulb state at random (excerpt below).

“I reserve the right to flip the light on or off between interrogations up to 12 times in total.”

Maybe it's poorly worded?

You mean the Easy++ problem? The solution isn't very different from the solution to Easy (i.e. the original problem); it just takes longer to run.

For the Hard problem, you're on your own.

The wording is very careful :-)

>> “I reserve the right to flip the light on or off between interrogations up to 12 times in total.”

> The wording is very careful :-)

Do you mean he can flip the switch 12 times in total between all interrogations? Or that between every interrogation he can flip the switch up to 12 times.

That's what I mean by poorly worded.

The former, hence the phrase "in total", and the number 12 instead of 1.

> The former, hence the phrase "in total", and the number 12 instead of 1.

It wasn't very clear.

>> You mean the Easy++ problem? The solution isn't very different from the solution to Easy (i.e. the original problem); it just takes longer to run.

Btw what's the run-time on your easy++ solution? - I think the run-time on the solution to the regular problem with a single counter is around ~26 years, so all your prisoners will die before they can get released unless you're doing something more clever than the basic solution.

Also I'm not sure I understand the difference between your Easy and Hard problems? I assume the prisoner who is not interrogated with the other inmates just estimates the run-time for their solution and waits (which I think is part of the original problem anyway ? )

http://www.smbc-comics.com/?id=2886

Another interesting one in the style of the Singaporean puzzle that's been making the rounds recently: http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-ch... (knowledge of transfinite ordinals is useful)

Hints: http://pastebin.com/ypPA5Uab

Do the true/ false gods know how the random god would answer? I don't see how they could since only he know the randomness. But if they don't know, they would have no way to answer the question, "what would guy x say ja meant" where x happens to be the random one.

True and False give random responses if you ask them how random would answer, unless you include clauses like "would that god definitely say X"

This is a question of implementation, and answering it was part of the reason why I implemented this problem in the form of a computer program in the first place. In this implementation, the True and False gods simply pose the question to Random and take Random's answer - which is random. If you then ask the same question of Random again, of course you may not get the same answer.

You can make this question even harder by removing foreknowledge of the words! So you know the gods have words for yes and no, but don't know what those words are. Here's an article on the solution: http://www.technologyreview.com/view/428189/the-hardest-logi...

Isn't that the same as stated in the link?

The qntm link tells you the words are da and ja, which makes the problem easier. In the hardest version you have no idea what the words for yes and no are.

If you actually read the next sentence..

"in which the words for yes and no are da and ja, in some order. You do not know which word means which."

That's the original version. The harder version is discussed below. In the harder version, you don't know the words are "da" and "ja". They might be "potato" and "walrus" or something completely different.

I don't think this makes the problem any different, does it? If it were possible that there was a list of "yes" words and a list of "no" words that they could prick from randomly or something, then yes, that would be much more difficult.

But in both examples, there's one word for "yes" and one word for "no" and in both examples, the asker doesn't know which one is which.

There's a solution that works if you know the words are "da" and "ja", but doesn't work if you don't know what the words are: “If I asked you if B is random, would you say ja?”

It seems like asking about randomness is not a valid question. I'm not sure how you would implement that (beyond checking for the assignment of random behavior), you can't really find out until you observe a difference in behavior over a larger sampling.

If you're puzzled about the implementation, I invite you to inspect the JavaScript code! And if you disagree with my implementation, I'd be interested to know what you would do differently.

My statement was conceptual. Boolos himself suggests that we ask if X is random to get to a solution (though in a more complex iff statement). But being able to ask if a source is random seems unreasonable, though without that capability I can't say if there is a solution.

Be very careful what you ask the gods, you might run into:

http://en.wikipedia.org/wiki/Epimenides_paradox

You can ask multiple questions by compounding them into one. For example: "what is the outcome of 'is A true' converted to string and concatenated by the outcome of 'is B true'"?

You can only ask yes/no questions.

In that case, I'd try enumerating all possible questions to tackle this problem (breadth first on question size).

> each question must be put to exactly one god.

> It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).

Make up your mind.

Those statements are not contradictory. Each question goes to only one god, each god may receive more than one question, or none.

These rules do not conflict. The first one means that a single question cannot be addressed to multiple gods simultaneously, the second one states you can ask each of these single-addressed questions to any one god you chose.

I don't think there's any conflict between these. The first just means that you only get a response from a single god of your choosing for each of your three questions, as opposed to receiving a response from each god for each question. It doesn't mean that each god is asked exactly one question.

The first bit mean you can't direct a question to more than one god, not each god gets exactly one question.

Basically he's trying to say

"Each of the 3 questions must be unique and only asked to a single god, and each god can receive 0, 1, 2 or all 3 questions out of the 3 unique questions".

In other words, don't create 1 question and ask it to multiple gods. But if you create 2 or 3 different questions, it's fine to ask them to the same god (forgoing to opportunity to ask them to another god).

I don't know how I managed to misread that.

Thanks everyone for pointing out I was wrong.

Reply on news.ycombinator.com