Tanya Khovanova's Math Blog

by Tanya Khovanova and Alexey Radul

We already blogged about the Sleeping beauty problem three times: The Sleeping Beauty Problem, Sleeping Beauty Meets Monty Hall, and Sleeping Beauty and Mondays. The posts were more than ten years ago, but the mathematical community seems to continue being stuck on this problem. So we come back to it.

Problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or not. If the coin was tails, however, she is put back to sleep with her memory erased, awakened on Tuesday and asked the same question again. She knows the protocol. She is awakened one morning: What is her probability that the coin was heads?

Let’s raise the stakes a little bit. Suppose a prize of $1K is set aside for her correct guess of a flip. What should be her strategy?

The problem is ambiguous. We didn’t tell you how the prizes are awarded. We see several reasonable scenarios:

1. Sleeping Beauty gets the prize if she is right on Monday.
2. Sleeping Beauty gets the prize if she is right on Tuesday.
3. Sleeping Beauty gets the prize for every correct answer.
4. Sleeping Beauty gets the prize if she guesses correctly all the questions she is asked.
5. Sleeping Beauty gets the prize if she is right at least once.
6. Sleeping Beauty gets the prize if she is right for a randomly chosen answer. This means, if the coin is heads, she get the prize if she is right on Monday. If the coin is tails, then one of her two answers is chosen randomly, and she gets the prize if she is correct.

Because of selective amnesia, she can’t distinguish between her awakenings, thus her strategy has to be the same at every awakening. That is, she should say heads with probability p. The exact number depends on the scenario:

1. First scenario: It doesn’t matter what value of p she chooses. With a probability 1/2, she wins one grand.
2. Second scenario: She should choose p = 0. Her best strategy is to always say tails. With a probability 1/2 (when the coin is tails), she wins one grand.
3. Third scenario: She should choose p = 0. Her best strategy is to always say tails. With a probability 1/2, she wins two grand.
4. Fourth scenario: p = 0 or p = 1. Her best strategy is to stick with the same answer all the time; and it doesn’t matter what answer she chooses. With probability 1/2, she wins one grand.
5. Fifth scenario: She should choose p = 1/2. Her best strategy is to flip a coin herself each time and say tails with probability of 1/2. This way, her chances to win one grand are 5/8.
6. Sixth scenario: It doesn’t matter what value of p she chooses. With a probability 1/2, she wins one grand.

We see that though she is asked to guess the outcome of the coin flip and is rewarded for guessing correctly, her strategy is not to try to maximize the probability of guessing correctly each time. The strategy depends on the reward protocol.

We see that in the first and the sixth scenario, she gets one guess per coin flip. Not surprisingly, it doesn’t matter what she chooses to do. The classic Sleeping Beauty problem corresponds to the third scenario. If she wants to improve her chances per guess, she should favor tails.

Let’s look at the following variation.

Problem. Suppose Sleeping Beauty’s goal is to guess right once, but if she guesses right on Monday, she wins and is not put back to sleep. If she guesses wrong on Monday and the coin was tails, she is put back to sleep with he memory erased. That is, she is given a second chance. What’s the right strategy in this case?

As her memory is erased, the only strategy is to do the same thing each time she is awakened. That is to guess heads with probability p. Thus, she guesses correctly at least once with probability p/2 + (1–p)/2 + p(1–p)/2. We see that whatever strategy she chooses, she guesses with probability one half on Monday. She gets an additional chance of p(1–p)/2 to get a correct guess on Tuesday. Her worst strategy is to always guess tails or heads. Her best strategy is to flip a fair coin each time. This way, she has an additional probability of 1/8 to win on Tuesday.

Here is a question to our readers, for the best strategy above, what is her probability on waking that the coin is actually heads? Here is the problem more formally.

Problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thought the coin was heads or not. Sleeping Beauty answers by flipping a fair coin. If she guesses correctly, or if the Sunday coin was heads, the experiment ends. If the Sunday coin was tails and different from her guess, she is put back to sleep with her memory erased, awakened on Tuesday, and asked the same question again. She knows the protocol. She is awakened one morning: What is her probability that the Sunday coin was heads?

