21 ms·

Coming to Agreement, a logic puzzle for Oxford admissions interviews

63 points by mathgenius 5y ago

exdsq 5y ago
People might enjoy these questions from the All Souls College exam (a college at Oxford) https://www.asc.ox.ac.uk/sites/default/files/migrated-files/GeneralPastPapers.pdf https://www.asc.ox.ac.uk/sites/default/files/migrated-files/...
- gnufx 5y ago
  For people who don't know, All Souls isn't a normal college. https://en.wikipedia.org/wiki/All_Souls_College%2C_Oxford https://en.wikipedia.org/wiki/All_Souls_College%2C_Oxford might give some insight.
kangnkodos 5y ago
My message in round 1 would be: "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.
GenerocUsername 5y ago
These puzzles would make horrible college admissions tests. They hardly qualify as interview questions. 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.
- aardvark179 5y ago
  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.
- jonsen 5y ago
  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.
- rndm_access 5y ago
  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.
deleted 5y ago
[deleted]
kaz_sadeghi 5y ago
I'm surprised more people didn't recognize the two generals problem.
- nkmnz 5y ago
  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.
  - josephcsible 5y ago
    But isn't that exactly what the "Pigeon variation" the article mentions is?
- Someone 5y ago
  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.
  - thaumasiotes 5y ago
    I'm guessing "degree course" means "degree".
    - Someone 5y ago
      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.
      - gnufx 5y ago
nkmnz 5y ago
„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! Where can I get my ticket to Oxford?
- goldcd 5y ago
  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.
  - nkmnz 5y ago
    Exactly. Asymmetric payoffs lead to strange behavior.
    - goldcd 5y ago
      But I'd then be asking for a clarification of "life and death" 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"
Fellshard 5y ago
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...
curiousgal 5y ago
> 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).
- scatters 5y ago
  How would you know to use RGB and not CMYK or HSL?
  - curiousgal 5y ago
    Does it matter? I mean when we announce the color we will announce it in all of them since it's the same color.
goldcd 5y ago
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.
- nkmnz 5y ago
  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.
  - goldcd 5y ago
    Then as I mentioned below, you neither of you send a message and the game remains open indefinitely.
    - nkmnz 5y ago
      How do you do that after you’ve been killed for screaming „blue“?
      - goldcd 5y ago
        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')
      - thaumasiotes 5y ago
        You don't seem to have read all of goldcd's original comment: >>> and the two of you would just scream "blue" at each other You come to an agreement before you announce a choice.
throwaway73838 5y ago
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.
- mattlondon 5y ago
  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")
  - thaumasiotes 5y ago
    Waiting has just as much of a symmetry problem as leading does.
- thaumasiotes 5y ago
  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.
lordnacho 5y ago
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.
- d136o 5y ago
  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.
- gnufx 5y ago
  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.)
roomey 5y ago
Red Orange Yellow Green Blue Indigo Violet. < Finish game Idea is to use an external object as the "witness" to arrive at consensus.
- MauranKilom 5y ago
  You receive the following messages in reply: Violet Indigo Blue Green Yellow Orange Red. < Finish game You lose.
  - roomey 5y ago
    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
caffeine 5y ago
These seem like they would be pretty simple for anyone that has studied some networking …
brandonmenc 5y ago
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.
triactual 5y ago
This is a fun problem. There’s a squirrel catcher to get over in recognizing the symmetry problem and then there’s all kinds of ideas to explore.
eaglelamp 5y ago
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.
- deleted 5y ago
  [deleted]
- MauranKilom 5y ago
  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.
  - eaglelamp 5y ago
    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.
bakuninsbart 5y ago
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.
jedberg 5y ago
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.
- MauranKilom 5y ago
  > 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.
  - jedberg 5y ago
    > 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.
oli5679 5y ago
Would this work? 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']]"
ttz 5y ago
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.
- MauranKilom 5y ago
  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" What do you do?
- ttz 5y ago
  ah, yes, good point. thanks for the catch!
- ttz 5y ago
  revised solution? " 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. "
y7 5y ago
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.
- mjmahone17 5y ago
  The coin flip on the main puzzle is assuming each person proposes exactly one color: do you switch or stay the same. So there is guaranteed to be at most a pair of colors, and the goal is to eventually get agreement between those two options.
  - y7 5y ago
    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?
    - mjmahone17 5y ago
      Right exactly. 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.
