Tanya Khovanova's Math Blog

Here is the famous Sleeping Beauty problem.

Puzzle. Sleeping Beauty agrees to take part in an experiment. On Sunday, she is put to sleep, and a fair coin is tossed. If it lands heads, she is awakened on Monday only. If it lands tails, she is awakened on both Monday and Tuesday. After each awakening, she is put back to sleep and given a drug that erases her memory of that awakening. She knows the rules of the experiment, but during each awakening she cannot tell which day it is or whether she has been awakened before. Each time, she is asked: From her point of view, what is the probability that the coin landed heads?

The answer is 1/3. I won’t repeat the details here; explanations are easy to find. Yet plenty of people insist that the answer is 1/2. Apparently, if enough people argue with the correct answer, a problem gets promoted to a paradox.

I tried to convince the halfers. I wrote many essays, some of them with Alexey Radul. Here is the list in chronological order.

• The Sleeping Beauty Problem (with Alexey Radul) — August 25, 2011.
• Sleeping Beauty Meets Monty Hall — August 27, 2011.
• Sleeping Beauty and Mondays (with Alexey Radul) — August 27, 2011.
• Sleeping Beauty Wants the Prize Money (with Alexey Radul) — August 30, 2022.
• The Sleeping Beauty Problem Amplified — August 31, 2022.
• Sleeping Beauty and Tuesdays — September 1, 2022.

Eventually, I got tired and stopped fighting. I decided to wait, hoping that the correct answer would catch on.

More than 15 years have passed since I started advocating for the correct answer. Yesterday, I revisited the Wikipedia page. People are still arguing. So I asked ChatGPT Pro for the answer. It replied: 1/3. Is ChatGPT’s authority enough to turn the tide?

In 2016, I posted a cute puzzle, An Asteroid Walk, on my blog. Here it is.

Puzzle. Seven astronauts landed on a small spherical asteroid. They wanted to explore it and walked in different directions starting from the same location. All used the same walking algorithm: walk x kilometers forward, turn 90 degrees left and walk another x kilometers, turn 90 degrees left again and walk the last x kilometers. The value of x was different for different astronauts and was one of 30, 40, 50, 60, 70, 80, and 90.

All but one astronaut finished in the same location. What was the value of x for the astronaut who finished alone? What is the size of the asteroid? To be precise, by size, I mean the great-circle circumference.

I never posted the answer. This post had sat on my to-do list for more than ten years, and I finally got around to it. The answer is surprising: the value used by the lonely astronaut is uniquely determined, but the size of the asteroid is not.

Let c be the circumference of the asteroid, and call the astronauts’ starting point the North Pole. Walking straight ahead means following a great circle. Write r for the remainder of x after removing complete laps, so that 0 ≤ r < c. A complete lap returns an astronaut to the same position with the same heading, so only r matters. Moreover, if we reverse the initial heading and replace r by c − r, the astronaut visits the same turning points and reaches the same endpoint.

Suppose each leg is a quarter of a circumference. The astronaut walks from the North Pole to the equator, turns left and follows the equator for a quarter-circle, then turns left again and returns to the North Pole. The route forms a spherical triangle with three right angles. By symmetry, three-quarters of a circumference per leg also brings the astronaut home. An integer number of complete laps per leg obviously works, too.

Half a circumference behaves differently. Each leg takes the astronaut to the antipode of the previous position, regardless of the turns. After three such legs, the astronaut is at the South Pole.

Now try a circumference of 40 kilometers. The astronauts with x = 40 and 80 make whole laps on each leg. Those with x = 30, 50, 70, and 90 have remainders of 10 or 30 kilometers: a quarter-circle or a three-quarter-circle. All six return to the North Pole. The astronaut with x = 60 has a remainder of 20 kilometers, or half a circumference, and finishes alone at the South Pole. This is the most common answer.

