Tanya Khovanova's Math Blog

The Fomenko drawing on the left is from the original Russian edition of Homotopic Topology by Fuks, Fomenko and Gutenmacher. Dmitry Fuchs signed this book for me after my success in the USSR Math Olympiad when I was in the 9th grade. For many years I didn’t know what the picture meant and was mystified by it. Now the book has been republished with explanations and is available in English at a non-affordable price. You can find this picture and many other Fomenko drawings in his book called Mathematical Impressions, which is affordable, although the comments accompanying the illustrations are confusing. So I have my own explanation for the meaning of this illustration.

The bracelet is made out of shells. Each shell is a hollow cone whose vertex is glued to a point on the rim of the cone’s opening, thus giving each hollow cone its own handle. In a part of another drawing (at left), Fomenko shows how the bracelet is built by an army of tiny slaves. First they build the shells and then they connect them together.

How do they connect the shells to each other? The rim of the next shell is glued to the handle of the previous shell. Let me remind you that a straight line connecting a point on the rim to the vertex of a cone is called a generatrix. Imagine a generatrix that connects a vertex of a cone to the point on the rim to which this vertex is glued. This generatrix becomes a circle in a shell, which I call the handle circle. So the rim of the next shell is glued to the handle circle of the previous shell.

Now consider the fundamental group of a shell. The rim can be contracted to the handle circle. Moreover, the cone itself can be contracted to the handle circle. If we glue several shells together, the result is contractible to the handle circle of the last shell.

Now let’s go back to the bracelet. The shells become smaller in both directions and end in two points. The front end point is more interesting topologically than the one in back. Every point other than the front end has a contractible neighborhood, while the front end point does not. Or in scientific terms: The bracelet gives an example of a space with a point at which the space is “1-lc” but with no open neighborhoods on which every (Cech) 1-cycle bounds.

My son Sergei invented the following game a couple of years ago. Two people, Alice and Bob, agree on a number, say, four. Alice takes a clean Rubik’s cube and secretly makes four moves. Bob gets the resulting cube and has to rotate it to the initial state in not more than four moves. Bob doesn’t need to retrace Alice’s moves. He just needs to find a short path back, preferably the shortest one. If he is successful, he gets a point and then it is Alice’s turn.

If they are experienced at solving Rubik’s cube, they can increase the difficulty and play this game with five or six moves.

By the way, how many moves do you need to solve any position on a Rubik’s cube if you know the optimal way? The cube is so complicated that people can’t always know the optimal way. They think that God can, so they called the diameter of the set of all possible Rubik’s cube positions, God’s Number. It was recently proven that God’s Number is 20. If Alice and Bob can increase the difficulty level to 20, that would mean that they can find the shortest path back to the initial state from any position of the cube, or, in short, that they would master God’s algorithm.

One hundred people play the following game. Their names are written on pieces of paper and put into 100 labeled boxes at random. Each box is labeled with a number from 1 to 100 and one name has been placed inside each box. The boxes are placed on a table in a separate room. The players go into the room one by one and each has to open 99 boxes one after another. After each player finishes and leaves the room, the boxes are closed again. The players are not allowed to communicate with each other in any way, although they have been given one day before the event to discuss their strategies. They only win if every one of the one hundred players avoids opening the box with his or her own name. What is the optimal strategy?

Let me first discuss a simpler version of the game. Each player has to open exactly one box and they win if each one of them finds their name. After each player finishes and leaves the room, the boxes are closed again and the room is re-set.

If all of them decide to open box number 42, they are guaranteed to lose. They can try to open random boxes, then they win with probability (1/100)¹⁰⁰. Can they use a joint strategy that is better than random?

Yes, they can. Clearly, two people shouldn’t open the same box. So on the day before, if each agrees to open a box with a different assigned number, their probability to win is one over 100!. I leave it to my readers to prove that this is the best strategy.

What is the difference between this problem and the original problem? Isn’t choosing the last box the same as choosing the first? Aha! When they open 99 boxes they see the names, so they can use this information as part of their strategy.

I hope that this new version is so intriguing that you will start solving this puzzle right away.

* * *

Decimals have a point.

* * *

During the show “Are You Smarter Than a 5th Grader?” the following question was asked:

What is superfluous in the following list: a carrot, an onion, a potato, a Lexus?

A smart 5th grader answered: a carrot, an onion, and a potato.

* * *

If you buy 3 DVDs for the price of 4, you will get one more as a bonus.

* * *

Only yesterday, today was tomorrow.

* * *

By definition, one divided by zero is undefined.

* * *

Finally artificial intelligence has caught up with humans: when filling out electronic forms, many humans need several tries to prove they are not robots.

* * *

Be back in 5 minutes. If I am late, reread this sms.

* * *

— We’ll split the money 50-50.
— I want 70.
— Okay, 70-70!

I recently published my new favorite math problem:

