Archive for the ‘Math Competitions’ Category.

## Archimedes Helps Again

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.

Share:

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

## My Computational Linguistics Olympiads

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.

Share:## A Splashy Math Problem Solution

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 numberAso that for any natural numbern, there exists a square of a natural number that differs from the ceiling ofA^{n}by 2?

The problem is very difficult, but the solution is not long. It starts with a trick. Suppose *A* = *t*^{2}, then *A*^{n} + 1/*A*^{n} = *t*^{2n} + 1/*t*^{2n} = (*t*^{n} + 1/*t*^{n})^{2} − 2. If t < 1, then the ceiling of *A*^{n} differs by 2 from a square as long as *t*^{n} + 1/*t*^{n} 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*^{2} – 6*x* + 1, and declare *t* to be its largest root.

## The 41-st Tournament of the Towns

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 numbernthat doesn’t exceed the number of cards left in the row. The magician counts thenth 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).Numberxon 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.

Share:

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

## The Anniversary Coin

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

Share:

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?

## Build an All-red Cube

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.

Share:

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.

## Two Dice

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*) be the probabilities that die A (correspondingly B) shows

_{i}*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

_{i}z

^{i}and g(z) = ∑ b

_{i}z

^{i}. Then the desired result is that f(z)g(z) = ∑

_{j=0}

^{10}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

_{5}=b

_{5}=0 and the coefficient of z

^{10}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_{0}b_{0} = a_{5}b_{5} = 1/11. Then the probability of a total 7 is at least a_{0}b_{5} + a_{0}b_{5}. The geometric mean of a_{0}b_{5} and a_{0}b_{5}
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?

Share: