Tanya Khovanova's Math Blog

A combinatorial games section? At a math competition? I have never heard of it before. But here it is, at the Lomonosov Tournament. The first problem is from the 2012 Tournament (the link is to a Russian version). The problem is by Alexander Shapovalov. I picked it for its elegance and simplicity.

A rectangular band. You have a paper rectangle of size m by n with grid lines, where both m and n are greater than 1. Two players play the following game. The first player cuts the rectangle along any grid line into two rectangles. The next player picks one of the rectangles and cuts it again along a grid line, and so on. The winner is the player who, after their move, can arrange all the rectangles into a band of width 1. Which player is guaranteed a win regardless of the moves of their partner? Consider two cases.

1. One of the numbers, m or n, is even;
2. Both m and n are odd.

The next problem, by I. Raskin, is from the 2015 Tournament (in Russian). The problem is about fruits, and I know a lot of great puzzles with bananas and oranges, so I immediately got attracted to this one.

The original version had three types of fruit starting with the letters a, b, and c in Russian. They were oranges, bananas, and plums. I reused bananas and replaced oranges with apples, but I got stuck on the letter c. The players in this game eat their fruits, so using cantaloupes seemed like overkill. Plus, I am on a diet, so I decided on cherries.

Fruits. There are a apples, b bananas, and c cherries on the table. Two players play a game where one move consists of eating two different fruits. The person who can’t move loses. Assuming the players use their best strategies, would the first or the second player win in the following cases?

1. a = 1 (the answer might depend on the values of b and c);
2. a = 6, b = 8, c = 10;
3. a = 7, b = 9, c = 15;
4. a = 19, b = 20, c = 21.

The last problem is from the 2012 Tournament (in Russian). It has great sentimental value for me, as it was created by John Conway. It also reminds me of the famous Frobenius (chicken McNugget) problem.

Coin mintage. Once upon a time, in a faraway kingdom, two treasurers were minting coins. They decided to make it into a game, taking turns minting coins. Each turn, the player chooses a particular integral denomination and mints an infinite supply of coins of this denomination. The rules of the game forbid choosing a new denomination that can be paid with the existing coins. The treasurer who is forced to mint a coin of denomination 1 loses.

1. Prove that if the first treasurer starts with denomination 2 or 3, s/he loses.
2. Is it profitable for the first treasurer to start with denomination 4?
3. Is it profitable for the first treasurer to start with denomination 6?
4. Suppose the first treasurer minted coins of denomination 5, and the second treasurer of denomination 6. What is the winning strategy for the first treasurer after that?
5. Suppose the first treasurer minted coins of denomination 5, and the second treasurer of denomination k. Prove that the largest denomination available for minting is 4k − 5.
6. Prove that the first treasurer can win by starting with denomination 5. (Hint: Suppose the second treasurer replied with denomination k, and the first treasurer minted 4k − 5 after that. If this strategy wins, the problem is solved. However, if after that, the second treasurer wins by minting denomination m, then minting denomination 4k − 5 was the wrong move. What was the right move?)

Here is another exciting puzzle posted on Facebook by Konstantin Knop.

Puzzle. Eight glasses of wine are placed in a circle on a round table. Three sages are invited to take the following challenge. In the presence of the first sage, five glasses are filled with good wine and the other three with poisoned wine, indistinguishable from the good wine. After drinking the poisoned wine, the person will die a terrible tormented death. Each sage has to drink one full glass. The first sage is not allowed to give any hints to the other sages, but they can see which glass he chooses before making their own selection. The three sages can agree on their strategy beforehand. What is the strategy to keep them all alive?
An extra question. Does a strategy exist if fewer than eight glasses are placed around the table?

Let’s start with two trivial variations. If there is only one sage, s/he knows which glass to drink. Now, suppose there is only one poisoned glass and any number of sages. If the total number of good glasses is not less than the number of sages, the solution is obvious. The first sage drinks the glass clockwise from the poisoned one, and the other sages continue clockwise.

The next slightly less trivial case involves two sages and two poisoned glasses. If the total number of glasses is at least five, the sages are safe. The reason: there are at least two good glasses in a row. So the sages can agree that the first one drinks a good glass followed clockwise by another good glass. If the total number of glasses is less than 5, there is no reliable strategy, as the reader can check.

The above idea works if the number of sages is S, the number of poisoned glasses is P, and the total number of glasses is T, where T is greater than SP. Then, the strategy is the same since there is a guaranteed continuous stretch of S good glasses.