There are many cute math problems that use the trivial fact announced in the title. For example, I recently posted the following problem from the 43rd Tournament of Towns.

Problem. Find the largest number n such that for any prime number p greater than 2 and less than n, the difference n − p is also a prime number.

Solution. Prime numbers 3, 5, and 7 have different remainders modulo 3. Thus, for any n, one of the numbers n − 3, n − 5, or n − 7 is divisible by 3. If n > 10, that number that is divisible by 3 is also greater than 3, thus, making it composite. Therefore, the answer to this problem is not greater than 10. Number 10 works, thus, the answer is 10.

Here is another problem using the fact that 3, 5, and 7 have different remainders when divided by 3.

Problem. Find the maximum integer n, such that for any prime p, where p < n, the number n + 2p is prime.

Recently, I stumbled upon three lovely logic puzzles, while scrolling Facebook for news from the Russia-Ukraine war. I will start with an easy puzzle.

Puzzle. A traveler got to an island, where each resident either always tells the truth or always lies. A hundred islanders stood in a circle facing the center, and each told the traveler whether their neighbor to the right was a truth-teller. Based on these statements, the traveler was able to clearly determine how many times he had been lied to. Can you do the same?

In the next puzzle, there is another island where people are either truth-tellers or normal. There are three questions that increase in difficulty.

Puzzle. You are on an island with 65 inhabitants. You know that 63 inhabitants are truth-tellers who always tell the truth, and the other 2 are normal, who can either lie or tell the truth. You are allowed one type of question, “Are all the people on this list truth-tellers?” This question requires a list, which you can create yourself. Moreover, you can have as many different lists as you want. You can pose this question to any islander any number of times. Your goal is to find the two normal people. The easy task is to do it in 30 questions. The medium task is to do it in 14 questions. The hard task is to figure out whether it is possible to do it in fewer than 14 questions.

Here is the last puzzle.

Puzzle. You got to an island with 999 inhabitants. The island’s governor tells you, “Each of us is either a truth-teller who always tells the truth, or a liar who always lies. ” You go around the island asking each person the same question, “How many liars are on the island?” You get the following replies.
First person, the governor: “There is at least one liar on the island.”
The second person: “There are at least two liars on the island.”
This continues progressively until the 999th person says: “There are at least 999 liars on the island.”
What can you tell about the number of liars and truth-tellers on this island?

I recently wrote an essay, Thinking Inside and Outside the Box, which starts with a famous nine-dots puzzle that kicked off the expression: thinking outside the box. Here is another puzzle with the same nine-dots setup.

Puzzle. What is the smallest number of squares needed to ensure that each dot is in its own region?

Usually, people who try to solve this puzzle come up with the following four-squares solution.

As with the classic nine-dots puzzle, they imagine that the dots are on a grid and try to build squares with sides parallel to the grid lines. What would be the outside-the-box idea? The sides of the squares would not need to be parallel to the grid. This way, we can solve the puzzle with three squares.

One of my MathRoots students offered a different and awesome solution also using three squares.

Problem. Find the largest number n such that for any prime number p greater than 2 and less than n, the difference n − p is also a prime number.

The most famous thinking-outside-the-box puzzle is the Nine-Dots puzzle. This puzzle probably started the expression, “To think outside the box”. Here is the puzzle.

Puzzle. Without lifting the pencil off the paper, connect the nine dots by drawing four straight continuous lines that pass through all the dots.

Most people attempt something similar to the picture below and fail to connect all the dots.

They try to connect the dots with line segments that fit inside the square box around the dots, mentally restricting themselves to solutions that are literally inside the box.

To get to the correct solution, the line segments should be drawn outside this imaginary box.

Do you think that four line segments is the best you can do? Jason Rosenhouse showed me a solution for this puzzle that requires only three lines. Here, the outside-the-box idea is to use the thickness of the dots.

This and many other examples of thinking outside the box are included in my paper aptly titled Thinking Inside and Outside the Box and published in the G4G12 Exchange book.

