They were used for interviews for maths and CS, so I think it’s quite likely the candidates would have seen similar puzzles before, but I think that misses the point. This sort of puzzle is there so that the students can either present and an answer and the interviewer can start to dig into it with more questions, or so that the candidate doesn’t come up with an answer immediately and the interviewer can ask other questions that will help them reason things out.
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.
Apparently it's neither intended nor used as an "impossible/trivial" problem:
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.
This is general problem with modern public founded education system - it prizes memorization of repetitive schemes - as it's easy to check on the mass scale who is able to memorize these schemes. It's several magnitudes harder to check who really is a material for a scientist among same large population of candidates. I was educated in top university in my Central European country and to this day cannot shake off memories of people who passed calculus exams by memorizing solutions of integrals instead of understanding how to solve them. It was a general scheme - mediocre students interested only in "getting paper" aka diploma were passing exams mostly flawless some of them even get scholarships[sic(k)!] while people interested in actually understanding material and doing projects by their own (most students were making projects in groups and changing only minor details and teachers were pretending they do not see that) were struggling within that system. As the system has memorization without understanding and cheating as a fundamental of it's construction and people who resist following that pathological scheme were simply penalized. Attempts to rationalize with academic teachers in many cases resulted in absurd remarks of "everyone have equal requirements for passing classes". Puke inducing every time I think about that.
They're a little bit pretentious, I'd agree - but handy to see how somebody thinks.
(I'd never heard of "2 generals" before - so had a fun "Oh that", "Noo, then that doesn't", "Maybe if I ask on reply?".. nope..)
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.
Especially so in a pressured time-limited scenario. Its almost like asking them to play chess. If you play chess and studied then opening moves you are at a massive advantage.
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.
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.
Right, the word for that course of study is "degree". (Also "major".) The word for a certificate that is kind of like a degree, but without the course of study, is "honorary degree".
That’s clear, yes, but it could be bachelor’s, masters, or Ph.D.
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.
I think you can assume this is for first degrees, mostly for candidates at, or recently at, school. As far as I know, PPE is only an undergraduate course, and DPhil (PhD) wouldn't be a "course". https://www.ox.ac.uk/admissions/undergraduate/courses-listin...
[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.]
It’s not the two generals problem because you can be sure that your companion gets the message (both literally a d figuratively). The two generals problem is about inherent uncertainty, while the given problem has full transparency.
„Imagine the stakes are very high—perhaps life and death.“
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!
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.
Consensus protocols 101? It seems to boil down to, 'who will subordinate' - it doesn't matter who, so long as someone does. There is a risk of interminably failing to come to consensus on a means for finding consensus, though, an infinite regression that would necessarily need to be broken by one or the other...
> Some student candidates had proposed an interesting idea of trying to blend the two colors. [...] I like this idea a lot, but it seems problematic in light of the fact that we don’t have such a clear and unambiguous means of combining colors.
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).
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.
This is not true in a live and death scenario, because with asymmetric payoffs like that - termination being the down side risk - it is not at all „rational“ to jump to the answer that gives the highest probability of success, if that answer still has a non-zero risk of death.
But I'm only killed if they don't say blue and end the game on that - if they stay silent the game runs forever.
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')
I must confess, I hadn't actually read the 2nd half.
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.
One of the difficulties is deciding on a strategy that would work even if the other player used the exact same strategy on you.
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.
If you can rely on the other player being logical (as suggested), just wait for them to suggest a colour then use it. If they do not suggest a colour (perhaps they are waiting for you to suggest?) then suggest a colour yourself, then the other player being as logical as you will use it.
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")
That's not a difficulty. As noted in the post, you can easily solve it through the application of randomness. All you need is for one player to send an unopposed message announcing a color; at that point both players can use that color. There are only two failure states you can be in: both players can be talking, or both players can be waiting for a message. In the first case, one player needs to shut up long enough for the other player to make a choice. In the second case, one player needs to make a choice. A random approach will let these tiebreakers occur in an asymmetric way.
> 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.
This is why Oxbridge admissions are a bit of a crap shoot.
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.
When it comes to programming puzzle interviews I went through a similar sort of realization, there is a baseline level of knowledge about algos/design/experience, but beyond some point it seemed to be about how well I could explain my way through a problem. For a problem which I didn’t know off the bat I had to talk with the interviewer to eventually get to a working solution. A *huge* part of that is about not losing my cool, about not getting into a mental headspace of being stuck.
Interestingly, the less I need a particular job opportunity the more comfortable I have been with these probing conversations.
It was a long time ago, but I don't remember the interview being confrontational, just thinking the tutors seemed a bit odd -- I'd led a sheltered life. (Most interviews and tutorials surely won't be conducted by professors.)
True, is that a natural or thought way to read a rainbow however?
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
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."
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.
>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.
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.
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.
>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 :^)
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.
Great point - it's not quite as trivial as it appears.
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.
For the first scenario send the message: If two primary colors end and state the color that results from mixing, <primary color>.
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.
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.
I see where you're coming from, but for the problem to be solvable at all we need to presuppose some base level of agreement about the world between you and your partner. To take your critique even further (I haven't seen the article, original sub was a twitter link) how do I know that my partner agrees with me on the set of primary colors?
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.
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.
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.
> Main puzzle: [...] Confirm you agree with the strategy on your next turn, as well as sending a color or null
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.
> What if they disagree with the strategy? How do you resolve the situation where their strategy is just as valid as yours?
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.
> 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.
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"?
- 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']]"
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.
The message you receive from the other party on round 1 reads like this:
"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"
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.
"
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.
What do you do they come up with a different but equally compelling strategy at the same time? One of you is going to have to start following the other person's strategy, but what if you do so at the same time?
>But I have got a coin in my pocket, and from now on, I intend each round to flip the coin, sending the red message on heads and the blue 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.
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
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.
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?
Yes it doesn't quite feel right, but the problem as posed also doesn't quite seem rigorous enough, leading to some of the confusion in the answers here with people saying it seems easy.
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.
Most commenters seem to completely miss the problem of agreeing on the strategy before agreeing on the color. That agreement is at least as difficult as the problem of agreeing on a color itself (because the space of possible strategies is, in some sense, larger than the space of colors), so this is in some sense a recursive problem. The article itself touches on this meta-strategy agreement problem, but then completely ignores it when presenting other strategies (and doesn't go above the first "meta" level).
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.
You are the only one that got the problem. I was wondering why even the author of the article got the problem wrong.
A perfect logican always needs a 100% chance for stopping the game. Each message could either be:
a) the exact same strategy
b) the same strategy with a small variance that is also reasonable
c) a completely reasonable other strategy
d) just a color
e) waiting or something unrelated to the problem itself
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%).
98 comments
[ 2.7 ms ] story [ 176 ms ] threadThis 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.
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.]
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"
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.
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.
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.
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
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.
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.
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"?
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']]"
https://www.asc.ox.ac.uk/sites/default/files/migrated-files/...
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. "
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
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.
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%).