A deck of 36 playing cards (four suits of nine cards each) lies in front of a psychic with their faces down. The psychic names the suit of the upper card; after that the card is turned over and shown to him. Then the psychic names the suit of the next card, and so on. The psychic’s goal is to guess the suit correctly as many times as possible.
The backs of the cards are asymmetric, so each card can be placed in the deck in two ways, and the psychic can see which way the top card is oriented. The psychic’s assistant knows the order of the cards in the deck; he is not allowed to change the order, but he may orient any card in either of the two ways.
Is it possible for the psychic to make arrangements with his assistant in advance, before the latter learns the order of the cards, so as to ensure that the suits of at least (a) 19 cards, (b) 23 cards will be guessed correctly?
If you devise a guessing strategy for another number of cards greater than 19, explain that too.

If the psychic is only allowed to look at the backs of the cards, then the amount of transmitted information is 2³⁶, which is the same amount of information as suits for 18 cards. This number of guesses is achievable: the backs of every two cards can clue in the suit of the second card in the pair. This way the psychic can guess the suits of all even-numbered cards in the deck. So the problem is to improve on that. Using the info from the cards that the psychic is permitted to turn over can help too.

The problem is from the book Moscow Mathematical Olympiads, 2000-2005. The book and Russian blog discussions provide many different ideas on how to guess more than half of the deck.

Here is the list of ideas.

Idea 1. Counting cards. If you count cards you will know the suits of the last cards.

Idea 2. Trading. As we discussed before, the psychic can correctly guess the suits of even-numbered cards. By randomly guessing the odd-numbered cards she can correctly guess on average the suits of 4.5 additional cards. Unfortunately, this is not guaranteed. But wait. What if we trade the knowledge of the second card’s suit for the majority suit among odd-numbered cards?

Idea 3. Three cards. Suppose we have three cards. Three bits can provide the following knowledge: the majority color, plus the suit of the first and of the second cards in the majority color. Thus, three bits of information will allow the psychic to guess the suits of two cards out of three.

Idea 4. Which card. Suppose the assistant signals the suits of even-numbered cards. With no loss, the psychic can guess the even-numbered card and repeat the same suit for the next card. If this is the plan, the assistant can choose which of the two cards to describe. Which card of the two matches the psychic’s guess provides an additional bit of information.

Idea 5. Surprise. Suppose we have a strategy to inform the psychic about some cards. Suppose the assistant deliberately fails on one of the cards. Then the index of this card provides info to the psychic.

I leave it to my readers to use these ideas to find the solution for 19, 23, 24 and maybe even for 26 cards.

Imagine a slice of buttered white bread with a heap of sugar on top. That was my favorite lunch when I was a kid. My mom was working very hard, I was the oldest sister, and this was what I would make for myself almost every day.

Later someone told me that sugar is brain food. I believed that sugar and chocolate helped me do mathematics, so my love for sugar got theoretical support. I finally figured out the source of this love when my first son was born. To teach my son to stop requesting milk at night, my mother pushed me to give him sugar-water instead. At that moment, I realized that I developed my love of sugar with my mother’s milk. Or, more precisely, instead of my mother’s milk.

Now there is more and more evidence that the love of my life is a mistake. See for example Is Sugar Toxic?. Will I ever be able to break my oldest bad habit, the one I developed before I can remember myself doing it?

This is how my ex-husband Joseph Bernstein used to start his courses in representation theory.

Suppose there is a four-armed dragon on every face of a cube. Each dragon has a bowl of kasha in front of him. Dragons are very greedy, so instead of eating their own kasha they try to steal kasha from their neighbors. Every minute every dragon extends four arms to the neighboring cube’s faces and tries to get the kasha from the bowls there. As four arms are fighting for every bowl of kasha, each arm manages to steal one-fourth of what is in the bowl. Thus each dragon steals one-fourth of of the kasha of each of his neighbors, while all of his own kasha is stolen too. Given the initial amounts of kasha in every bowl, what is the asymptotic behavior of the amounts of kasha?

You might ask how this relates to representation theory. First, it relates to linear algebra. We can consider the amounts of kasha as a six-dimensional vector space and the stealing process as a linear operator. As mathematicians, we can easily assume that a negative amount of kasha is allowed.

Now to representation theory. The group of rotations of the cube naturally acts on the 6-dimensional vector space of kashas. And the stealing operator is an intertwining operator of this representation. Now for a spoiler alert: I’m about to finish the solution, so stop here if you want to try it on your own.

The intertwining operator acts as a scalar on irreducible representations of the group. Thus we should decompose our representation into irreducible ones. The group has five irreducible representations with dimensions 1, 1, 2, 3, and 3.

We can decompose the kasha into the following three representations:

• One-dimensional. Every dragon has the same amounts of kasha. The stealing operator acts as identity.
• Three-dimensional. Dragons on opposite sides have the opposite amount of kasha. The stealing operator acts as zero.
• Two-dimensional. Dragons on opposite sides have the same amount of kasha and the total amount of kasha is zero. The stealing operator acts as −1/2.

We see that asymptotically every dragon will have the same amount of kasha.

