Tanya Khovanova's Math Blog

SEAHOP created a practice puzzle, called “Making Connections,” that includes me. It seems I am making connections.

I recently posted a short article on plagiarism. Did you notice that not a word of it was mine?

Baron Münchhausen is famous for his tall tales. My co-author Konstantin Knop wants to rehabilitate him and so invents problems where the Baron is proven to be truthful from the start. We already wrote a paper about one such problem. Here is a new problem by Konstantin:

Kostya has a black box, such that if you put in exactly 3 coins of distinct weights, the box will expose the coin of median weight. The Baron gave Kostya 5 coins of distinct weights and told him which coin has the median weight. Can Kostya check that the Baron is right, using the box not more than 3 times?

Actually, Konstantin designed a more complicated problem that was given at the Euler Olympiad, 2012 in Russia.

Let n be a fixed integer. Kostya has a black box, such that if you put in exactly 2n+1 coins of distinct weights, the box will expose the coin of median weight. The Baron gave Kostya 4n+1 coins of distinct weights and told him which coin has the median weight. Can Kostya check that the Baron is right, using the box not more than n+2 times?

Note that Kostya can’t just put 4n+1 coins in the box. The box accepts exactly 2n+1 coins. The problem that I started with is for n = 1. Even such a simple variation was a lot of fun for me to solve. So, have fun.

Once upon a time there was a land where the only antidote to a poison was a stronger poison, which needed to be the next drink after the first poison. In this land, a malevolent dragon challenges the country’s wise king to a duel. The king has no choice but to accept.

By bribing the judges, the dragon succeeds in establishing the following rules of the duel: Each dueler brings a full cup. First they must drink half of their opponent’s cup and then they must drink half of their own cup.

The dragon wanted these rules because he is able to fly to a volcano, where the strongest poison in the country is located. The king doesn’t have the dragon’s abilities, so there is no way he can get the strongest poison. The dragon is confident of winning because he will bring the stronger poison.

The only advantage the king has is that the dragon is dumb and straightforward. The king correctly predicts what the dragon will do. How can the king kill the dragon and survive?

There is an array containing all the integers from 1 to n in some order, except that one integer is missing. Suggest an efficient algorithm for finding the missing number.

A friend gave me the problem above as I was driving him from the airport. He had just been at a job interview where they gave him two problems. This one can be solved in linear time and constant space.

But my friend was really excited by the next one:

There is an array containing all the integers from 1 to n in some order, except that one integer is missing and another is duplicated. Suggest an efficient algorithm for finding both numbers.

My friend found an algorithm that also works in linear time and constant space. However, the interviewer didn’t know that solution. The interviewer expected an algorithm that works in n log n time.

The company claims that they are looking for the smartest people in the world, and my friend had presented them with an impressive solution to the problem. Despite his excitement, I predicted that they would not hire him. Guess who was right?

I reacted like this because of my own story. Many years ago I was interviewing for a company that also wanted the smartest people in the world. At the interview, the guy gave me a list of problems, but said that he didn’t expect me to solve all of them — just a few. The problems were so difficult that he wanted to sit with me and read them together to make sure that I understood them.

The problems were Olympiad style, which is my forte. While we were reading them, I solved half of them. During the next hour I solved the rest. The interviewer was stunned. He told me of an additional problem that he and his colleagues had been trying to solve for a long time and couldn’t. He asked me to try. I solved that one as well. Guess what? I wasn’t hired. Hence, my reaction to my friend’s interview.

The good news: I still remember the problem they couldn’t solve:

A car is on a circular road that has several gas stations. The gas stations are running low on gas and the total amount of gas available at the stations and in the car is exactly enough for the car to drive around the road once. Is it true that there is a place on the road where the car can start driving, stopping to refuel at each station, so that the car completes a full circle without running out of gas? Assume that the car’s tank is large enough not to present a limitation.

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.

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.

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?

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?