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

91–99 of 99 posts

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

#91

Post by totony »

mjmahone17 wrote: post #69
y7 wrote: post #57

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…

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.

>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

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

#92

Post by kybernetikos »

aaaaaaaaaaab wrote: post #55
brandonmenc wrote: post #47

Earlier quoted context omitted.

An intermediate step could be to send the two strategies back and forth at random until you both agree on the same one. The arbitrary message "constraint" seems to be an escape hatch.

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.

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

#93

Post by gnufx »

lordnacho wrote: post #23

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

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

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

#94

Post by gnufx »

exdsq wrote: post #53

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

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

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

#95

Post by gnufx »

Someone wrote: post #87
thaumasiotes wrote: post #30

Earlier quoted context omitted.

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.

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

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

#96

Post by thaumasiotes »

jameshart wrote: post #61
thaumasiotes wrote: post #30

Earlier quoted context omitted.

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

More precisely, a course of study which leads to a degree

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

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

#97

Post by themarlzy »

Something1234 wrote: post #90
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.

Unless you had me - in Australia we’d veer left

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

#99

Post by kangnkodos »

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.

Post reply on HN