Now it is your turn to use this method to solve a similar problem, where there are n dragons sitting on the sides of an n-gon. Each dragon has two arms, and steals half of the kasha from his neighbors. Hey, wait a minute! Why dragons? There are people around the table stealing each other’s kasha. But the question is still the same: What is the asymptotic behavior of the amounts of kasha?

Students should use a different strategy for the AIME than for the AMC. So students who are approaching the AIME for the first time need to question the habits they have developed after years of doing multiple choice tests. Here are some suggestions.

Checking. I’ve noticed that the accuracy level of students who take the AIME for the first time drops significantly. It seems that they are so used to multiple choice questions that they rely on multiple choices as a confirmation that they are right. So when someone solves a problem, they compare their answer to the given choices and if the answer is on the list they assume that the answer must be correct. Their pattern is broken when there are no choices. So they arrive at an answer and since there is no way to check it against choices, they just submit it. Because of this lack of confirmation, checking their answer in other ways becomes more important.

Timing. At the AMC we have 3 minutes per problem. At the AIME — 12. That means the timing strategies need to be different. Indeed, the AMC is so fast-paced that it is reasonable to save time by not reading a problem twice. If you read it, you either solve it or skip it and go on. The student who is not trying to achieve a perfect score can decide in advance not to read those final, highly-difficult problems.
For the AIME it is not expensive, in relative terms of time, to read all the problems. The student can read the problems and choose the most promising ones to start with, knowing that if there is time they can always come back to other problems.

Guessing. Guessing at the AMC is very profitable if you can exclude three choices out of the given five. Guessing for the AIME is a waste of time because the answers are integers between 000 and 999. So the probability of a random guess is one in a thousand. Actually, this is not quite right, because the problem writers are human and it is much easier to write a problem with an answer of 10 than one with an answer of 731. But the AIME designers are trying very hard to make answers that are randomly distributed. So the probability of a random guess is not one in a thousand, but it is very close. You can improve your chances by an intelligent guess. For example, you might notice that the answer must be divisible by 10. But guessing is still a waste of time. Thinking about a problem for two minutes in order to increase the probability of a correct guess to one in a 100 means that your expected gain is 1/200 points per minute. Which is usually much less than the gain for checking your answers. You can play the guessing game if you have exhausted your other options.

What saddens me is that the students who are not trained in checking use their first guess to make their life choices. But this is a subject for a separate discussion.

I have already written about how American math competition are illogically structured, for the early rounds do not prepare students for the later rounds. The first time mathletes encounter proofs is in the third level, USAMO. How can they prepare for problems with proofs? My suggestion is to look East. All rounds of Russian math Olympiads — from the local to the regional to the national — are structured in the same way: they have a few problems that require proofs. This is similar to the USAMO. At the national All-Russian Olympiad, the difficulty level is the same as USAMO, while the regionals are easier. That makes the problems from the regionals an excellent way to practice for the USAMO. The best regional Olympiad in Russia is the Moscow Olympiad. Here is the problem from the 1995 Moscow Olympiad:

We start with four identical right triangles. In one move we can cut one of the triangles along the altitude perpendicular to the hypotenuse into two triangles. Prove that, after any number of moves, there are two identical triangles among the whole lot.

This style of problems is very different from those you find in the AMC and the AIME. The answer is not a number; rather, the problem requires proofs and inventiveness, and guessing cannot help.

Here is another problem from the 2002 Olympiad. In this particular case, the problem cannot be adapted for multiple choice:

The tangents of a triangle’s angles are positive integers. What are possible values for these tangents?

The problems are taken from two books: Moscow Mathematical Olympiads, 1993-1999, and Moscow Mathematical Olympiads, 2000-2005. I love these books and the problems they present from past Moscow Olympiads. The solutions are nicely written and the books often contain alternative solutions, extended discussion, and interesting remarks. In addition, some problems are indexed by topics, which is very useful for teachers like me. But the best thing about these books are the problems themselves. Look at the following gem from 2004, which can be used as a magic trick or an idea for a research paper:

A deck of 36 playing cards (four suits of nine cards each) lies in front of a psychic with their faces down. The psychic names the suit of the upper card; after that the card is turned over and shown to him. Then the psychic names the suit of the next card, and so on. The psychic’s goal is to guess the suit correctly as many times as possible.
The backs of the cards are asymmetric, so each card can be placed in the deck in two ways, and the psychic can see which way the top card is oriented. The psychic’s assistant knows the order of the cards in the deck; he is not allowed to change the order, but he may orient any card in either of the two ways.
Is it possible for the psychic to make arrangements with his assistant in advance, before the latter learns the order of the cards, so as to ensure that the suits of at least (a) 19 cards, (b) 23 cards will be guessed correctly?
If you devise a guessing strategy for another number of cards greater than 19, explain that too.

Do you remember how to divide three apples among four people? Make apple sauce, of course. In the following two puzzles you are not allowed to cut apples. Here is an old riddle:

There are four apples in a basket. How can you divide them among four people, so that one apple remains in the basket?

Here is a variation from Konstantin Knop’s blog:

There are four apples in a basket. How can you divide them among three people, so that no one has more than the others and one apple remains in the basket?