goodgoodmike 5y ago
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.
ximeng 5y ago
Trying to make this a little more rigorous: You have two VMs, VM one has a program pre-loaded that takes an optional tuple (bool endGame, rgb agreed_color, string message) and emits a tuple in the same format. The message from the emitted tuple is used as input to a similar program on the second VM, the output message of which is passed as input to the first VM. Both VMs also send their output to a judge which decides the next stage of the game as follows: The game ends with a win if the output from both programs includes endGame set to true and agreed_color set to the same as the other program. If endGame is set to true by either program then the game is lost unless the win condition is true. Otherwise the game continues. You need to write the program on the second VM without knowing the program on the first VM. However you can assume a "logical" program is loaded. If we assume this means you can send code through to execute on the other machine: eval(message), then we can simplify the problem to loading the same program on both VMs and executing it. This is easy as is, program both machines to output (true, red, ""). So to make it interesting there needs to be some complications. Effectively there is some hidden state on the first VM. Maybe this could be modeled as a random permutation of the color space on the first VM such that any reference to a color is first permuted before being output, including within messages. This would mean the initial program above could now produce (true, blue, "") on the first VM. However, the programs are identical and don't know which VM they are running on. Is this a good model for the problem? How could we improve it to add a solution?
- y7 5y ago
  I think this is an arbitrary "computerification" of the problem, and doesn't really make things clearer.
  - ximeng 5y ago
    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.
deleted 5y ago
[deleted]
MauranKilom 5y ago
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.
- 5y ago
deleted 5y ago
[deleted]
kthejoker2 5y ago
Literal collision variation: 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?
- Something1234 5y ago
  Take out my phone and turn on my flashlight, so they can see me. Also hug the right wall, cause that's what most people do.
  - themarlzy 5y ago
    Unless you had me - in Australia we’d veer left
- BoiledCabbage 5y ago
  Pretty simple because time isn't discrete in this puzzle. 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.
lovecg 5y ago
“On the next round I will say Blue. I will not open the message you’re sending me so I have no idea what you said, so it’s in your best interest to say Blue as well.” Then pray they didn’t do something similar :)

63 points by mathgenius 5y ago

People might enjoy these questions from the All Souls College exam (a college at Oxford) https://www.asc.ox.ac.uk/sites/default/files/migrated-files/GeneralPastPapers.pdf https://www.asc.ox.ac.uk/sites/default/files/migrated-files/...

gnufx 5y ago
For people who don't know, All Souls isn't a normal college. https://en.wikipedia.org/wiki/All_Souls_College%2C_Oxford https://en.wikipedia.org/wiki/All_Souls_College%2C_Oxford might give some insight.

kangnkodos 5y ago

My message in round 1 would be: "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.

GenerocUsername 5y ago

These puzzles would make horrible college admissions tests. They hardly qualify as interview questions. 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.

aardvark179 5y ago
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.
jonsen 5y ago
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.
rndm_access 5y ago
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.

deleted 5y ago

[deleted]

kaz_sadeghi 5y ago

I'm surprised more people didn't recognize the two generals problem.

nkmnz 5y ago
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.
- josephcsible 5y ago
  But isn't that exactly what the "Pigeon variation" the article mentions is?
Someone 5y ago
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.
- thaumasiotes 5y ago
  I'm guessing "degree course" means "degree".
  - Someone 5y ago
    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.
    - gnufx 5y ago

nkmnz 5y ago

„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! Where can I get my ticket to Oxford?

goldcd 5y ago
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.
- nkmnz 5y ago
  Exactly. Asymmetric payoffs lead to strange behavior.
  - goldcd 5y ago
    But I'd then be asking for a clarification of "life and death" 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"

Fellshard 5y ago

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

curiousgal 5y ago

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

scatters 5y ago
How would you know to use RGB and not CMYK or HSL?
- curiousgal 5y ago
  Does it matter? I mean when we announce the color we will announce it in all of them since it's the same color.

goldcd 5y ago

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.

