Tanya Khovanova's Math Blog

Here is one of my all-time favorite problems.

Puzzle. Four glasses are placed on the four corners of a square rotating table; each glass is either right-side up or upside down. You need to turn them all in the same direction, either all facing up or all down. You may do so by grasping any two glasses and turning either none, one of them, or both over.
There are two catches: 1) You are blindfolded, and 2) the table is spun after each round. Assuming a bell rings when you have them all facing the same way, how do you do it?

When I first heard this problem, the person who tortured me with it forgot to mention the bell. The problem was impossible: there was no feedback. Then, the bell was mentioned. It was an aha moment: you get information, but only a confirmation that the problem is solved. I tried to think about the puzzle backwards. What could be my last step? Assume that I know that the glasses alternate around the table: up, down, up, down. Then, as my last step, I can reach for the diagonal glasses and turn them over.

This is how you might start thinking about this puzzle. You can find the rest of the solution on the puzzle’s Wikipedia page.

Here is a wonderful variation, proposed by Michael Hotiner from Ukraine, that appeared ten years ago at a puzzle competition. This variation is not cheap; the players must pay with their lives, albeit virtual ones.

Puzzle setup. Consider a computer game where at level M, there is an M-sided rotating table with glasses at each corner. The setup is similar to the four-glasses puzzle above. The player is blindfolded, and the table rotates between rounds. As soon as level M is over, if all the glasses face one direction, the bell rings, and the player moves to the next level, M+1.
At each round, the player can decide on the number N of glasses to touch. Upon deciding, they have to pay N! lives for that round. Then, the player can touch the glasses one by one, choosing the next glass depending on how the previous glasses are oriented. After all the glasses are touched, the player can decide which ones to turn upside down.

Let’s see what happens at the very beginning of this game. The game starts at level 1, with only one glass. The round is solved before it starts. The cost is 0. The bell rings, and the game immediately goes to level 2.

Consider level 2. If the bell doesn’t ring immediately, the glasses face different directions. The cheapest way to proceed is to choose N = 1 and turn any glass. The cost is 1.

Consider level 3. A player can solve it in one round by touching all three glasses and turning them the same way. The cost is 3! = 6. There is a cheaper method that costs 4 lives in two rounds. In the first round, the player can touch any two glasses and turn both of them up. If the bell doesn’t ring, then the third glass is upside down. In the next round, the player can touch two glasses. If one is upside down, that glass should be turned up. If both glasses are right side up, then the player should turn both of them over to finish the round.

Puzzle tasks.

1. Find a way to pass level 3 using only three lives.
2. Find the cheapest way to pass level 4.
3. Find the cheapest way for level 6.
4. Find a way to pass level 5 using only 30 lives.

Here are some problems that I liked from the YuMSh (Youths Math School in St. Petersburg) Olympiad.

Problem for 6th grade. Twenty people from an island of knights and knaves have a party. Knights always tell the truth, and knaves always lie. Each party-goer got a card with a different number from 1 to 20. When they were asked about their numbers, each answered with a number from 1 to 20. The sum of all the answers is 156. What is the minimum possible number of liars that have to be at the party?

Problem for 7th grade. Alice and Bob bought a deck of playing cards (52 cards total) and took turns gluing the cards on the wall one at a time. Alice was first. The game is lost if, after a move, the wall has 4 cards of the same suit or 4 cards of consecutive values (for example, 8-9-10-jack). Can Alice or Bob guarantee themselves a win, regardless of their opponent’s moves?

Problem for 7th grade. Buddhist monks gather in an infinite cave where a finite number of prime numbers are written on the wall. The numbers might not be distinct. Every second, one of the monks performs one of the following operations.

1. Adds to one of the numbers one of its digits.
2. Shuffles the digits of one of the numbers.

Every time they do it, they erase the old number and write the new one. The rule is that the new number has to be greater than the old one. If a composite number gets written on the wall of this cave, then the world collapses into nothingness. Can the monks save the world for eternity?

Problem for 8th grade. The incenter of a triangle is equidistant from the midpoints of the sides of the triangle. Prove that the triangle is equilateral.

Problem for 9th grade. Bob was given 30 distinct natural numbers. He wrote down all the 435 pairwise sums. It appears that among those sums, 230 are divisible by 3. How many of the original 30 numbers are divisible by 3?

Problem. Find the largest number n such that for any prime number p greater than 2 and less than n, the difference n − p is also a prime number.

I recently posted a cute Shapovalov’s puzzle about gnomes. Here is another easier gnome puzzle, also by Alexander Shapovalov.

Puzzle. All gnomes are knights or knaves: knights always tell the truth, and knaves always lie. There is a gnome on every cell of a 4 by 4 chessboard. It is known that both knights and knaves are present in this group. Every gnome states, “Among my neighbors, the number of knaves is the same as the number of knights”. How many knaves are there, if by neighbors they mean orthogonally adjacent gnomes?

The next gnome puzzle has a different author, Alexander Gribalko. Gnomes in this puzzle are not knights or knaves but rather friendly and polite beings.

Puzzle. Nine gnomes repeated the following procedure three times. They arranged themselves on a 3 by 3 chessboard with one gnome per cell and greeted all their orthogonal neighbors. Prove that not all pairs of gnomes greeted each other.

Ukraine is on my mind. Here is a problem for 9-graders from the 1978 Ukrainian Math Olympiad:

Problem. Prove that for every natural number n, the following number is not an integer.

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.