But nothing in the puzzle limits the number of laps an astronaut can make. What happens if the circumference is 40/3 kilometers? A quarter of this circumference is 10/3 kilometers. Measured in quarter-circles, the seven leg lengths are now 9, 12, 15, 18, 21, 24, and 27. Only 18 is congruent to 2 modulo 4. Once again, the 60-kilometer astronaut finishes at the South Pole, and everyone else returns to the North Pole.

More generally, every circumference of the following form works:

c = 40/(2m + 1) kilometers, where m = 0, 1, 2, ….

Indeed, a quarter of the circumference is then 10/(2m + 1) kilometers. If x = 10n, the leg contains n(2m + 1) quarter-circles. Because 2m + 1 is odd, this number is divisible by 4 when n is 4 or 8, is congruent to 2 modulo 4 when n = 6, and is odd for the remaining four values of n. Thus the 60-kilometer astronaut alone travels a half-circle after completing some number of full laps.

Are these all the solutions? And must the six astronauts finish where they started? Yes and yes. Unfortunately, the proof is much less charming than the answer: it is a calculation with trigonometric polynomials. This seems like an appropriate part to outsource to AI.

I used to write a review and list math-related puzzles for each MIT Mystery Hunt. Recently, my team, Death and Mayhem, started a new tradition of adding descriptions to the puzzle list. This makes it easy to find puzzles related to math. Nowadays AI can also help. So I plan to stop writing hunt reviews.

So consider this a farewell to my annual MIT Mystery Hunt reviews. I will just mention some puzzles that my team loved. I will provide the official descriptions where available and perhaps add a comment of my own.

• Urban Angst — Seven pictures. This puzzle might be especially enjoyed for people connected to MIT.
• Shapes — Metamatching puzzle. People found this puzzle satisfying.
• Minute Minute Cryptic — An innocuous-looking cryptic crossword. Great for cryptic lovers.
• Had — This puzzle doesn’t have a description, but it got the largest number of positive comments.
• Multidimensional Crossword — This puzzle has no listed description, but it was praised for its elegance.
• Setting Boundaries — Again, no description. This is a logic puzzle, and several people loved it.
• Dichotomies — This is a metapuzzle with five bite-sized logic/math five feeder puzzles.
• Can you really call it a crossword if… — This is another meta with six minifeeders.

I have finally become a queen — though only in a research paper. In Immensely Questionable Tests, I am Queen Tanya, and my ten PRIMES STEP student coauthors are my sages.

The project began with a probability puzzle from Mathematical Puzzles and Curiosities, my book with Ivo David and Yogev Shpilman. Here I present an equivalent version, without probabilities, to match our project.

Puzzle. How many correct answer choices are there?

a) 1    b) 1    c) 2    d) 2

The intended answer is 2: exactly two choices say 2. So far, so good. Now erase one of the 1s. How many correct answer choices are among a) 1, b) 2, and c) 2?

Now 1 appears once and 2 appears twice. Either value can be an answer. But calling all three choices correct would require the answer to be 3. What is going on here?

We restrict the answer choices to positive integers. We call a value m valid if it occurs exactly m times among the choices. Now we can discuss valid answers without getting into paradoxes.

Our first paper Self-Referential Tests counts tests with valid answers as a function of the cost, defined as the sum of all test options. The paper answers many questions related to different types of tests. For example, what is the cheapest test with k distinct valid values? The cheapest such test uses one 1, two 2s, and so on, through k copies of k. Its cost is 1² + 2² + … + k². For three distinct valid values, the cheapest test is 1, 2, 2, 3, 3, 3, costing 14.

Our second paper, Immensely Questionable Tests, mentioned at the very start of this essay, deals with the paradoxical nature of such tests.

For example, consider a test with these options:

1, 2, 2, 3, 3, 3, 3, 4, 4, 4.

The valid values are 1 and 2, accounting for three options. This tempts us to say that the correct answer is 3. But there are four threes on the test, suggesting that the correct answer should be 4 instead. And there are three fours, taking us back to 3. We are going in circles! It is surprisingly difficult to decide which answers should be called correct. We were not able to agree on the answer. So we turned our confusion into a story about a queen and her sages. Ironically, even in a fairy tale, I keep teaching people mathematics.

