Tanya Khovanova's Math Blog

Kvant is a very popular Russian math and physics journal for high school-children. My favorite page is the one with puzzles directed to younger readers. Here are two puzzles from the latest online issue: 2012 number 3.

The first one, by N. Netrusova, is optimistic about the next year.

An astrologist believes that a year is happy if its digit representation contains four consecutive digits. For example, the next year, 2013, will be happy. When was the previous happy year?

The second problem is by L. Mednikov and A. Shapovalov. It confused me at first. For a moment I thought that the best answer is 241 rubles:

A big candle lasts one hour and costs 60 rubles. A small candle lasts 11 minutes and costs 11 rubles. Can you measure a minute by spending not more than a) 200 rubles, b) 150 rubles?

Do you like challenging puzzles? Are you tired of sudoku? Here’s your chance to try your hand at puzzles that are designed for world puzzle championships.

I’ve already done the homework for you — and it turned out to be more complicated than I anticipated. The world puzzle federation has a website, but unfortunately they are lazy or secretive. It is difficult to find puzzles there. A few puzzles are available in the World Puzzle Federation Newsletters.

Since I am stubborn, I spent a lot of time looking for championship puzzles. I found them in books. Here is the list I compiled so far. If you too are interested in high-level puzzles, this ought to make your search a lot easier. The book titles are confusing, so I added a description of what’s in them.

• Games Magazine Presents Brain Twisters from the First World Puzzle Championships — Warm-up puzzles, US/Canada Qualifying test, First World Championship, Foreign team puzzles.
• Games Magazine Presents Brain Twisters from the World Puzzle Championships, Volume 2 — US/Canada Qualifying test, Second World Puzzle Championship, Third World Puzzle Championship.
• Games Magazine Presents Brain Twisters from the World Puzzle Championships, Volume 3 — Fourth World Puzzle Championship, Fifth World Puzzle Championship.
• World Puzzle Championships Omnibus, Volume 1 — Contains World-Class Puzzles from the World Puzzle Championships Volumes 1-3 below.
• World-Class Puzzles from the World Puzzle Championships, Volume 1 — Sixth World Puzzle Championship and Seventh World Puzzle Championship.
• World-Class Puzzles from the World Puzzle Championships, Volume 2 — 1999 Qualifying test, Eighth World Puzzle Championship.
• The New York Times Sunday Crossword Omnibus, Volume 3 — 2000 Qualifying test, Ninth World Puzzle Championship.
• World-Class Puzzles from the World Puzzle Championships, Volume 4 — 2001 Qualifying test, Tenth World Puzzle Championship.
• World-Class Puzzles from the World Puzzle Championships, Volume 5 — 2002 Qualifying test, Eleventh World Puzzle Championship.
• Random House World-Class Puzzles — 2002 Qualifying test, Twelfth World Puzzle Championship. (The year for the qualifying test is probably a typo as puzzles differ from the qualifying test in the previous book,)

One of my favorite puzzle types is Easy as ABC. You have to fill one of A, B, C, and D in each row and column. The letters outside the grid indicate which letter you see first from that direction. Here is one from the 2011 newsletter:

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?