Tanya Khovanova's Math Blog

Here is a problem from the 1978 Kyiv Olympiad for 7 graders.

Is it possible to place seven points on a plane so that among any three of them, two will be at distance 1 from each other?

Below, you can find a lovely problem from the 2016 All-Russian Olympiad suggested by Bogdanov and Knop. I took some liberties translating it.

Problem. King Hiero II of Syracuse has 11 identical-looking metallic ingots. The king knows that the weights of the ingots are equal to 1, 2, …, 11 libras, in some order. He also has a bag, which would be ripped apart if someone were to put more than 11 libras worth of material into it. The king loves the bag and would kill if it was destroyed. Archimedes knows the weights of all the ingots. What is the smallest number of times he needs to use the bag to prove the weight of one of the ingots to the king?

And a bonus question from me.

Bonus. Add one more weighing to prove the weight of three more ingots.

Do you know that I participated in Linguistics Olympiads in high school? They are not well-known in the US, but the Soviet Union has been running them since 1965. The first International Linguistics Olympiad was conducted in 2003, and the US joined in 2007. They are called Computational Linguistics because you are expected to discover some phenomenon in an unfamiliar language on the fly instead of knowing a lot of languages already. The problems mostly need logic and are a good fit for a person who likes mathematics. However, a feel for languages is very helpful.

I do not remember why I started attending the Olympiads, but I remember that there were two sets of problems: more difficult for senior and less difficult for non-senior years. I used to be really good at these Olympiads. When I was in 8th grade, I finished my problems before the time ran out and started the senior problems. I got two awards: first place for non-senior years and second place for senior years. In 9th grade, I got two first-place awards. I didn’t know what to do in 10th grade, which was a senior year at that time in the USSR. I couldn’t get two first-place awards, as I could no longer compete in the non-senior category. I felt ashamed that my result could only be worse than in the previous years, so I just didn’t go.

The prizes were terrific: they gave me tons of rare language books. In the picture, a guy from the jury is carrying my prizes for me. I immediately sold the books at used-books stores for a good price. Looking back, I should have gone to the Olympiad in 10th grade: my winter boots had big holes.

I recently wrote a post, A Splashy Math Problem, with an interesting problem from the 2021 Moscow Math Olympiad.

Problem (by Dmitry Krekov). Does there exist a number A so that for any natural number n, there exists a square of a natural number that differs from the ceiling of Aⁿ by 2?

The problem is very difficult, but the solution is not long. It starts with a trick. Suppose A = t², then Aⁿ + 1/Aⁿ = t²ⁿ + 1/t²ⁿ = (tⁿ + 1/tⁿ)² − 2. If t < 1, then the ceiling of Aⁿ differs by 2 from a square as long as tⁿ + 1/tⁿ is an integer. A trivial induction shows that it is enough for t + 1/t to be an integer. What is left to do is to pick a suitable quadratic equation with the first and the last term equal to 1, say x² – 6x + 1, and declare t to be its largest root.

Today I present three problems from the 41-st Tournament of the Towns that I liked: an easy one, one that reminds me of the Collatz conjecture, and a hard one.

Problem 1 (by Aleksey Voropayev). A magician places all the cards from the standard 52-card deck face up in a row. He promises that the card left at the end will be the ace of clubs. At any moment, an audience member tells a number n that doesn’t exceed the number of cards left in the row. The magician counts the nth card from the left or right and removes it. Where does the magician need to put the ace of clubs to guarantee the success of his trick?

Problem 2 (by Vladislav Novikov). Number x on the blackboard can be replaced by either 3x + 1 or ⌊x/2⌋. Prove that you can use these operations to get to any natural number when starting with 1.

Problem 3 (by A. Gribalko). There are 2n consecutive integers written on a blackboard. In one move, you can split all the numbers into pairs and replace every pair a, b with two numbers: a + b and a − b. (The numbers can be subtracted in any order, and all pairs have to be replaced simultaneously.) Prove that no 2n consecutive integers will ever appear on the board after the first move.

A problem from the 2021 Moscow Math Olympiad went viral on Russian math channels. The author is Dmitry Krekov.

Problem. Does there exist a number A so that for any natural number n, there exists a square of a natural number that differs from the ceiling of Aⁿ by 2?