Here is an old puzzle that I have used in my classes for years.

Puzzle. Two people take turns placing quarters on a round table so that the quarters fit on the table and no two quarters overlap. The person who can’t move loses. Who has a winning strategy?

It is easy to see that the first player always wins by using the symmetry of the table. On the first move, the first player puts the first coin directly in the center of the table. For each subsequent move, the first player places a coin in the spot that is centrally symmetric to where the coin was placed on the previous move.

This year, something unusual happened. It seems I have a couple of true mathematicians among my STEP students. They added the following detail.

The first player wins, except when the table is smaller than the quarter.

Here is another puzzle from Konstantin Knop.

Puzzle. A town has 801 residents, and they vote on 9 different questions. On each question, everyone votes either “Yes” or “No”, and the majority wins. A resident is happy with the result of a question if the final decision matches their own vote. We will call a resident satisfied if they are happy with at least 5 of the 9 final decisions. What is the smallest possible number of satisfied residents?

I leave the solution to the reader, but I want to recast the puzzle in the language of coding theory.

Write each ballot as a string of 9 zeros and ones. For example, a 1 can mean “Yes” and a 0 can mean “No”. A ballot is then a point in the 9-dimensional Hamming cube. The final result is another string of 9 zeros and ones, obtained by taking the majority vote in each coordinate.

The Hamming distance between two strings is the number of positions in which they differ. A resident is satisfied exactly when their ballot has Hamming distance at most 4 from the final result. So the puzzle becomes:

Puzzle. Given 801 binary strings of length 9, how few can lie within Hamming distance 4 of their coordinate-by-coordinate majority?

I promised not to give away the solution, but I can’t resist one more observation: we can flip zeros and ones in any coordinate without changing the problem. Therefore, without loss of generality, we may assume that the final result is 111111111. Then we can restate the puzzle again.

Puzzle. Given 801 binary strings of length 9 such that every coordinate contains at least 401 ones, how few of the strings can have at least five ones?

Vouchers are supposed to make shopping cheaper, right? Apparently, the shopkeeper in the following puzzle didn’t know. By the way, the puzzle is from Mathematical Puzzles and Curiosities, my book with Ivo David and Yogev Shpilman.

Puzzle. A shop sells vouchers with price tags of 1, 2, 3, … dollars. There is exactly one voucher of each price. Buying the voucher tagged N makes your very next voucher cost N times its own price tag. Each multiplier applies only to the next purchase; the multipliers do not accumulate. Your first voucher costs exactly its price tag.

You have 26 dollars. What is the largest number of vouchers you can buy?

For example, buying the vouchers tagged 1, 2, 3, and 4, in that order, costs 1 + 1 · 2 + 2 · 3 + 3 · 4 = 21 dollars.

I will leave the 26-dollar puzzle to you. Meanwhile, suppose you have already chosen a finite set of vouchers and must buy all of them. In what order should you buy them to spend as little as possible? And what order makes you spend as much as possible?

My PRIMES STEP students and I chose this puzzle as the starting point in our research. We got many results and wrote a paper From a Voucher Puzzle to Extremal Sums of Adjacent Products, available on arXiv.

Here is the coolest part: the cheapest and the most expensive purchase orders depend only on the ranks of the price tags. They work for any finite set of distinct positive integers. You need to know which price is smallest, second-smallest, and so on. You do not need to know what the actual prices are.

Let us play with four vouchers. For price tags 1, 2, 3, and 4, the cheapest orders are 3, 2, 1, 4 and 2, 3, 1, 4 for the total cost of 15 dollars. The most expensive orders are 2, 4, 3, 1 and 3, 4, 2, 1 for the total cost of 25 dollars.

