3 ms·

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

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

deleted 5y ago
[deleted]
aaaaaaaaaaab 5y ago
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."
- brandonmenc 5y ago
  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.
  - aaaaaaaaaaab 5y ago
    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. ...
    - brandonmenc 5y ago
      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.
      - aaaaaaaaaaab 5y ago
        >Someone can always break the loggerjam by sending the message "I am going to dictate the strategy. Send 'yes' if you agree to this." Since the other party is just as logical as you, they can send you the same at the same time... By the way, if you think this is an acceptable solution, then there's no need for the whole random colour and strategy thing; just send "The color will be red. Send yes if you agree to this". If you think this is not an acceptable solution, then neither is yours.
- t_serpico 5y ago
  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.
  - GavinMcG 5y ago
    How do you decide this? If you propose this, and they propose a different strategy, what do you expect happens on the next move?
mritun 5y ago
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.
- AQuantized 5y ago
  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.
  - aaaaaaaaaaab 5y ago
    >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 :^)
    - brandonmenc 5y ago
      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.
      - aaaaaaaaaaab 5y ago
        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.
        kybernetikos 5y ago

deleted 5y ago

[deleted]

aaaaaaaaaaab 5y ago

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

brandonmenc 5y ago
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.
- aaaaaaaaaaab 5y ago
  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. ...
  - brandonmenc 5y ago
    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.
    - aaaaaaaaaaab 5y ago
      >Someone can always break the loggerjam by sending the message "I am going to dictate the strategy. Send 'yes' if you agree to this." Since the other party is just as logical as you, they can send you the same at the same time... By the way, if you think this is an acceptable solution, then there's no need for the whole random colour and strategy thing; just send "The color will be red. Send yes if you agree to this". If you think this is not an acceptable solution, then neither is yours.
t_serpico 5y ago
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.
- GavinMcG 5y ago
  How do you decide this? If you propose this, and they propose a different strategy, what do you expect happens on the next move?

mritun 5y ago

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.

AQuantized 5y ago
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.
- aaaaaaaaaaab 5y ago
  >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 :^)
  - brandonmenc 5y ago
    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.
    - aaaaaaaaaaab 5y ago
      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.
      - kybernetikos 5y ago