Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

math.dartmouth.edu

Post reply on HN
Print view View original

11–20 of 220 posts

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#11

Post by oli5679 »

I'm have some trouble understanding the solution to the 3 natives puzzle. Is the objective to find the road guarded by the truth teller?

SPOILER BELOW

The solution suggests

Q1) --> A

Q1): Is B least likely to tell the truth out of B and C?

If yes ask Q2 --> B, If no, ask Q2 --> C

Q2): If I were to ask you does your road lead to the truth village, would you say yes?

If yes, you know where the truth village is. If no, you would know the person you are questioning in the liar, but both of the other two could be the truth teller or the random answerer?

For example, if A is the random answerer and randomly selects 'truth', or if A is the truth teller, they will both direct you to the liar for Q2.

Let me know where I've gone wrong.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#12

Post by StavrosK »

mkagenius wrote: post #4

Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.

I knew "the" solution was something DH-like, but my solution was:

Maria mails Jan one of her padlocks, and he mails her the ring back in a box that's locked by that padlock.

...I think others are overcomplicating this.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#13

Post by charlesdenault »

mkagenius wrote: post #4

Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.

Assuming cryptography exists in Kleptopia, couldn't he use a padlock with a combination and transmit this electronically?

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#15

Post by craigsmansion »

StavrosK wrote: post #12
mkagenius wrote: post #4

Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.

I knew "the" solution was something DH-like, but my solution was: Maria mails Jan one of her padlocks, and he mails her the ring back in a box that's locked by that padlock. ...I think others are overcomplicating this.

> Maria mails Jan one of her padlocks

I think the idea is that that padlock would get stolen unless it would be sent in a padlocked box.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#16

Post by StavrosK »

craigsmansion wrote: post #15
StavrosK wrote: post #12

Earlier quoted context omitted.

I knew "the" solution was something DH-like, but my solution was: Maria mails Jan one of her padlocks, and he mails her the ring back in a box that's locked by that padlock. ...I think others are overcomplicating this.

> Maria mails Jan one of her padlocks I think the idea is that that padlock would get stolen unless it would be sent in a padlocked box.

I don't know, why would someone steal a padlock unless it was attached to a box? Maybe so, though.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#17

Post by jfries »

SPOILER 1 Names in boxes

I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if chance has it that there are two cycles of length 50. Then it seems the chance would be very large that one of the 100 prisoners would en up in the "wrong" loop and thus not find their name?

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#18

Post by ikeboy »

Avshalom wrote: post #3
Ensorceled wrote: post #2

For #1, I didn't hear correctly because I didn't understand that the clearly insane and cruel warden would let the prisoners label the boxes before hand :-/

You don't actually need to label them you just need all the prisoners to be able to memorize which name is associated with which box, Alice's box is the first on the left, Bob's the second etc... Then when Zach. Z. Z. Vanderwall opens "his box" and finds the name Bob he follows procedure. You need a minimal perfect hash function but it's a thing that can be done, especially because prisoners in these sort of conundru…

>fantastic memories and mental math facility.

If you assume the axiom of choice and allow them to memorize arbitrary uncountable elements, you can get more interesting puzzles (and also go insane).

https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-ch...

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#19

Post by mkagenius »

StavrosK wrote: post #16
craigsmansion wrote: post #15

Earlier quoted context omitted.

> Maria mails Jan one of her padlocks I think the idea is that that padlock would get stolen unless it would be sent in a padlocked box.

I don't know, why would someone steal a padlock unless it was attached to a box? Maybe so, though.

If not steal, can definitely make a copy of the key :)

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#20

Post by agf »

oli5679 wrote: post #11

I'm have some trouble understanding the solution to the 3 natives puzzle. Is the objective to find the road guarded by the truth teller? SPOILER BELOW The solution suggests Q1) --> A Q1): Is B least likely to tell the truth out of B and C? If yes ask Q2 --> B, If no, ask Q2 --> C Q2): If I were to ask you does your road lead to the truth village, would you say yes? If yes, you know where the truth village is. If no,…

There are only two roads and one village, and the problem is to find out which of the roads lead to the village. Forget about "guarding" and the "truth village".

If you ignore the random answerer for a second, then you ask "if I were to ask you if this road leads to the village, what would you say?". Let's call this the original question. The answer will be trustable, because the truth teller will tell the truth, and the liar will lie about a lie, making the result the truth as well.

Now we introduce a new question, and a third answerer -- random. Since we know we can solve the problem with only the original question and original two natives, the goal of this question is just to eliminate the random answerer.

The solution given in the article uses this new question in two ways. One, by asking it of one native and not ever asking that native the original question, if the native we happen to ask is the random answerer, we know we won't ask the original question of that answerer, so what they answer doesn't matter -- either way, we'll end up with the liar or truth teller to ask the original question of.

So we only need to design the new question assuming the one we ask it of is not the random answerer. So now we're back to asking a "double question", resulting in a truth about a truth or a lie about a lie. You ask the question you stated, knowing that the native identified as "least likely to tell the truth" will never be the random one, due to truth-about-truth, lie-about-lie, or due to the random answerer being neither B nor C.

Post reply on HN