Coming to Agreement, a logic puzzle for Oxford admissions interviews
jdh.hamkins.org
jdh.hamkins.org
What they're really after is whether you can keep thinking and not be intimidated into silence. Just about any subject that a professor understands can be taken to where a high school graduate is stumped. You can always add twists to just about anything interesting. They key is to realise they are testing whether you'll interact well, not whether you can figure out the answers.
I was quite fortunate, they kept asking me things that I knew and they weren't disappointed with where my limits were.
It does come off as a bit confrontational to the modern observer I'd say, and it does give the impression that tutorials are some sort of intellectual sparring match. They're not, clearly you'd be flattened by the professor if they were.
Interestingly, the less I need a particular job opportunity the more comfortable I have been with these probing conversations.
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.
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.
Then presumably their strategy would also involve a confirmation message, so I would randomly choose my second message to either be "I agree with your strategy" or "I disagree" and then re-propose my strategy. It's all about being random in your choices.
> The turns proceed as in the main variation, you just don't whether the message of each round arrives.
Right, but the strategy changes if I have a fixed counter telling me what turn it is, because then I can reliably say "Pick a color and turn number to announce it and repeat your message on every turn" and as long as the turn number is high enough then the probability of me getting the confirmation is high and we are certain to announce on the same turn.
But if the turn counter has to be kept independently, then we need more information, because first we need to send many messages to determine the baseline delivery success rate so we can have a high probability of being on the same turn number.
What if their choice of (meta-)strategy for agreeing on the strategy is different?
Unless you can prove that only a single winning strategy exists (which every perfect logician will arrive at), you can't really assume that they will cooperate with whatever strategy or (meta-)*strategy you communicate. Sure, most humans will be on the same page as you very quickly as you go up meta-levels, but if you rely on human nature you also quickly get fallibility (see the host of bad answers in this thread) and not "perfect logicians".
> But if the turn counter has to be kept independently, then we need more information
Every time you have the opportunity to send a message, a new round begins (for both participants). Can you explain how this needs "more information"?
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.
So there is guaranteed to be at most a pair of colors, and the goal is to eventually get agreement between those two options.
So long as at least one of you uses a coin flip to switch between the strategy they last suggested and the strategy you last suggested it will work.
What if the other person says "But I have got a coin in my pocket, and from now on, I intend each round to flip the coin, sending the green message on heads and the orange message on tails. If you do likewise, then we are very likely in a few rounds to hit upon the same message, and then we shall win on the next round by following through, announcing the agreed-upon color."
How do you choose the strategy? If both stick to theirs, then you have a deadlock
"340958123405982
In order to decide who the leader is:
Before every round, I'm going to flip a coin before I send the next message out. Heads I'll stick with my method of deciding who the leader is for the round. Tails, I'll switch to your method of deciding on the leader for the round.
If I get heads, in the next round, I will send you this same message but starting with a different random integer from one to any size. If we both send each other this same exact message but starting with a different integer, in the same round, then whoever sends the largest integer, gets to be the leader and we will follow their plan."
------------------------
Next round and every round after:
If heads, I'll send out the same message but starting with a different random integer.
If tails, I'll follow their method of selecting a leader.
------------------------
If it ever reaches a point where we both send each other the exact same message except for the integer, and my integer was the largest one, my next message would be (or if their method ends up with me being the leader):
"I am the leader. We will both announce red in the next round"
------------------------
If it ever reaches a point where we both send each other the exact same message except for the integer, and my integer was the smaller one, my next message would be (or if their method ends up with them being the leader):
"You are the leader. I will follow the plan you sent me in this round."
------------------------
If we send each other the exact same message and the integers are tied, in the next round I flip a coin and if heads, send out the same long message again.
You are walking down one side of a hallway. It is only wide enough for two people to pass side by side.
Due to shoddy logic puzzle-appropriate workmanship, the hallway lights only work when nobody in the hallway is moving, and otherwise it is complete darkness.
A person is coming in the opposite direction, on the same side as you.
As a logician you are far too shy to be able to speak to this other person directly.
How do you avoid colliding with them?
Assuming they are logical as well, both of you know you can't keep walking forward in the dark without risking bumping. If you change sides, they could as well. So you both stop waking and the lights turn on.
Because you both know time isn't discrete, if the lights go out and you weren't moving, then it was your partner that was moving. The person who initiates the darkness gets to move. Wait a random amount of time and if the lights didn't go out, swap sides of the hallway.
Once the swap is done (by the one who moved first) and you both see you are no longer going to collide, both resume waking forward.
https://www.asc.ox.ac.uk/sites/default/files/migrated-files/...
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."
"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."
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.
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.
...
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.
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.
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 :^)
The arbitrary message "constraint" seems to be an escape hatch.
But I think you could just use the same approach: "Every turn, keep suggesting a strategy until you receive the same strategy you suggest". Once that happens, then you both execute that strategy.
Both players are trying to collaborate here, so they'll naturally subordinate themselves on the first opportunity to win the game, they'll implement randomness or backoff naturally.
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.
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.
Ultimately the problem is constructed to prompt a discussion so any reasonable "solution" would do, or if the stakes were life and death maybe the rational solution is to play forever as suggested by other commenters.
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?
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.
The only acceptable solution for perfectly rational players in the case of „death“ as possible down side while only having „live“ as a potential upside would be to extend the game indefinitely by telling the co-player that you will never agree on a different strategy than infinite play - all possible rewards, zero downside risk!
Where can I get my ticket to Oxford?
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"
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.
My solution is to say something like: ‘I will nominate a colour next round. If we both nominate the same colour, I will say that colour and end the game next round. If anything else, I will nominate a different colour, proceeding alphabetically.’
Of course, it would depend on what message you receive that round - there’s probably no one size fits all approach, such as the issues of both people using an unyielding strategy. So maybe you’d have a clause which says, if the other player gives an ultimatum message, then you will go along with that.
I don’t think there’s a perfect solution here, but I could be wrong.
Job done.
These scenarios in TFA seem to imply that both players want to be the "leader" as it were (all this talk of breaking symmetry etc) and that this is so somehow some sort of interminable problem. The problem does not seem to state any "cost" of waiting a turn, so there is no rush it seems, and there seems to be no cost of being the "leader" or "follower".
This is a basic master-election issue more than anything. Solved problem ... see paxos et al (although I concede that this is more of a "how you think" question, and less about the "correct answer")
> So maybe you’d have a clause which says, if the other player gives an ultimatum message, then you will go along with that.
But that doesn't work, because both players can send such a message simultaneously, but they can't both comply simultaneously.
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']]"
Not if we use RGB, send the color as a tuple of three numbers and average both tuples (taking the floor for example if one of the numbers is odd).
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.
So still think it makes sense to say it. It might get through and they repeat and we win. It might not, and they'd be taking a guess that I'd said it. (but the alternate would be I've not sent a message, providing best output of game-running forever/death - so if they presumed I was logical, they'd know I'd said 'blue')
>>> and the two of you would just scream "blue" at each other
You come to an agreement before you announce a choice.
Also that I'd mis-read the question - I'd assumed it was being played with one of the variations, but the variation being used wasn't shared with the participants.
I was always awful at reading the question..
Also my 'gut random colour' was red, but got blue back from google. Maybe there's something about red being a more assertive colour - or maybe it just helps to identify people who googled this article before an interview.
Then pray they didn’t do something similar :)
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?
"
i am going to send a random posint next round, and will continue to do so until you also send a random posint.
When we both receive posints, if they are identical, resend.
Otherwise, if both are the same parity, then we should choose red on the following round. otherwise, blue.
If for some reason your message details a strategy similar to this but with a different color decision based on the parity, then we should use the larger posint sender as the one to dictate the color decision strategy. "
You could argue that humans have a certain inbuilt meta-strategy for agreeing on strategies and are all inherently different enough to symmetry-break the situation eventually. But the problem supposes everyone is a perfect logician (not a fallible human), and so relying on this "inbuilt meta-strategy" is as mathematically interesting as the answer "people put into this situation will often succeed". (Note that, when pairing up most top-level comments in this thread, if they were executed as written, you would end up with people either failing or never finishing.)
I also think that randomness is, mathematically, a cop-out for two reasons: It requires some external source of "symmetry breaking" (although I suppose humans are decent enough at picking random numbers), and it only gives a probabilistic solution (although this will be good enough in practice). And it does not in itself contribute to solving meta-problem of strategy agreement either.
In terms of a solution to the problem as posed, we can reason that, since the other side is a perfect logician, they will not choose a (meta-)*strategy that can possibly result in a "deadlock". For example, they will not choose "I wait until you write 'blue' and then say 'blue' to the host, and I will never diverge from this strategy" as this runs into a deadlock with the same strategy but different color. "Deadlock" here doesn't necessarily mean "fails to break symmetry", as some strategies don't require that ("choose the average of the two RGB values").
The question remains whether there exists any provably non-deadlockable (meta-)*strategy. If, for every communicated strategy (and this includes any level of meta-strategy), a different strategy is conceivable that results in a deadlock, the problem has no solution. I don't know the answer to this, but here are some thoughts:
- Are what I called "deadlocks" above not just symmetry breaking failures on the (or a certain) meta-level?
- We can average colors to avoid the need for symmetry breaking in color choice. Can we do the same on the (meta-)*strategy level somehow?
- If messages must not be of finite length, it feels like there should be some trick to obtain a solution. But I guess we are interested only in finite message lengths.
The problem is that every proposal of a-e could get matched with something a-e that ruins it.
Examples:
1. I say just a color, they say just a color. You stay by the color they also stay, you decide to switch they also do it at the same time.
2. You propose something to confirm, so did they and we are back at 1.
3. You decide to do something random and they also decide to do something random with the same outcome
Since you are both perfect logical, you will realize that, making any try obsolete.
So you could try to get to know each other and just chat to something unrelated but there is still the problem that they could exactly mirror your messages again.
So you both come to the conclusion that there is no 100% strategy. You could now decide that you should continue playing the game forever or decide that a strategy with less than 100% is good enough.
Both have etablished now that using a meta strategy to agree on something is just a waste of time, because of a-e and we can just stay on the main layer. Repeating the color is also useless because the other might have the same strategy. So the only solution would be to announce just random colors and as soon as they match we end the game and are free. Theoretically they never have to match so the game could just go forever (hence it's not 100%).
I’m not familiar with the term “degree course”, but suspect the candidates were bright, but also around 18 years old.
Form those, bachelor’s to me, seemed the most likely by a wide margin, but I donn’t know whether the British educational system has its quirks. Especially in the likes of Oxford and Cambridge, that doesn’t seem unlikely to me.
[Fairly early in the pandemic, satirical organ Private Eye had an item on the cabinet(?) discussing the disastrous lack of PPE. Even the prime minister only did Greats, and some of the cabinet didn't even go to Oxford.]
Orange
Yellow
Green
Blue
Indigo
Violet. < Finish game
Idea is to use an external object as the "witness" to arrive at consensus.
Violet
Indigo
Blue
Green
Yellow
Orange
Red. < Finish game
You lose.
If the assumption is Western (and it seems to be as both contestants seem to speak the same language at least), Roy G. Biv wins. Or what ever anacronym I've not heard of one starting with violet.
I get you are trying to show the synchronising problem but using a third party (in this case a common well known reference) as a biased influence to a certain pattern and order.
I get ya though it's not working the logic side so much
This typpe of problem is nearly impossible for folks that have never heard a similar test and nearly trivial for someone who has heard ~3 like it.
The object is generally to explore how a candidate thinks. If it turns out they memorised logic puzzles and can’t explain them then they will not get through the interview.
The interviews were an in-depth back-and-forth discussion, as much as could be had in about 25 minutes. These interviews, of course, are just one component among many in regard to the difficult admissions decision, a chance for the candidate to show us how they think through a problem, how well they can explain their ideas, how well they take hints and suggestions. In every interview, we had paused at a certain stage, when the candidate had a fully formed argument for one of the variations, and asked them to undertake an integrative exercise, summarizing as clearly as they could the entire problem and solution and how they expected it to play out. Since these were interviews for joint philosophy degrees, in my view this step was a key part of the interview, measuring the ability of the candidate to integrate what they had learned from the discussion and to present a complete, coherent argument.
My guess is that 'impossible problems' either pick up on people who know "Oh that's the 2 generals problem" (gold star) or can quickly cycle through ideas and then pick up on the shortcomings as they mentally explore. Maybe A+ if they can explain why it's impossible, A if they say it is, D- if come up with something that doesn't work.
So it becomes a test of preparedness and ruthlessness. The winner is the one who finds out what the questions are and studies them. Or studies enough IQ stuff to get through.
Its leetcode basically.
Not sure what the solution is. I think additional on topic exams you study for and have past papers would be better.
I didnt apply for oxbridge because of this extra pressure. My worry was id screw up the bread and butter of the a levels with the extra study needed for this kind of test.
Being an interview scenario too means you need to act. I was shy but very passionate about maths. A London college gave me feedback I wasn’t passionate about maths and should consider another course. Based in half an hour with me.