Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Coming to Agreement, a logic puzzle for Oxford admissions interviews

jdh.hamkins.org

Post reply on HN
Print view View original

81–90 of 99 posts

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#81

Post by throwaway73838 »

thaumasiotes wrote: post #26
throwaway73838 wrote: post #14

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 yo…

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…

Yeah, randomness is the only way to break the symmetry problem.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#82

Post by ttz »

ttz wrote: post #56

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.

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

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#83

Post by kthejoker2 »

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?

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#84

Post by [deleted] »

eaglelamp wrote: post #43

For the first scenario send the message: If two primary colors end and state the color that results from mixing, . 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 t…

[deleted]

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#86

Post by tigertigertiger »

MauranKilom wrote: post #74

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 complet…

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

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#87

Post by Someone »

thaumasiotes wrote: post #30
Someone wrote: post #7

Earlier quoted context omitted.

FTA: We had used these puzzles in our admissions interviews of candidates for a place at Oxford University in the degree courses Math/philosophy, CS/philosophy, and PPE at University College, Oxford I’m not familiar with the term “degree course”, but suspect the candidates were bright, but also around 18 years old.

I'm guessing "degree course" means "degree".

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.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#88

Post by BoiledCabbage »

kthejoker2 wrote: post #83

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 t…

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.

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#89

Post by roomey »

MauranKilom wrote: post #68
roomey wrote: post #31

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

You receive the following messages in reply: Violet Indigo Blue Green Yellow Orange Red. You lose.

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

Re: Coming to Agreement, a logic puzzle for Oxford admissions interviews

#90

Post by Something1234 »

kthejoker2 wrote: post #83

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 t…

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.
Post reply on HN