On the other hand, one can argue that for S and P more than 1, and T = S + P, it is impossible to find a strategy.

Our original problem corresponds to the case S = P = 3, and T = 8. Presumably, the strategy doesn’t exist if S = P = 3, and T < 8. If the 8-glasses problem is difficult, here is a much easier version, corresponding to the case S = 2, P = 3, and T = 6.

An Easier Puzzle. Six glasses of wine are placed in a circle on a round table. Two sages are invited to take the following challenge. In the presence of the first sage, three glasses are filled with good wine and the other three with poisoned wine, indistinguishable from the good wine. After drinking the poisoned wine, the person will die a terrible tormented death. Each sage has to drink one full glass. The first sage is not allowed to give any hints to the other sages, but they can see which glass he chooses before making their own selection. The two sages can agree on their strategy beforehand. What is the strategy to keep them all alive?

I am trying to make a point that, mathematically, the Sleeping Beauty problem is resolved, and the Wikipedia article about it should stop assuming that there is an ongoing debate.

The Sleeping Beauty 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 tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, she is put back to sleep with her memory erased and awakened again on Tuesday and asked the same question. In this case, the experiment stops on Tuesday. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?

Here is the solution. If it is Monday, then the probability that the coin is heads is one half. So the probability of Monday/heads is the same as Monday/tails. If the coin is tails, Sleeping Beauty can’t distinguish between Monday and Tuesday. So the probability of Monday/tails is the same as Tuesday/tails. Thus, the three cases Monday/heads, Monday/tails, and Tuesday/tails are equally probable. It follows that when she is awakened, the probability of heads is one third.

However, there are still people — called halfers — who think that the probability of heads is one half.

But suppose we ask a different question.

Different question. She is awakened one morning. From her point of view, what is the probability that the day is Tuesday?

As I explained before, when she is awakened, the probability of it being Tuesday is one third. Let us calculate what the halfers think. Suppose they think that the probability of the day being Tuesday is x, then the probability of Monday is 1 − x. Let’s calculate the probability of the coin being heads from here. The probability of heads, if today is Tuesday, is zero. The probability of heads, if today is Monday, is 1/2. Therefore, the probability of heads equals 0 · x + (1 − x)/2 = (1 − x)/2. In halfers’ view, the resulting calculation equals 1/2. In other words, (1 − x)/2 = 1/2. It follows that x is zero. Doesn’t make much sense that the probability of the day being Tuesday is zero, does it?

Halfers are wrong. Wikipedia should update the article.

The Sleeping Beauty 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 tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, she is put back to sleep with her memory erased and awakened again on Tuesday and asked the same question. In this case, the experiment stops on Tuesday. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?

This problem is considered controversial. Some people, called halfers, think that when she is awakened, the probability that the coin was heads is one half. Other people, called thirders, think that when she is awakened, the probability that the coin was heads is one third.

I am a thirder, so let me explain my thinking. If it is Monday, then the probability that the coin is heads is one half. So the probability of Monday/heads is the same as Monday/tails. If the coin is tails, Sleeping Beauty can’t distinguish between Monday and Tuesday. So the probability of Monday/tails is the same as Tuesday/tails. Thus, the three cases Monday/heads, Monday/tails, and Tuesday/tails are equally probable, and the answer follows.

This problem is similar to the Monty Hall problem in some ways. The main difference is that The Monty Hall problem stopped being controversial, while Sleeping Beauty problem continues to be. The best argument that helped intuition and led to the resolution of the Monty Hall problem was increasing the number of doors. Similarly, for the Sleeping Beauty problem, we can increase the number of days she is put back to sleep when the coin is tails. Forgive me for the cruelty of this theoretical experiment.

The Sleeping Beauty Variation. 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 tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, the experiment continues for 99 more days. Each day, she is put back to sleep with her memory erased and awakened the next day and asked the same question. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?

In this variation, when she is awakened, she should be almost sure that the coin was tails. I hope it will help halfers feel that, in this case, the probability of heads can’t be one half. For me, the argument is the same as before, making the probability that the coin was heads is 1 over 101.

After I wrote this essay, I discovered that Nick Bostrom made the same argument. Though, for tails, he put Sleeping Beauty to sleep one million and one times, which is about 2,740 years. He increased my one hundred days by several orders of magnitude, amplifying our point. Surely, when Sleeping Beauty awakens, she should be almost certain that the coin was tails. After Sleeping Beauty agrees to so much torture, why is the problem still controversial?

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?

