Tanya Khovanova's Math Blog

A while ago I posted my second favorite problem from the 2015 All-Russian Math Olympiad:

Problem. A coin collector has 100 coins that look identical. He knows that 30 of the coins are genuine and 70 fake. He also knows that all the genuine coins weigh the same and all the fake coins have different weights, and every fake coin is heavier than a genuine coin. He doesn’t know the exact weights though. He has a balance scale without weights that he can use to compare the weights of two groups with the same number of coins. What is the smallest number of weighings the collector needs to guarantee finding at least one genuine coin?

Now it’s solution time. First we show that we can do this in 70 weighings. The strategy is to compare one coin against one coin. If the scale balances, we are lucky and can stop, because that means we have found two real coins. If the scale is unbalanced, the heavier coin is definitely fake and we can remove it from consideration. In the worst case, we will do 70 unbalanced weighings that allow us to remove all the fake coins, and we will find all the real coins.

The more difficult part is to show that 69 weighings do not guarantee finding the real coin. We do it by contradiction. Suppose the weights are such that the real coin weighs 1 gram and the i-th fake coin weighs 100ⁱ grams. That means whatever coins we put on the scale, the heaviest pan is the pan that has the fake coin with the largest index among the fake coins on the scale.

Suppose there is a strategy to find a real coin in 69 weighings. Given this strategy, we produce an example designed for this strategy, so that the weighings are consistent, but the collector cannot find a real coin.

For the first weighing we assign the heaviest weight, 100⁷⁰ to one of the coins on the scale and claim that the pan with this coin is heavier. We continue recursively. If a weighing has the coins with assigned weights, we pick the heaviest coin on the pans and claim that the corresponding pan is heavier. If there are no coins with assigned weights on pans, we pick any coin on the pans, assigned the largest available weight to it and claim that the corresponding pan is heavier.

After 69 weighings, not more than 69 coins have assigned weights, while all the weighings are consistent. The rest of the coins can have any of the leftover weights. For example, any of the rest of the coins can weigh 100 grams. That means that there is no coin that is guaranteed to be real.

I stumbled upon a couple of problems that I like while scanning the Russian website of Math Festival in Moscow 2014. The problems are for 7 graders.

Problem. Inside a 5-by-8 rectangle, Bart draws closed paths that follow diagonals of 1-by-2 rectangles. Find the longest possible path.

This problem is really very difficult. The competition organizers offered an extra point for every diagonal on top of 16. The official solution has 24 diagonals, but no proof that it’s the longest. I’m not sure anyone knows if it is the longest.

Here is another problem:

Problem. Alice and Bob are playing a game. They start with two numbers: 2014 and 2015. In one move a player can do one of two things:

1. subtract one of the numbers by one of the non-zero digits in any of the two numbers or,
2. divide one number by two if the number is even.

The winner is the person who is the first to get a one-digit number. Assuming that Alice starts, who wins?

I like Odd-One-Out puzzles that are ambiguous. That is why I bought the book Which One Doesn’t Belong? Look at the cover: which is the odd one out? The book doesn’t include answers, but it has nine more examples in each of which there are several possible odd-one-outs.

It is rare when a word equation coincides with a number equation.

Problem. A store sells letter magnets. The same letters cost the same and different letters might not cost the same. The word ONE costs 1 dollar, the word TWO costs 2 dollars, and the word ELEVEN costs 11 dollars. What is the cost of TWELVE?

Alex Bellos wrote a puzzle book Can You Solve My Problems? Ingenious, Perplexing, and Totally Satisfying Math and Logic Puzzles The book contains a mixture of famous puzzles and their solutions. Some of the puzzles are not mathematical in the strictest sense, but still have an appeal for mathematicians. For example, which integer comes up first when you alphabetize all the integers up to a quadrillion?

Recognize the puzzle on that book cover? You’re right! That’s my Odd One Out puzzle. Doesn’t it look great in lights on that billboard in London?

Mine isn’t the only terrific puzzle in the book. In fact, one of the puzzles got my special attention as it is related to our current PRIMES polymath project. Here it is:

A Sticky Problem. Dick has a stick. He saws it in two. If the cut is made [uniformly] at random anywhere along the stick, what is the length, on average, of the smaller part?

The beautiful Pascal triangle has been around for many years. Can you say something new about it?

Of course you can. Mathematicians always find new way to look at things. In 2012 RSI student, Kevin Garbe, did some new and cool research related to the triangle. Consider Pascal’s triangle modulo 2, see picture which was copied from a stackexchange discussion.

