Four really hard logic puzzles
These have in common that they can sound impossible at first description, even (or perhaps especially) to seasoned puzzlers and/or people with some mathematical knowledge. In all cases, if I were presented with them for the first time and asked "either do this or provide a proof that it's mathematically impossible", I'd be inclined to start working on the impossibility proof first - but I'd be wrong.
I will discuss solutions in a separate post, so there are no spoilers in the body of this post (although there are spoilers for the yellow hats one in the linked ACX comment thread). You can discuss solutions in comments here if you like, or wait for the follow-up post. I will say, though, that some of the solutions are a bit involved, so if you're hoping for a solution as concise and elegant as "ask the guard what the other guard would say" you might be disappointed.
1. The 100 prisoners and boxes puzzle
This was first told to me by a colleague at Autonomy about 15 years ago.
There are 100 prisoners, and there's a room containing 100 boxes, where each box contains a piece of paper with one prisoner's name written on it, and each of the 100 names is in one box. The prisoners will each go one at a time into the room, look inside up to 50 of the boxes and close them again (so that the boxes look indistinguishable from if they'd never been opened), and leave by another exit before the next prisoner comes in.
If all the prisoners find their own names, all the prisoners will be released; if even one prisoner fails to find their own name, they'll all be executed. They can decide on a strategy together in advance, but once the first prisoner has entered the room they can't communicate.
This is a probabilistic puzzle: you're not expected to come up with a strategy that will guarantee success, but one that does significantly better than the infinitesimal chance of success you'd have if everyone just opened 50 boxes at random.
2. The chessboard puzzle
gerald_duck recently posted this and said that some maths celebrities like Matt Parker couldn't solve it.
There's a chessboard with a coin on each of the 64 squares, some showing heads, some showing tails. You see someone hide a very small piece of paper under one of the coins. You may optionally turn one of the coins over to its other side, and then you must leave the room, and your associate can come in and try to guess which coin the paper is hidden under. You can decide on a strategy together in advance, but you can't use any "physical" tricks like the coin you touched being warmer or having fingerprint grease on it or being off-centre in its square.
This is not a probabilistic puzzle: the aim is to come up with a strategy that will guarantee success.
3. The yellow hats puzzle
This was recently posted in a comment on Astral Codex Ten (Scott Alexander's new blog). Many of the commenters there seemed to think it was impossible. I'll quote it verbatim (partly because of the entertainingness of the failure consequences):
You and your thirty friends have been imprisoned by a mad logician.
You are going to be placed in a room together, each wearing either a buttercup yellow hat or a hat or a cadmium yellow hat (I like yellow!)
Each of you will then be simultaneously and secretly given the option to guess which shade of hat you are wearing (although you are allowed to demur and not guess if you choose). If any of you guess correctly and no-one guesses incorrectly then you will be released, but if anyone guesses incorrectly, or if all thirty-one of you decline to guess, then you will be sentenced to spend the next twenty years either unable to lie or unable to tell the truth, guarding a door which may or may not have a goat behind it.
Once the trial has started you are forbidden from communicating, but you can agree a strategy in advance. What is the best chance of escape you can manage?
4. The red/green/blue hats puzzle
You're in a group of five people. You will each be given a red, green, or blue hat, and then be seated opposite each other in a row of 2 and a row of 3 (so each person can see the people in the row opposite but not the ones in their own row). There are no guarantees about the distribution of the five hat colours: they could be any combination, like RRRRR, RGBBB, etc.
Your aim is for at least one of you to guess their own hat colour correctly.
You can decide on a strategy together in advance, but guesses are simultaneous (so you can't get any information from anyone else's guess before making your own guess).
This is not a probabilistic puzzle: the aim is to come up with a strategy that will guarantee success.
I will discuss solutions in a separate post, so there are no spoilers in the body of this post (although there are spoilers for the yellow hats one in the linked ACX comment thread). You can discuss solutions in comments here if you like, or wait for the follow-up post. I will say, though, that some of the solutions are a bit involved, so if you're hoping for a solution as concise and elegant as "ask the guard what the other guard would say" you might be disappointed.
1. The 100 prisoners and boxes puzzle
This was first told to me by a colleague at Autonomy about 15 years ago.
There are 100 prisoners, and there's a room containing 100 boxes, where each box contains a piece of paper with one prisoner's name written on it, and each of the 100 names is in one box. The prisoners will each go one at a time into the room, look inside up to 50 of the boxes and close them again (so that the boxes look indistinguishable from if they'd never been opened), and leave by another exit before the next prisoner comes in.
If all the prisoners find their own names, all the prisoners will be released; if even one prisoner fails to find their own name, they'll all be executed. They can decide on a strategy together in advance, but once the first prisoner has entered the room they can't communicate.
This is a probabilistic puzzle: you're not expected to come up with a strategy that will guarantee success, but one that does significantly better than the infinitesimal chance of success you'd have if everyone just opened 50 boxes at random.
2. The chessboard puzzle
gerald_duck recently posted this and said that some maths celebrities like Matt Parker couldn't solve it.
There's a chessboard with a coin on each of the 64 squares, some showing heads, some showing tails. You see someone hide a very small piece of paper under one of the coins. You may optionally turn one of the coins over to its other side, and then you must leave the room, and your associate can come in and try to guess which coin the paper is hidden under. You can decide on a strategy together in advance, but you can't use any "physical" tricks like the coin you touched being warmer or having fingerprint grease on it or being off-centre in its square.
This is not a probabilistic puzzle: the aim is to come up with a strategy that will guarantee success.
3. The yellow hats puzzle
This was recently posted in a comment on Astral Codex Ten (Scott Alexander's new blog). Many of the commenters there seemed to think it was impossible. I'll quote it verbatim (partly because of the entertainingness of the failure consequences):
You and your thirty friends have been imprisoned by a mad logician.
You are going to be placed in a room together, each wearing either a buttercup yellow hat or a hat or a cadmium yellow hat (I like yellow!)
Each of you will then be simultaneously and secretly given the option to guess which shade of hat you are wearing (although you are allowed to demur and not guess if you choose). If any of you guess correctly and no-one guesses incorrectly then you will be released, but if anyone guesses incorrectly, or if all thirty-one of you decline to guess, then you will be sentenced to spend the next twenty years either unable to lie or unable to tell the truth, guarding a door which may or may not have a goat behind it.
Once the trial has started you are forbidden from communicating, but you can agree a strategy in advance. What is the best chance of escape you can manage?
4. The red/green/blue hats puzzle
You're in a group of five people. You will each be given a red, green, or blue hat, and then be seated opposite each other in a row of 2 and a row of 3 (so each person can see the people in the row opposite but not the ones in their own row). There are no guarantees about the distribution of the five hat colours: they could be any combination, like RRRRR, RGBBB, etc.
Your aim is for at least one of you to guess their own hat colour correctly.
You can decide on a strategy together in advance, but guesses are simultaneous (so you can't get any information from anyone else's guess before making your own guess).
This is not a probabilistic puzzle: the aim is to come up with a strategy that will guarantee success.