Konstantin Knop, the world’s top authority on coin-weighing puzzles, suggested the following problem for the 2019 Russian Math Olympiad.

Puzzle. Eight out of sixteen coins are heavier than the rest and weigh 11 grams each. The other eight coins weigh 10 grams each. We do not know which coin is which, but one coin is conspicuously marked as an “Anniversary” coin. Can you figure out whether the Anniversary coin is heavier or lighter using a balance scale at most three times?

This is one of my favorite problems given at the 2017 Moscow Olympiad to grades 6 and 7. It was suggested by one of my favorite problem writers: Alexander Shapovalov.

Problem. We are given eight unit cubes. The third of the total number of their faces are blue, and the rest are red. We build a large cube out of these cubes so that exactly the third of the unit cube’s visible faces are red. Prove that you can use these cubes to build a large cube whose faces are entirely red.

My friend Alex Ryba uses interesting math questions in the CUNY Math Challenge. For the 2016 challenge they had the following problem.

Problem. Eve owns two six-sided dice. They are not necessarily fair dice and not necessarily weighted in the same manner. Eve promises to give Alice and Bob each a fabulous prize if they each roll the same sum with her dice. Eve wishes to design her two dice to minimize the likelihood that she has to buy two fabulous prizes. Can she weight them so that the probability for Alice and Bob to get prizes is less than 1/10?

The best outcome for Eve would be if she can weight the dice so that the sum is uniform. In this case the probability that Alice and Bob get the prizes is 1/11. Unfortunately for Eve, such a distribution of weight for the dice is impossible. There are many ways to prove it.

I found a beautiful argument by Hagen von Eitzen on the stack exchange: Let a_i (correspondingly b_i) be the probabilities that die A (correspondingly B) shows i + 1. It would be very useful later that that i ranges over {0,1,2,3,4,5} for both dice. Let f(z) = ∑ a_izⁱ and g(z) = ∑ b_izⁱ. Then the desired result is that f(z)g(z) = ∑_j=0¹⁰ z^j/11. The roots of the right side are the non-real roots of unity. Therefore both f and g have no real roots. So, they must both have even degree. This implies a₅=b₅=0 and the coefficient of z¹⁰ in their product is also 0, contradiction.

Alex himself has a straightforward argument. The probabilities of 2 and 12 have to be equal to 1/11, therefore, a₀b₀ = a₅b₅ = 1/11. Then the probability of a total 7 is at least a₀b₅ + a₀b₅. The geometric mean of a₀b₅ and a₀b₅ is 1/11 (from above), so their arithmetic mean is at least 1/11 and their sum is at least 2/11. Therefore, the uniform distribution for sums is impossible.

So 1/11 is impossible, but how close to it can you get?

I just got this picture from my friend Victor Gutenmacher, which I never saw before. My 1975 IMO team is posing at our training grounds before the Olympiad trip to Bulgaria.

Left to right: Boris Yusin, Yuri Ionin, Zoya Moiseyeva (front), Gregory Galperin (back), me, Ilya Yunus, Valentin Skvortsov, Aleksandr Kornyushkin, Sergei Finashin, Sergei Fomin (front), Alexander Reznikov (back), Yuri Shmelev (front), Yuri Neretin (back), Victor Gutenmacher.

Our coaches are in the shot as well. Surprisingly, or not surprisingly, all of them moved to the USA. Yuri Ionin, now retired, was a professor at Central Michigan University. Gregory Galperin is a professor at Eastern Illinois University. Sergei Fomin is a professor at the University of Michigan. Victor Gutenmacher worked for BBN Technologies and Siemens PLM Software, and is now retired.

There are two more adults in the picture: Valentin Anatolievich Skvortsov, our leader and Zoya Ivanovna Moiseyeva, our deputy leader. Skvortsov was working at the math department of Moscow State University at that time. The University was angry that he didn’t block some students with Jewish heritage from the team thus allowing them to be accepted to Moscow State University without exams. I wrote a story of how Zoya persuaded Alexander Reznikov not to go to Moscow University to help Valentin. It ruined Alexander’s live, and didn’t even help Valentin. 1975 was Valentin’s last trip as the leader.