Ah, I love these kind of puzzles!<p>Here's another one, similiar to the first one (Names in Boxes). Apologies for any incorrections in advance.<p>There are 100 prisoners. At random times one prisoner is chosen uniformly at random and led into a room with a single lamp. The prisoner can choose to switch it on or off or leave it as the last visiting prisoner left it. Apart from the state of the lamp he must leave the room unchanged.<p>After visiting the room, each prisoner is asked if every prisoner has visited the room by now. If he answers 'Yes' and indeed everyone has been to the room at least once, then everybody is freed immediately. Otherwise they are all executed ;) He can answer 'I don't know' without any consequences.<p>Apart from the lamp being on or off the prisoners have no way of communication at all, but of course as is customary in such puzzles they can plot a strategy in advance and everybody is a perfect logician.<p>So, to clarify: The goal is for one prisoner to be 100% sure that everybody has been to the room at least once. The "easiest" solution would simply be to wait a few billion years (it's an abstract puzzle, they are all immortal anyways ;). But of course there is a more elegant solution that terminates earlier.<p>Also, as the time for a visit is chosen at random a prisoner has no way of knowing who the previous person in the room was. It might just as well have been himself!<p>As there is some randomness involved, it is theoretically possible that the goal state never happens. Just assume that in the limit everybody will have visited the room infinitely often ;)<p>In other words: Implement synchronization between 100 threads with only one bit of shared memory and completely random scheduling.
I like Cheryl's transfinite logic puzzle, which takes logic puzzles to a ridiculous extreme.<p><a href="http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-challenge/" rel="nofollow">http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-ch...</a><p>The puzzle is inspired by Cantor's transfinite ordinal numbers, which are pretty cool. You don't need to know anything about transfinite numbers to solve the puzzle, but they are interesting in their own right. The simplified idea is suppose you count 1, 2, 3, ... up to infinity (ω). Everyone knows adding 1 to infinity doesn't get you anywhere, but suppose you can do it and get ω+1, ω+2, ... The limit is 2ω. But then you can go 3ω, 4ω, ... Which obviously :-) gets you to ω*ω = ω^2. Then you can keep going with bigger and bigger infinities. See <a href="https://en.wikipedia.org/wiki/Ordinal_number" rel="nofollow">https://en.wikipedia.org/wiki/Ordinal_number</a>
"Learning a single variable polynomial" also falls into this camp, although partly due to learned bias.<p><a href="https://jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/" rel="nofollow">https://jeremykun.com/2014/11/18/learning-a-single-variable-...</a>
I collect riddles like these! Here are a few of them.<p>Numbered Hats<p>A warden places a hat on the head of each of 100 prisoners, each with a random number from 1 to 100. There may be duplicates. Each prisoner can see everybody's hat but their own. Each prisoner then guesses their own number; if any guess correctly, they all go free. The group may not communicate in any way during the trial, but may strategize beforehand. What strategy has the best chance of success?<p>Colored Hats<p>A warden lines up a group of 30 prisoners so they can see everybody in front of them and nobody behind them, then places either a red or a blue hat on each of their heads, randomly. He then goes from the back of the line to the front, telling each prisoner to guess the color of their own hat. Each who guesses correctly is freed. The prisoners cannot see the color of their own hat, and cannot communicate with each other, but can hear each others' guesses and can strategize beforehand. What strategy saves the greatest number of prisoners?<p>Coins on a Chessboard<p>A warden takes prisoner A into a room containing a chessboard, on each square of which is a coin randomly showing heads or tails. He then indicates a random square on that board. Prisoner A is given the chance to flip one coin (or none), then taken from the room, after which prisoner B is taken into the room and must say which square the warden indicated. The two prisoners may strategize beforehand, but may not communicate during the trial (except with the single coin flip). What should be their strategy?
A different solution to the Box in box problem, with less math:<p>Consider the square of (length + with + height). The sum of the diagonal terms is the square of the distance between opposite corners, the sum of the off diagonal terms equals half the area of the boxes. We can show that both these terms are smaller for the innermost box.<p>It’s obvious for the diagonal terms, as the opposite corners of a box are the two points of the box that are furthest apart. So the opposite corners of the inner box must be separated by less than the opposite corners of the outer one.<p>For the cross diagonal terms: take axes that are aligned with the inner box. Consider the parts of the outer box that would be projected on the inner box if you projected either on the x&y, x&z, or y&z planes (i.e. you project on the faces of the inner box). These six pieces of the outer box don’t intersect, and each of them is larger than the face of the inner box on which they project. So this part of the outer box has an area bigger than the total are of the inner box.
QED
The 'dot-town suicides' is a more general version of a puzzle I know, "The Island with Blue-Eyed People". The solution is an induction, which is unusual in these kinds of problems.
It's not in the same vein, but my favorite puzzle is the Monty Hall Problem. Although as is relentlessly pointed out, it's not actually how "Let's Make A Deal" works.<p>Monty Hall shows you three doors, two have goats behind them, one has a brand new car. While still closed, you pick a door. After you've picked, Monty opens one of the other two doors to show you a goat, and asks if you want to stay with your choice, or choose the other remaining door. What do you do? Stay? Switch? Or it doesn't matter?<p>For background and spoiler, <a href="https://en.wikipedia.org/wiki/Monty_Hall_problem" rel="nofollow">https://en.wikipedia.org/wiki/Monty_Hall_problem</a><p>Edit: Spelling
SPOILER 1 Names in boxes<p>I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if chance has it that there are two cycles of length 50. Then it seems the chance would be very large that one of the 100 prisoners would en up in the "wrong" loop and thus not find their name?
Peter Winkler's books of mathematical puzzles ("Mathematical Puzzles" and "Mathematical Mind-Benders") are top-notch and highly recommended. You will learn something there even if you've read dozens of puzzle books before.
Some of these are poorly worded:<p>* Kleptopia is ambiguous about what gets stolen, and what toplogy the boxes/padlocks must have for the solution.<p>* The "clever" solution to Unwanted Expansion isn't a complete proof, unless you add some complicated reasoning or use the non-clever proof, but if you do that, you don't need the "clever" proof at all.<p>* The Wimbledon puzzle doesn't explain the scoring rules of tennis :(
I think there's a simpler solution to boxes in boxes. Assume that the outer box is axis-aligned. Project both boxes onto the X axis, so they become one-dimensional. It's easy to check that the "projected perimeter" of the inner box is smaller. Repeat for axes Y and Z. From that and the triangle inequality, the result follows.
<spoiler>For #1, I didn't hear correctly because I didn't understand that the clearly insane and cruel warden would let the prisoners label the boxes before hand :-/
I'm have some trouble understanding the solution to the 3 natives puzzle. Is the objective to find the road guarded by the truth teller?<p>SPOILER BELOW<p>The solution suggests<p>Q1) --> A<p>Q1): Is B least likely to tell the truth out of B and C?<p>If yes ask Q2 --> B, If no, ask Q2 --> C<p>Q2): If I were to ask you does your road lead to the truth village, would you say yes?<p>If yes, you know where the truth village is. If no, you would know the person you are questioning in the liar, but both of the other two could be the truth teller or the random answerer?<p>For example, if A is the random answerer and randomly selects 'truth', or if A is the truth teller, they will both direct you to the liar for Q2.<p>Let me know where I've gone wrong.
I have always been a fan of the Pirate game puzzle. <a href="https://omohundro.files.wordpress.com/2009/03/stewart99_a_puzzle_for_pirates.pdf" rel="nofollow">https://omohundro.files.wordpress.com/2009/03/stewart99_a_pu...</a>
One that I heard last week:
There is an 8x8 checkerboard in a room with a coin placed on each square. Each coin is either facing heads or tails up, and the face is determined randomly. Before you can inspect the board, a "master" comes in, picks a square of interest, and must make a manipulation to the board by flipping one of the 64 coins. He then exits the room. You are now allowed to enter, and must read out which square of interest the master chose by inspecting the state of the board. There is a strategy that is guaranteed to work for all possible configurations of the board.
Of course a few of these mathematical puzzles assume that the human beings involved are all robotic, and capable of remembering a randomly ordered list 100 long. The blue dot red dot problem being the worst offender because the theorem doesn't hold up of you assume anyone in the village has the wrong internal state.
A short collection of similar puzzles that have been shared with me over the years: <a href="https://quaxio.com/some_math_puzzles/" rel="nofollow">https://quaxio.com/some_math_puzzles/</a>