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

Coming to Agreement, a logic puzzle for Oxford admissions interviews

jdh.hamkins.org

Post reply on HN
Print view View original

41–50 of 99 posts

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#41

Post by goldcd »

nkmnz wrote: post #20
goldcd wrote: post #18

Earlier quoted context omitted.

Well in that case, you just don't answer. Your buddy on the other side also wouldn't be expecting you to, so they'll just leave the game running indefinitely as well.

Exactly. Asymmetric payoffs lead to strange behavior.

But I'd then be asking for a clarification of "life and death"

Given a problem that's "Life and Death" - my take is that being unable to solve the problem is likely to 'be death'

chips all in, presume an external signal (google or a GPS clock), and I'm shouting "Blue"

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#42

Post by AQuantized »

mritun wrote: post #39
brandonmenc wrote: post #32

Is this supposed to be difficult? Without reading ahead... First message (main puzzle type): "Let's send each other 'red' or 'blue' at random. The first time we send the same color, our next move is to end the game and announce that color. Send 'yes' as your next message if you agree to this strategy."

The problem is there is no “us” here. The other contestant does not know the strategy in advance. This problem is a variation of the distributed consensus problem in computer science. The canonical solutions (Paxos, Raft, et al) are non-trivial and there are unsolved corner cases. In short - this is problem where they are looking at your approach to problem solving rather than the solution itself.

You just told the other contestant the strategy, making it an us. He has no need to know in advance since you just informed him.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#43

Post by eaglelamp »

For the first scenario send the message: If two primary colors end and state the color that results from mixing, .

If the other participant sends a primary color in the first round you can end immediately. Given that your partner understands primary colors and mixing you will be done after one round.

The benefit of this solution is that no matter what your partner sends over to you they have the instructions needed to know what you will do on your side, which addresses the coordination challenge.

I think this solution works for some of the other scenarios as well, but I didn't read them all.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#44

Post by brandonmenc »

aaaaaaaaaaab wrote: post #36
brandonmenc wrote: post #32

Is this supposed to be difficult? Without reading ahead... First message (main puzzle type): "Let's send each other 'red' or 'blue' at random. The first time we send the same color, our next move is to end the game and announce that color. Send 'yes' as your next message if you agree to this strategy."

And what would you do if you then received the following message? "Let's send each other 'purple' or 'green' at random. The first time we send the same color, our next move is to end the game and announce that color. Send 'yes' as your next message if you agree to this strategy."

Instead of sending "yes" you can send a message outlining a similar strategy (sending colors at random) to agree on one of the two sets of colors.

The ability to send arbitrary messages and a logical human on the other end seem to make this trivial, but maybe I'm missing something.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#45

Post by aaaaaaaaaaab »

AQuantized wrote: post #42
mritun wrote: post #39

Earlier quoted context omitted.

The problem is there is no “us” here. The other contestant does not know the strategy in advance. This problem is a variation of the distributed consensus problem in computer science. The canonical solutions (Paxos, Raft, et al) are non-trivial and there are unsolved corner cases. In short - this is problem where they are looking at your approach to problem solving rather than the solution itself.

You just told the other contestant the strategy, making it an us. He has no need to know in advance since you just informed him.

>He has no need to know in advance since you just informed him.

But the other party could have informed you their strategy too. So you tell them "Let's use strategy X", and the same step you receive "Let's use strategy Y" from them. Looks like the first meta-task is to agree on a strategy :^)

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#46

Post by bakuninsbart »

I thought it was interesting that the article talks about "breaking the symmetry" in a fundamentally different way than I thought about it. Since the amount of iterations is inconsequential, my first thought was to propose in the first iteration to play a round of stone, paper, scissors to decide who chooses a color, then continue with one of these until it is reciprocated successfully. A slightly more polite way of breaking the symmetry would be to suggest writing something along the lines of: "How about only one of us writes a message and the other [blank]? (I will write [blank] next round)".

Both of these approaches of course still have the weakness of requiring consensus to break the symmetry of the requests, so I'm not sure if they are adequate ideas at all.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#47

Post by brandonmenc »

aaaaaaaaaaab wrote: post #45
AQuantized wrote: post #42

Earlier quoted context omitted.

You just told the other contestant the strategy, making it an us. He has no need to know in advance since you just informed him.

>He has no need to know in advance since you just informed him. But the other party could have informed you their strategy too. So you tell them "Let's use strategy X", and the same step you receive "Let's use strategy Y" from them. Looks like the first meta-task is to agree on a strategy :^)

An intermediate step could be to send the two strategies back and forth at random until you both agree on the same one.

The arbitrary message "constraint" seems to be an escape hatch.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#48

Post by t_serpico »

aaaaaaaaaaab wrote: post #36
brandonmenc wrote: post #32

Is this supposed to be difficult? Without reading ahead... First message (main puzzle type): "Let's send each other 'red' or 'blue' at random. The first time we send the same color, our next move is to end the game and announce that color. Send 'yes' as your next message if you agree to this strategy."

And what would you do if you then received the following message? "Let's send each other 'purple' or 'green' at random. The first time we send the same color, our next move is to end the game and announce that color. Send 'yes' as your next message if you agree to this strategy."

To avoid waiting for consensus, how about we decide to each send a random color and in the next turn announce the color that is first alphanumerically? We each know our own color and the color our partner sent.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#49

Post by jedberg »

This is basic consensus protocols, so it requires one person to "write" while the other does not. Each variation requires each person to randomly select if they will be the writer and then confirm that with the other person. Here are my solutions without reading theirs first (Edit: I finished reading and it looks like we pretty much agree):

Main puzzle: "On each following turn, we will flip a coin and randomly choose to send a message either with a color or 'null'. If either person receives a color message when they did not send one themselves, then we both announce that color on the next turn. Confirm you agree with the strategy on your next turn, as well as sending a color or null".

Alternation variation: This one is actually easier, if I know I'm player one. I simply send a message that says "I am player one, announce the color red on turn three, and confirm you will comply on round 2". Then when they confirm, send a third message that says "announce the color red".

Collision variation: Send the same message as in the main puzzle, but flip a coin first to determine if you send a message at all.

Pigeon variation: There isn't enough information. Will I know when it is my turn again, or is that part of the lost information? Either way, I will start each message with "This is my message for turn 1, please number your reply as 'message 2'" and then use the same message as the alternation variation, repeating my message until I get their message 2 reply, and then I will send message three saying "announce the color red" and will do the same. Presumably there would be an arbiter to collect our round three announcements.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#50

Post by oli5679 »

Would this work?

Toss a coin

- If heads, say: "I am waiting to see what you say and if you suggested a strategy compatible with a colour to coordiate on, I will follow this coordination, otherwise I will toss a coin and next term will do [[insert entire strategy from 'Toss a coin']]"

- If tails, say: "lets coordinate on red next turn, unless you have suggested something that is not compatible with this red, in which case next turn I will do [[insert entire strategy from 'Toss a coin']]"

Post reply on HN