A section of this paper is devoted to my students, who sometimes give unexpected and inventive solutions to famous puzzles. Here is an example of such a puzzle and such solutions that aren’t in the paper because I collected them after the paper was published.

Puzzle. Three men were in a boat. It capsized, but only two got their hair wet. Why?

The standard answer is the following: One man was bald.

Lucky for me, my creative students suggested tons of other solutions. For example,

• One man was wearing a waterproof helmet.
• The boat capsized on land, and two men had their hair already wet.

My favorite example, however, is the following.

• One man didn’t have a head.

I love knights-and-knaves puzzles: where knights always tell the truth, and knaves always lie. The following puzzle has a new type of person: a sophist. A sophist only makes statements that, standing in their place, neither a truth-teller nor a liar could make. For example, standing next to a liar, a sophist might say, “We are both liars.” Think about it. If the sophist was a truth-teller, then the statement would have been a lie, thus creating a contradiction. If the sophist was a liar, the statement would be true, again creating a contradiction.

Here is the puzzle with sophists. And by the way, this one is intended for sixth graders.

Puzzle. You are on an island inhabited by knights, knaves, and sophists. Once upon a time, a sophist made the following statements about the island’s inhabitants:
1. There are exactly 25 liars on this island.
2. There are exactly 26 truth-tellers on this island.
3. The number of sophists on this island is no less than the number of truth-tellers.
How many inhabitants were on the island once upon that time?

I love this new sophist character in logic puzzles, but I have no clue why they are called sophists. Can anyone explain this to me?

After reading my post, Shapovalov’s Gnomes, Grant, one of my readers, directed me to the Brick puzzle from Section 2.3 of Xinfeng Zhou’s A Practical Guide to Quantitative Finance Interviews.

Puzzle. Can you pack 53 bricks with dimensions 1-by-1-by-4 into a 6-by-6-by-6 box?

The solution in Zhou’s book has some flaws. So I am posting my own solution here.

Solution. We start with a sanity check. The box contains 216 unit cube cells, and 53 bricks would take up 212 cells. So there is no contradiction with the volume. We need to look at something else.
Let’s divide the box into 27 smaller 2-by-2-by-2 boxes and color the smaller boxes in a checkerboard manner. We get 13 boxes of one color, say white, and 14 boxes of another color, say black. Whichever way we place a brick inside the original box, it has to cover 2 white cells and 2 black cells. But we have a total of 104 white cells, which is only enough for 52 bricks.

Alexander Gribalko designed a new coin problem, two versions of which appeared at the 43rd Tournament of the Towns. I will start with the easier version.

Problem. Alice and Bob found eleven identical-looking coins; four of them are fake. All real coins weigh the same. All fake coins weigh the same but are lighter than the real ones. Alice offered Bob four specific coins. Before agreeing to take them, Bob wants to ensure they are all real. Can he do so by only using the balance scale twice? He can use any of the eleven coins for weighing purposes.

Surprisingly, the more difficult version has fewer coins.

Problem. Alice and Bob found eight identical-looking coins; three of them are fake. All real coins weigh the same. All fake coins weigh the same but are lighter than the real ones. Alice offered Bob three specific coins. Before agreeing to take them, Bob wants to ensure they are all real. Can he do so by only using the balance scale twice? He can use any of the eight coins for weighing purposes.

I recently posted a cute Shapovalov’s puzzle about gnomes. Here is another easier gnome puzzle, also by Alexander Shapovalov.

Puzzle. All gnomes are knights or knaves: knights always tell the truth, and knaves always lie. There is a gnome on every cell of a 4 by 4 chessboard. It is known that both knights and knaves are present in this group. Every gnome states, “Among my neighbors, the number of knaves is the same as the number of knights”. How many knaves are there, if by neighbors they mean orthogonally adjacent gnomes?

The next gnome puzzle has a different author, Alexander Gribalko. Gnomes in this puzzle are not knights or knaves but rather friendly and polite beings.

Puzzle. Nine gnomes repeated the following procedure three times. They arranged themselves on a 3 by 3 chessboard with one gnome per cell and greeted all their orthogonal neighbors. Prove that not all pairs of gnomes greeted each other.