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

51–60 of 99 posts

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

#51

Post by aaaaaaaaaaab »

brandonmenc wrote: post #44
aaaaaaaaaaab wrote: post #36

Earlier quoted context omitted.

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.

The other party can do the same, but describing a slightly different strategy. How would you decide whose strategy to use?

In order to agree on a colour, you first must agree on a strategy.

In order to agree on a strategy, you first must agree on a strategy to choose the strategy.

In order to agree on a strategy to choose the strategy, you first must agree on a strategy to choose the strategy to choose the strategy.

...

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

#52

Post by GavinMcG »

t_serpico wrote: post #48
aaaaaaaaaaab wrote: post #36

Earlier quoted context omitted.

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.

How do you decide this? If you propose this, and they propose a different strategy, what do you expect happens on the next move?

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

#54

Post by brandonmenc »

aaaaaaaaaaab wrote: post #51
brandonmenc wrote: post #44

Earlier quoted context omitted.

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.

The other party can do the same, but describing a slightly different strategy. How would you decide whose strategy to use? In order to agree on a colour, you first must agree on a strategy. In order to agree on a strategy, you first must agree on a strategy to choose the strategy. In order to agree on a strategy to choose the strategy, you first must agree on a strategy to choose the strategy to choose the strategy.…

Someone can always break the loggerjam by sending the message "I am going to dictate the strategy. Send 'yes' if you agree to this."

Again, I think the "logical human on the other end" plus "arbitrary messages" along with the vanishing probability of constantly sending the same messages makes this easy in practice.

They're not asking to prove that it halts, but I get what you're saying.

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

#55

Post by aaaaaaaaaaab »

brandonmenc wrote: post #47
aaaaaaaaaaab wrote: post #45

Earlier quoted context omitted.

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

And how would you agree on this intermediate step? The other party could offer a similar but different variant of this intermediate step (e.g. use the strategy whose description comes first alphanumerically). You have no way to force the other party to use your random strategy for the intermediate step.

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

#56

Post by ttz »

am i finding some of the comments here over analyzing?

you can assume neither of you will end on the first round with a color.

message on round 1 = "if you send me a color, let us choose the most alphabetically earliest of your color and my color, which I am sending as red. if you did not send a color, i will not say anything, and logically, you will not either"

repeat each round if they continue to not send colors.

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

#57

Post by y7 »

Just looking at the main puzzle, I don't think the author's solution of randomness works. He suggests using a coin flip between two colors, say red and blue, but it suffers the same problem as the other solutions that he shoots down, namely that you have to get consensus on the pair {red, blue} first. If the other person suggests the pair {green, yellow} in the same round, you're out of luck. If you can get consensus on a pair of colors, then you can also get consensus on one color.

I think using randomness to decide whether you send a message or you stay silent does work. For example: toss a coin, and if it's heads, you send "If didn't send a message this round, I will send the host 'Red' on the next round." (you could add one round asking them to confirm on the next round, to make sure you speak the same language, etc.) If it's tails you stay silent.

If you stay silent during a round and your partner says something, you can use their strategy. Basically, you need a round where only one of you says something. If your partner is equally logical, and therefore has an equally efficient solution, this ends the game in an expected 1 + sum(k/2^k for k=1..inf) = 3 rounds.

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

#58

Post by goodgoodmike »

Here's the strategy with a one-in-a-million chance of failure. Choose a number between one and one million. On your chosen round, send the strategy instructions, "Pick red next round and end the game." If they send strategy instructions before your chosen round, comply. If they send a message of deference before your chosen round, follow up immediately with your strategy instructions. With infinite rounds, arbitrary random numbers are a way to break symmetry.

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

#59

Post by ximeng »

Trying to make this a little more rigorous:

You have two VMs, VM one has a program pre-loaded that takes an optional tuple (bool endGame, rgb agreed_color, string message) and emits a tuple in the same format. The message from the emitted tuple is used as input to a similar program on the second VM, the output message of which is passed as input to the first VM.

Both VMs also send their output to a judge which decides the next stage of the game as follows:

The game ends with a win if the output from both programs includes endGame set to true and agreed_color set to the same as the other program. If endGame is set to true by either program then the game is lost unless the win condition is true. Otherwise the game continues.

You need to write the program on the second VM without knowing the program on the first VM. However you can assume a "logical" program is loaded. If we assume this means you can send code through to execute on the other machine: eval(message), then we can simplify the problem to loading the same program on both VMs and executing it.

This is easy as is, program both machines to output (true, red, ""). So to make it interesting there needs to be some complications.

Effectively there is some hidden state on the first VM. Maybe this could be modeled as a random permutation of the color space on the first VM such that any reference to a color is first permuted before being output, including within messages.

This would mean the initial program above could now produce (true, blue, "") on the first VM. However, the programs are identical and don't know which VM they are running on.

Is this a good model for the problem? How could we improve it to add a solution?

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

#60

Post by MauranKilom »

eaglelamp wrote: post #43

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 t…

The problem with your suggestion is that your partner might send a different but equally "guaranteed success" strategy (e.g. "...opposite color of the mixing result"). Then how do you agree on which strategy to use?

Or, take the critique mentioned in the article: Is red + blue called violet or purple? Same problem: You would need to agree on one name, and this conflict is not solved by you sending what you would call it - your partner might do exactly the same but with a different name.

Post reply on HN