61–70 of 99 posts
Earlier quoted context omitted.
FTA: We had used these puzzles in our admissions interviews of candidates for a place at Oxford University in the degree courses Math/philosophy, CS/philosophy, and PPE at University College, Oxford I’m not familiar with the term “degree course”, but suspect the candidates were bright, but also around 18 years old.
I'm guessing "degree course" means "degree".
Earlier quoted context omitted.
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.
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.
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 decide…
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 decide…
I think this is an arbitrary "computerification" of the problem, and doesn't really make things clearer.
Maybe two VMs, identical program loaded on both, pick a leader through synced messages. You can't do this unless there is something different about the VMs. If one VM goes first it's easy (just use its suggested color), if there is a hardware RNG, easy (iterate until one VM rolls higher than the other, then use the last suggested color from that VM).
If the programs are different (as "maximally logical" is vague), then it comes down to some kind of analysis of the output of an arbitrary program, which is impossible in the general case. You then have to assume some kind of shared knowledge (red most likely, rgb averaging is most likely way to blend, known mots likely ordering of colors such as alphabetical) to make progress.
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…
What if they disagree with the strategy? How do you resolve the situation where their strategy is just as valid as yours?
> Will I know when it is my turn again, or is that part of the lost information?
The turns proceed as in the main variation, you just don't whether the message of each round arrives. As the article says - it's the general's problem, which is only solveable probabilistically.
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.
"if you send me a color, let us choose the most alphabetically latest of your color and my color, which I am sending as blue. if you did not send a color, i will not say anything, and logically, you will not either"
What do you do?
There's solving the problem - and there's solving the scenario. I'd presume that a logical contestant would google blue to be the most frequently chosen random colour, and the two of you would just scream "blue" at each other other and then you'd end the game.
Red Orange Yellow Green Blue Indigo Violet. Idea is to use an external object as the "witness" to arrive at consensus.
Violet
Indigo
Blue
Green
Yellow
Orange
Red. You lose.
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…
So there is guaranteed to be at most a pair of colors, and the goal is to eventually get agreement between those two options.