Tanya Khovanova's Math Blog

I found a strange piece of paper in an old pile. I believe that it is a visual proof of the following statement:

If ∞ = 1/0, then 0 = 1/∞.

Proof. Assume ∞ = 1/0. Rotate each side of the equation counterclockwise 90 degrees. We get 8 = −10. Subtract 8, getting 0 = −18. Then rotate both parts back: 0 = 1/∞. QED.

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.