I updated my version to correctly reflect what I heard. But I agree that it’s not as “logically correct” as the eye color counterpart. It’s an adulterated version next to a drink after all xD
2 Likes
Another epistemic puzzle involving a Cheryl…
And there were several other epistemic puzzles posted in that thread as well
1 Like
For those who enjoy the Cheryl-Birthday-style puzzle, this puzzle featured in the MIT Mystery Hunt in January this year. Or rather, the “⊥IW” Mystery Hunt. 
https://perpendicular.institute/puzzle/ignorance/
During the hunt, I had a lot of fun working through this one together with a friend. Both the graph and the nonogram subpuzzles were really good, and the way some of the later puzzles made use of the nesting of the “Albert knows that Bernard knows that…” - it did things that I hadn’t realized were even possible with this sort of “ignorance” mechanic in a puzzle.
3 Likes
My daughter came up with an explanation of the Blue Eyed solution that seems “understandable”.
It goes like this.
"
Each person thinks:
- The guru mentioned that there are blue eyes on the island - so everyone is thinking about that today!
- If the guru had said red, and I could see no red eyes, I’d have to leave.
- If the guru had said red and I could see only one red eye, that means there are either 1 red (Aaron) or 2 red eyes (red-eye-Aaron and myself)
- That means that if Aaron did have red eyes, and he did not leave tonight, I would have to leave with him tomorrow
- From this I can see that for any group of eye colour, n big, if they don’t leave on the nth day, I must leave with them on the n+1th day, because the only reason they stayed this long is because I am with them.
QED.
1 Like
I think I figured out a solution to this, but it might be more complex than necessary. I’m assuming that the solution is not just something silly like the Guru waiting N days and then just telling them each their eye color. That is, I’m assuming that solutions are constrained to the Guru only talking “today”, while the effect of the two people leaving must happen N days into the future relative to “today”. I also think that it is necessary to have at least N other people on the island, and set up some assumptions about their eye color.
A solution attempt
Let’s assume that there are also N other people on the island, and that those N people all have hazel eyes. Let’s also call the blue eyed and brown eyed persons Alice and Bob, respectively.
The Guru could say the following to everyone:
- For everyone except for me, the only possible (but necessarily extant) eye colors are blue, brown, and hazel. Note that this statement should be assumed to be carefully expressed such that it is not actually saying whether or not there are a non-zero number of each eye color.
- Alice and Bob have different colored eyes.
- I see at least one person with hazel eyes.
Note: I think that it is just necessary that there are at least N other people with the same eye color (different from brown and blue). If there are more than N, the Guru can first cull that group down to N, by saying the eye color of specific people. If there are other eye colors, those can be first culled away first. The remaining steps would have to be expressed in terms of just the remaining population that had not been culled.
Then N-1 days later, the N hazel eyed people will leave at midnight, which then causes Alice and Bob to realize their own eye color (the next morning when they see everyone else gone), so that they then leave at midnight at the end of the N-th day.
Is there are simpler way?
I was thinking about statements like “There are no more than N non-blue eyed people”, but I couldn’t quite get that to work.
1 Like
There is a solution that does not depend on the number of people on the island. That is, there is a solution where the only three people on the island are the Guru, Alice and Bob.
It’s not necessarily simpler, though… It depends on what you mean with “simple”
1 Like
Ok, I think I have an idea of how it’s done with just Alice (blue), Bob (brown), and the Guru.
Solution Concept
The Guru could say,
The following statements are true:
- If Alice’s eyes are green, then Bob’s eyes are brown.
- If Bob’s eyes are green, then Alice’s eyes are blue.
- If Bob is still on the island on tomorrow and his eyes are hazel, then Alice’s eyes are blue.
- If Alice is still on the island tomorrow and her eyes are hazel, then Bob’s eyes are brown.
- If Bob is still on the island on day 3 and his eyes are brown, then Alice’s eyes are blue.
- If Alice is still on the island on day 3 and her eyes are blue, then Bob’s eyes are brown.
Note: “today” is day 1 and “tomorrow” is day 2.
I think this would result in Alice and Bob both leaving the island at midnight at the end of day 3.
1 Like
Comments
Very close to what I would try, but you don’t need the reference to the days. You might also need a couple more colours.
1 Like
Hat Puzzles
There are a whole family of induction puzzles called “hat puzzles” (SPOILER) that combine epistemic logic with probability, and are even related to error-correcting codes (for reliable data transmission).
Spoiler Note: that section of that link describes the following example of this puzzle, but reading the whole article or its references will give away the solution to the puzzle below.
A Three Person Hat Puzzle
Alice, Bob, and Charlie wish to win the following team game.
- They cannot communicate by any means during the game, but before the game they can discuss to agree upon a strategy for how they will play (given knowledge of all of these rules).
- At the beginning of the game, they will each be assigned a hat, either red or blue, which are each picked by independent, fair coin flips.
- They are not able to see the color of their own hat, but will be able to see the colors of the other two people’s hats. They do not what the other players are guessing (or even whether or not they passed).
- They are then separated and each given the choice to either guess the color of their own hat or to pass.
- They win if at least one persons guesses correctly and none of them guess incorrectly. They lose if everyone passes or one of them guesses incorrectly.
What is a strategy that they can use to maximize their chances of winning?
A comment: Clearly, they could win with 50% odds if they agree that only Alice guesses and she picks randomly between red and blue. Can they do better than that?
2 Likes
Who leaves the island?
The ones smart enough to look at their reflection.
Next stop: navier-stokes.
1 Like
A riddle I did not know yet - very nice, thank you for sharing!
spoiler
I’m thinking of the following strategy: Whoever sees that the other two are wearing hats with the same color, should guess that their hat has the other color.
If they play using this strategy, then they lose in 2 of 8 cases, namely when all three wear hats of the same color.
In all other six cases there are two hats of the same color and one hat of the other color. Then exactly one person sees two hats of the same color and will guess correctly, hence they win in 6 out of 8 cases.
1 Like
I’ve got a solution for 75%. Can it be better than 75% chance?
1 Like
Here’s a nice hat colour puzzle for people who like the axiom of choice:
Hilbert’s prison has a prisoner for each natural number. On execution day, all prisoners are put in an infinite line, so that any prisoner can see all of those prisoners and only those prisoners that have been assigned a higher number. Each prisoner is given a black or a white hat by coin flip.
At noon, all prisoners have to declare a hat colour (simultaneously). Those prisoners that guess wrong are immediately executed. Those that survive are released. The prisoners discuss a strategy beforehand, and amazingly enough almost all prisoners manage to be released.
I’m trying to remember a variant, where the prisoners declare their hat colour one by one, which even more amazingly manages to save all prisoners but one, but I’m not sure of the conditions of that puzzle, and the solution escapes me at the moment…
I think the conditions should be: all prisoners declare their hat colour one by one, from small numbers to large, being executed as soon as they guess the wrong number. All prisoners can hear what the previous prisoners guessed. The first prisoner necessarily has only 50% chance to survive, but after that every single prisoner manages to guess their hat colour correctly.
2 Likes
Answering this requires either a proof or a counterexample.
Spoiler for this question and the puzzle below
There is a proof (for the general case) showing that the winning probability is bounded by 75% in this case.
Another hat puzzle: What if there were seven players instead of three?
Hint: Hamming(7,4) - Wikipedia
2 Likes
The name of your hint already was too big of a spoiler, but yeah, I see 
1 Like
spoiler
This is not a rigorous proof, but here’s how I would “intuitively” explain it:
Any strategy defines in which situations Alice, Bob and Charlie should make a guess. From the perspective of Alice (or Bob or Charlie), if Alice sees a combination of colors where the strategy tells Alice to make a guess, then from Alice’s perspective there are two possible cases left, and her guess will be correct in exactly one of them. This is true for any strategy.
So an optimal strategy should 1.) make it so in every case at least one of them makes a guess and 2.) try to group the “failcases” as much as possible. The above strategy does exactly this; The individual failcases are grouped in the two cases where all have the same hat color.
1 Like
spoiler
One way to define a strategy is to start with any case and accept it as a “failcase”. Then for every person we make a note, writing down what they see, along with the instruction “if you see exactly this, then guess that your color is X”, where X is the color which this particular person is not wearing in the failcase.
For example if we start with the case “every person wears a red hat”, then the instruction is “if you see all red hats, then guess that your hat is blue”.
For more complicated cases, we have to distinguish which people are wearing which color etc. The note should clearly define all of it.
This means that with a single failcase, we can “cover” all cases that are “adjacent” to it, that is, cases where we change the color of the hat of exactly one person. In the case of 7 people, one failcase can cover 8 cases (including itself).
Hence we need at least 2^7 / 8 = 16 failcases to cover all cases. This implies that (assuming that there exists an optimal strategy which can be constructed in this way) the best we can achieve is a winning chance of 1 - 16 / (2^7) = 7/8. However the question that remains is whether or not we can cover all cases without overlap.
1 Like
This Hilbert’s prison problem seems like a tricky one.
Some thoughts
My first thought is to consider the finite, sequential case to build some ideas.
With a finite number of prisoners, the first could guess the XOR of all of the rest. This has a 50% success probability, but it reveals to the second prisoner what their hat is, and then when that prisoner guesses correctly, it reveals to the next prisoner, and so on.
It does not seem obvious how to generalize the XOR function to infinite sequences of bits. However, what we basically want is a function that maps each infinite sequence of bits to a binary value, such that whenever just a single bit in the input sequence is changed, the binary output value is flipped.
I’m not sure if this function exists, let alone how to explicitly define this function, but I’m guessing that the hint about the axiom of choice is key to understanding that something like this exists. However, even if the AC implies that this function exists, without a concrete construction to allow the prisoners to actually compute it (just in principle at least, since actual practical computation seems to be out of the question for infinite sequences).
Maybe something like this function is not needed and there is some other way to solve the infinite, sequential form of the riddle.
2 Likes
The fact that AC is needed means that it cannot be defined explicitly 
More on this / also a slight hint
AC just promises the existence of a function, and the prisoners can then decide to pick an arbitrary one. The process of picking a function cannot be computable in the first place, since an uncountable number of choices needs to be made.
But yeah, I agree that this area becomes slightly hard to do “in practice”, but we have infinitely many prisoners, so it’s not practical anyways.
2 Likes
An Evil Number Riddle
Consider the following procedure:
- Pick an integer larger than one.
- If your number is even, divide it by two. Otherwise (if it is odd), multiply it by three and add one.
- Stop if the resulting number is one. Otherwise, repeat step 2 (on this new number), until you reach one.
Some examples of sequences that you might generate with the above steps:
- Starting with 5, you multiply by 3 and add one to get 16. Then, you divide 16 by two to get 8. Then, you divide 8 by two to get 4. Then, you divide 4 by two to get 2. Then, you divide 2 by two to get 1 and stop.
- Starting with 11, you go through 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, and then stop.
- Starting with 42, you go through 21, 64, 32, 16, 8, 4, 2, 1, and then stop
- Starting with any power of two, you just repeatedly divide by two, until you reach one, e.g., 32, 16, 8, 4, 2, 1.
If you try a bunch of starting numbers, you might find that you seem to always eventually return to one.
The question is: Are there starting numbers (let’s call these evil numbers) such that the procedure does not eventually return to one (i.e., the sequence instead diverges to infinity or gets stuck in a loop)?
If such evil numbers exist, what’s the smallest example? If they do not exist, why not?
If you’ve heard of this one before, please don’t spoil it for the rest 
3 Likes