A consecutive block of m digits in one row of the triangle modulo 2 is called an m-block. If you search the triangle you will find that all possible binary strings of length 2 are m-blocks. Will this trend continue? Yes, you can find any possible string of length 3, but it stops there. The blocks you can find are called accessible blocks. So, which blocks of length 4 are not accessible?

There are only two strings that are not accessible: 1101 and 1011. It is not surprising that they are reflections of each other. Pascal’s triangle respects mirror symmetry and the answer should be symmetric with respect to reflection.

You can’t find these blocks on the picture, but how do we prove that they are not accessible, that is, that you can’t ever find them? The following amazing property of the triangle can help. We call a row odd/even, if it corresponds to binomial coefficients of n choose something, where n is an odd/even number. Every odd row has every digit doubled. Moreover, if we take odd rows and replace every double digit with its single self we get back Pascal’s triangle. Obviously the two strings 1101 and 1011 can’t be parts of odd rows.

What about even rows? The even rows have a similar property: every even-indexed digit is a zero. If you remove these zeros you get back Pascal’s triangle. The two strings 1101 and 1011 can’t be part of even rows. Therefore, they are not accessible.

The next question is to count the number of inaccessible blocks of a given length: a(n). This and much more was done by Kevin Garbe for his RSI 2012 project. (I was the head mentor of the math projects.) His paper is published on the arxiv. The answer to the question can be found by constructing recurrence relations for odd/even rows. It can be shown that a(2r) = 3a(r) + a(r+1) − 6 and a(2r+1) = 3a(r) + 2a(r+1) − 6. As a result the number of inaccessible blocks of length n is n² − n + 2. I wonder if there exists a direct proof of this formula without considering odd and even rows separately.

This RSI result was so pretty that it became a question at our entrance PRIMES test for the year 2013. In the test we changed the word accessible to admissible, so that it would be more difficult for applicants to find the research. Besides, Garbe’s paper wasn’t arxived yet.

The pretty picture above is from the stackexchange, where one of our PRIMES applicants tried to solicit help in solving the test question. What a shame.

I picked four problems that I liked from the Moscow Math Olympiad 2016:

Problem 1. Ten people are sitting around a round table. Some of them are knights who always tell the truth, and some of them are knaves who always lie. Two people said, “Both neighbors of mine are knaves.” The other eight people said, “Both neighbors of mine are knights.” How many knights might be sitting around the round table?

Problem 2. Today at least three members of the English club came to the club. Following the tradition, each member brought their favorite juice in the amount they plan to drink tonight. By the rules of the club, at any moment any three members of the club can sit at a table and drink from their juice bottles on the condition that they drink the same amount of juice. Prove that all the members can finish their juice bottles tonight if and only if no one brings more than the third of the total juice brought to the club.

Problem 3. Three piles of nuts together contain an even number of nuts. One move consists of moving half of the nuts from a pile with an even number of nuts to one of the other two piles. Prove that no matter what the initial position of nuts, it is possible to collect exactly half of all the nuts in one pile.

Problem 4. N people crossed the river starting from the left bank and using one boat. Each time two people rowed a boat to the right bank and one person returned the boat back to the left bank. Before the crossing each person knew one joke that was different from all the other persons’ jokes. While there were two people in the boat, each told the other person all the jokes they knew at the time. For any integer k find the smallest N such that it is possible that after the crossing each person knows at least k more jokes in addition to the one they knew at the start.

Spoiler for Problem 2. I want to mention a beautiful solution to problem 2. Let’s divide a circle into n arcs proportionate to the amount of juice members have. Let us inscribe an equilateral triangle into the circle. In a general position the vertices of the triangle point to three distinct people. These are the people who should start drinking juices with the same speed. We rotate the triangle to match the drinking speed, and as soon as the triangle switches the arcs, we switch drinking people correspondingly. After 120 degree rotation all the juices will be finished.

I recently posted the following puzzle:

Puzzle. We have 3²ⁿ identical-looking coins. One of the coins is fake and lighter than the other coins, which all are real. We also have three scales: two normal and one random. Find the fake coin in the smallest total number of weighings.

Here is my son Sergei’s solution. Divide the coins into nine groups of equal size and number the groups in ternary: 00, 01, 02, 10, 11, 12, 20, 21, and 22. On each scale we put three groups versus three groups. On the first scale we compare the three groups that start with 1 with the three groups that start with 2. For the second scale we do the same using the last digit instead of the first one, and for the third scale we use the sum of two digits modulo 3. Any pair of scales, if they are assumed to be normal, would point to one out of nine groups as the group containing the fake coin.