Now suppose the shop changes the price tags to 2, 7, 10, and 100. These numbers are much less evenly spaced. It looks as though we should start over with new calculations. We do not have to. We simply replace the smallest old number by the smallest new number, the second-smallest by the second-smallest, and so on. The first cheapest order becomes 10, 7, 2, 100 for the total cost of 10 + 70 + 14 + 200 = 294 dollars, and the first most expensive order becomes 7, 100, 10, 2 for the total cost of 7 + 700 + 1000 + 20 = 1,727 dollars.

We also studied two relatives of the voucher cost. The pairwise cost is what you pay if the first voucher is free but still applies its multiplier to the next purchase: just add the products of neighboring price tags. For the order 1, 2, 3, 4, this gives 1 · 2 + 2 · 3 + 3 · 4 = 20 dollars. For the loop cost, arrange the price tags in a circle and include the product of the last and first tags too, giving 20 + 4 · 1 = 24 dollars. Both variations have recipes for minimizing and maximizing the cost: and again the result depends only on the ranks of the price tags.

In all three costs, we have the same intuition. To maximize the cost, we want to cluster the most expensive vouchers together, creating large products of neighboring price tags. For the smallest cost, we want to put the largest price tags next to the smallest ones.

There is a particularly tidy order maximizing all three costs. Number the vouchers by rank, starting with 1 for the cheapest. Take the even ranks in increasing order, followed by the odd ranks in decreasing order. For eight vouchers, this gives 2, 4, 6, 8, 7, 5, 3, 1. These are ranks, not prices: all eight actual price tags could be odd. The minimizing orders also use only ranks, although they weave the large and small numbers together differently.

For more examples, and the exact results, check our paper From a Voucher Puzzle to Extremal Sums of Adjacent Products.

Here is a famous riddle.

Puzzle. A police officer saw a truck driver going the wrong way down a one-way street, but didn’t try to stop him. Why?

The standard answer: the truck driver was walking.

My students are usually very inventive, but this time they came up with only two alternative answers worth mentioning:

• The truck was a fire truck rushing to a fire.
• It was Halloween, and the police officer was just a kid dressed as one.

I am sure there are more cute ways to explain the situation. Do you have one?

I like pets, but, for various reasons, I can’t have one. So I flirt with other people’s pets. There is a black cat across the road who likes sitting in my driveway. So I had to buy a new car with a backup camera to make sure the cat is safe. As you can imagine, I couldn’t skip this problem about cats posted by Konstantin Knop on Facebook.

Puzzle. One cat eats one stick of sausage in 27 minutes. You have four identical sticks of sausage and five cats. Using only the cats and the sausages, measure exactly one minute.
All the cats eat at the same constant rate, and all the sausage sticks are identical. You may measure time intervals only between moments when cats finish sausage sticks. At each such moment, you may redistribute the cats among the remaining sausage sticks.

For the last homework of the year, I gave my students a killer puzzle—literally.

Puzzle. A mysterious man kidnaps people, takes them to his cabin, and offers each victim two identical-looking pills. He claims that one pill is poisonous and the other is harmless. The victim chooses one pill, swallows it with water, and dies, while the killer consumes the other pill and survives. How does the killer manage to get the safe pill every time?

The official answer was that neither pill was poisoned. The poison was in the water.

Some students suggested that the poison becomes active only when mixed with water. I did not give full credit for this solution: saliva contains water, so the proposed chemistry is off.

Naturally, my students suggested other solutions. Here are two good ones, which are similar to each other:

• Both pills are poisonous, but the killer has taken an antidote.
• Both pills are poisonous, but the killer has somehow built up a resistance to the poison.

And here is an ingenious and highly specific answer from a student:

The killer kidnaps only people with deadly peanut allergies. He knows who they are because he is the town’s allergy tester, and both pills contain peanut butter.

ChatGPT offered a solution exploiting the wording: perhaps the victims die after swallowing the pill—but many decades later, of perfectly natural causes.

I feel there should be some more interesting solutions. Any takers?