I love Toblerone, but I never paid attention to its logo.

This Swiss chocolate was created in Bern (Berne) more than a hundred years ago. A legend says that Berne’s founder loved hunting and vowed to name the city after the first animal he met on his hunt. The animal happened to be a bear, and so the town was named Berne. The bear became a big deal for the town; you even can find the bear on the town’s flag and coat of arms.

Theodor Tobler, the creator of Toblerone, put the famous local mountain, Matterhorn, in the logo of Toblerone and hid a bear in the image. He obviously loved his country and town.

Tobler was clearly a wordsmith and invented a fascinating name for his chocolate. As Wikipedia explains, the name Toblerone is a portmanteau combining Tobler’s name with the Italian word torrone, which is a type of nougat used in his chocolate. However, Wikipedia doesn’t explain that the word Toblerone also contains a secret: the word BERNE (bear).

After writing this, I couldn’t resist and bought some dark Toblerone chocolate. Now it brings me pleasure in more ways than one.

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.

Here is the current picture of my coauthor, Joel Lewis. I remember him from many years ago when he was a graduate student at MIT. I am glad he kept his big smile.

Back to the subject matter. Joel Lewis made a comment on my recent post, thinking-outside-the-box ideas. He mentioned his two theorems:

The Big Point Theorem. Any three lines intersect at a point, provided that the point is big enough.

The Thick Line Theorem. Any three points lie on the same line, provided that the line is thick enough.

I grew up a purist. Mathematics was about mathematics, not about gender. I personally would never have competed in a math competition exclusively for girls. I would have felt diminished somehow. Furthermore, suppose there were separate math competitions for boys, where girls were not allowed. I would have felt outraged. By symmetry, I should have been outraged by math competitions exclusively for girls.

When I first heard about math competitions for girls, I was uncomfortable. I also noticed that my Eastern European friends shared my feelings, while my other friends did not.

There was a stage in my life when I lived in Princeton for seven years and became friends with Ingrid Daubechies, who is NOT Eastern European. She didn’t share my extreme views, and we argued a lot. Every spring, there was a big conference for Women-in-Mathematics at the Institute for Advanced Study in Princeton. But I was stubborn and completely ignored it. With one exception: when Ingrid gave a lecture there, I went just to hear her talk.

In 2008, I was living in Boston, worrying about money, as I had just resigned from my industry work to return to mathematics. Out of the blue, Ingrid called to offer me a job at that very same Women-in-Mathematics conference. I admire Ingrid and got excited about working with her. More importantly, I needed the money. So I decided to put aside my prejudice and take the job.

Being part of the conference was a revelation. Although most of the two-week conference was spent on mathematics, there were some women-and-math seminars. There, women discussed bullying by advisers and colleagues, impostor syndrome, workplace bias, the two-body problem, and other issues. And guess what? I went through all of that too. I just never realized it and never talked about it.

My biggest regret was that I hadn’t attended the conference earlier. Plus, the conference didn’t feel unfair towards men: all lectures and math seminars were open to the public, and some courageous guys sat in.

What about my symmetry test? What happens if we swap genders? Should there be separate math conferences for men, open to the public? The idea makes me laugh. Women are in the minority in math, and many conferences already feel like conferences for men open to the public. My symmetry test doesn’t quite work.

But, while I saw how helpful the support was for female mathematicians and for me, something still bugs me. Where is the fine line between minority support and unfairness? Let’s look at math clubs for girls. On the surface, there are so many math clubs, so why not have the occasional math club for girls? I can imagine a girl, not me, who would prefer to attend such a club. However, girls’ clubs often have sponsors and are much cheaper to attend than regular clubs. This is unfair to boys whose parents can’t afford a regular club. It also becomes counterproductive for girls. What if some girls go to such a club, not because they need a special environment but because it is a cheaper club? They are missing out on the fun of learning math together with boys. (Trust me, I know!) So, I am not sure where that line is.

I am older and wiser now. I do not run away from events organized for women in math. I think lunches and dinners for women in math are great. They help female mathematicians find mentors, build networks, and stay in mathematics.

What about my original question: Should there be separate math competitions for girls? In a truly equal society, math competitions should be for everyone. And, though I do not actively oppose girls’ competitions anymore, I hope the need for them will die out in my lifetime.

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?