If all three pairs of scales agree on one group, then this is the group containing the fake coin. Thus in three weighings, we reduce the number of groups of coins by a factor of nine. If the pairs of scales do not agree, then the random scale produced a wrong weighing and thus can be found out. How do we do that? We have three out of nine groups of coins each of which might contain the fake coin. We compare two of the groups on all three scales. This way we know exactly which group contains the fake coin and, consequently, which scale generated a wrong weighing. If we know the random scale, we can speed up the rest of the process of finding the fake coin. Thus in the worst case we require 3n+3 weighings.

The big idea here is that as soon as the random scale shows a wrong weighing result it can be found out. So in the worst case, the random scale behaves as a normal scale and messes things up at the very end. Sergei’s solution can be improved to 3n+1 weighings. Can you do that?

The improved solution is written in a paper Взвешивания на «хитрых весах» (in Russian) by Konstantin Knop, that is published in Математика в школе 2009-2. The paper contains an even stronger solution that provides a better asymptotics.

May 5 of 1955 can be written as 5/5/55. How many times during the 20th century the date in the format month day and the last two digits of the year can be written with the same digit?

If like me, you fancy Raymond Smullyan and his books, then you’ve heard about knights and knaves. Knights always tell the truth and knaves always lie. In addition to knights and knaves, there are normal people who sometimes tell the truth and sometimes lie. Here is a puzzle.

Puzzle. How, in one sentence, can a normal person prove that they are normal?

We can draw a parallel between people and coins. We can say that knights correspond to real coins, and knaves to fake coins that are lighter than real ones. Inspired by normal people, my coauthor Konstantin Knop invented chameleon coins. Chameleon coins can change their weight and behave like real or fake coins. I just wrote a post about chameleon coins.

Normal people are too unpredictable: they can consistently pretend to be knights or knaves. So logicians invented a simpler type of person, one who switches from telling the truth in one sentence to a lie in the next and then back to the truth. Such people are called alternators. Here is another puzzle:

Puzzle. You meet a person who is one of the three types: a knight, a knave, or an alternator. In two questions, find out which type they are.

Continuing a parallel between people and coins we can define alternator coins: the coins that switch their weight each time they are on the scale from weighing as much as real ones to weighing as much as fake ones. For the purposes of this essay, we assume that the fake coins are lighter than real ones. Unlike the chameleon coin, which might never reveal itself by always pretending to be real, the alternators can always be found. How do you find a single alternator among many real coins? There is a simple strategy: repeat every weighing twice. This strategy allows us to find an alternator among 9 coins in four weighings. Can we do better?

I used the alternator coins as a research project for my PRIMES STEP program where we do math research with students in seventh and eighth grade. The students started the alternator project and immediately discovered the strategy above. The next step is to describe a better strategy. For example, what is the maximum number of coins containing one alternator such that the alternator can always be found in four weighings?

But first we count possible outcomes. Suppose there is a strategy that finds an alternator. In this strategy we can’t have two unbalanced weighings in a row. To prove that, let us suppose there was an unbalanced weighing. Then the alternator switches its weight to a real coin and whether or not the alternator is on the scale, the next weighing must balance. The beauty of it is that given a strategy each outcome has to point to a particular coin as an alternator. That means the number of outcomes bounds the total number of coins that can be processed.

Counting the number of possible outcomes that do not have two unbalances in row is a matter of solving a recurrence, which I leave to the readers to find. The result is Jacobshtal numbers: the most beautiful sequence you might never have heard of. For example, the total number of possible outcomes of four weighings is 11. Since each outcome of a strategy needs to point to a coin, the total number of coins that can be processed in four weighings is not more than 11. But 11 is better than 9 in our previous strategy. Can we process 11 coins in four weighings? Yes, we can. I will describe the first part of the strategy.

So we have 11 coins, one of which is an alternator. In the first weighing we compare 5 coins against 5 coins. If the weighing unbalances, the alternator is on a lighter pan. Our problem is reduced to finding the alternator among five coins when we know that it is in the real state. If the weighing balances, then we know that if the alternator is among the coins on the scale it must now be in the light state. For the second weighting, we pick two sets of three coins out of this ten coins and compare them against each other. Notice that 3 is a Jacobsthal number, and 5, the number of coins outside the scale, is also a Jacobsthal number. If the second weighing balances, the alternator must be among 5 coins outside the scale. All but one of these coins are in the light state, and I leave it to the readers to finish the strategy. If the weighing unbalances, we need to find the alternator among 3 coins that are in the real state now. This can be done in two weighings, and again the readers are to the rescue.

It appears that Jacobsthal numbers provide the exact lower bound of the number of coins that can be processed. This is what my middle-schoolers discovered and proved. We wrote a paper on the subject. The strategy in the paper is adaptive. That means it changes depending on the results of the previous weighings. Can we find an oblivious strategy? I will tell you in later posts.