nkmnz 5y ago
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.
- goldcd 5y ago
  Then as I mentioned below, you neither of you send a message and the game remains open indefinitely.
  - nkmnz 5y ago
    How do you do that after you’ve been killed for screaming „blue“?
    - goldcd 5y ago
      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')
    - thaumasiotes 5y ago
      You don't seem to have read all of goldcd's original comment: >>> and the two of you would just scream "blue" at each other You come to an agreement before you announce a choice.

throwaway73838 5y ago

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.

mattlondon 5y ago
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")
- thaumasiotes 5y ago
  Waiting has just as much of a symmetry problem as leading does.
thaumasiotes 5y ago
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.

lordnacho 5y ago

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.

d136o 5y ago
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.
gnufx 5y ago
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.)

roomey 5y ago

Red Orange Yellow Green Blue Indigo Violet. < Finish game Idea is to use an external object as the "witness" to arrive at consensus.

MauranKilom 5y ago
You receive the following messages in reply: Violet Indigo Blue Green Yellow Orange Red. < Finish game You lose.
- roomey 5y ago
  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

caffeine 5y ago

These seem like they would be pretty simple for anyone that has studied some networking …

brandonmenc 5y ago

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.

triactual 5y ago

This is a fun problem. There’s a squirrel catcher to get over in recognizing the symmetry problem and then there’s all kinds of ideas to explore.

eaglelamp 5y ago

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.

deleted 5y ago
[deleted]
MauranKilom 5y ago
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.
- eaglelamp 5y ago
  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.

bakuninsbart 5y ago

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.

jedberg 5y ago

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.

MauranKilom 5y ago
> 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.
- jedberg 5y ago
  > 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.

oli5679 5y ago

Would this work? 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']]"

ttz 5y ago

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.

MauranKilom 5y ago
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" What do you do?
ttz 5y ago
ah, yes, good point. thanks for the catch!
ttz 5y ago
revised solution? " 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. "

y7 5y ago

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.

mjmahone17 5y ago
The coin flip on the main puzzle is assuming each person proposes exactly one color: do you switch or stay the same. So there is guaranteed to be at most a pair of colors, and the goal is to eventually get agreement between those two options.
- y7 5y ago
  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?
  - mjmahone17 5y ago
    Right exactly. 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.

goodgoodmike 5y ago

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.

ximeng 5y ago

Trying to make this a little more rigorous: You have two VMs, VM one has a program pre-loaded that takes an optional tuple (bool endGame, rgb agreed_color, string message) and emits a tuple in the same format. The message from the emitted tuple is used as input to a similar program on the second VM, the output message of which is passed as input to the first VM. Both VMs also send their output to a judge which decides the next stage of the game as follows: The game ends with a win if the output from both programs includes endGame set to true and agreed_color set to the same as the other program. If endGame is set to true by either program then the game is lost unless the win condition is true. Otherwise the game continues. You need to write the program on the second VM without knowing the program on the first VM. However you can assume a "logical" program is loaded. If we assume this means you can send code through to execute on the other machine: eval(message), then we can simplify the problem to loading the same program on both VMs and executing it. This is easy as is, program both machines to output (true, red, ""). So to make it interesting there needs to be some complications. Effectively there is some hidden state on the first VM. Maybe this could be modeled as a random permutation of the color space on the first VM such that any reference to a color is first permuted before being output, including within messages. This would mean the initial program above could now produce (true, blue, "") on the first VM. However, the programs are identical and don't know which VM they are running on. Is this a good model for the problem? How could we improve it to add a solution?

y7 5y ago
I think this is an arbitrary "computerification" of the problem, and doesn't really make things clearer.
- ximeng 5y ago
  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.

deleted 5y ago

[deleted]

MauranKilom 5y ago

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.

5y ago

deleted 5y ago

[deleted]

kthejoker2 5y ago

Literal collision variation: 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?

Something1234 5y ago
Take out my phone and turn on my flashlight, so they can see me. Also hug the right wall, cause that's what most people do.
- themarlzy 5y ago
  Unless you had me - in Australia we’d veer left
BoiledCabbage 5y ago
Pretty simple because time isn't discrete in this puzzle. 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.

lovecg 5y ago

“On the next round I will say Blue. I will not open the message you’re sending me so I have no idea what you said, so it’s in your best interest to say Blue as well.” Then pray they didn’t do something similar :)