2015 Coin Problem Solution

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 100i 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, 10070 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.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

2014 Math Festival in Moscow

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?

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

My First Husband with My Third Husband

Bernstein and Goncharov

The year is 1994. The man on the left is my first husband, Alexander Goncharov. Although we were out of touch for a decade, when I married my third husband, Joseph Bernstein (on the right), Goncharov started visiting us. It wasn’t me he was interested in: he wanted to talk mathematics with my husband. I found this situation hilarious, so I took this photo.

But that’s not all. My second husband, Andrey Radul, is not in the picture. But all four of us were students of Israel Gelfand. In short, my three ex-husbands and I are mathematical siblings — that is, we are all one big happy mathematical family.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Best Writing on Mathematics 2016

Best Writing on Mathematics 2016The Best Writing on Mathematics 2016 is out. I am happy that my paper The Pioneering Role of the Sierpinski Gasket is included. The paper is written jointly with my high-school students Eric Nie and Alok Puranik as our PRIMES-2014 project.

At the end of the book there is a short list of notable writings that were considered but didn’t make it. The “short” list is actually a dozen pages long. And it includes two more papers of mine:

To continue bragging, I want to mention that my paper A Line of Sages was on the short list for 2015 volume. And my paper Conway’s Wizards was included in the 2014 volume.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Which One Doesn’t Belong?

Which One Doesn't Belong?

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.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

A Waterfall of my Feelings

I married an American citizen and moved to the US in 1990. At the time I was a very patriotic Russian. It took me a year of pain to realize that some of my ideas had been influenced by Soviet propaganda. After I washed away the brainwashing, I fell in love with the US. For 25 years I thought that America was great. Not anymore.

For the last several months I’ve been worried as never before in my life. I feel paralyzed and sick. To help myself I decided to put my feelings in words.

World War. My mom was 15 when World War II started. The war affected her entire life, as well as the lives of everyone in the USSR. Every now and then my mom would tell me, “You are lucky that you are already 20 and you haven’t witnessed a world war.” I moved to the US while my mom stayed back in Russia. From time to time I tell myself something like, “I am lucky that halfway through my expected lifetime, I haven’t had to live through a world war.” It’s been more than 70 years since WWII ended. To maintain the peace is a difficult job. Everything needs to be in balance. Trump is disrupting this balance. I am worried sick that my children or grandchildren will have to witness a major war.

The Red Button. I’ve noticed that, as a true showman, Trump likes misdirecting attention from things that worry him to fantastic plot twists that he invents. What’s the best way to make people forget about his tax returns? It’s the nuclear button. Dropping a nuclear bomb some place will divert people from thinking about his tax returns. As his plot twists are escalating, is he crazy enough to push the button?

Climate. The year 2014 was the warmest on record. The year 2015 was even warmer. And last year, 2016, was even warmer than that. I remember Vladimir Arnold’s class on differential equations. He talked about a painting that had been hanging on a wall for 20 years. Then it unexpectedly fell off. Mathematics can explain how such catastrophic events can happen. I keep thinking about our Earth: melting ice, dead reefs, fish eating plastic, and so much more. My grandchildren might not be able to enjoy beaches and forests the way I did. What if, like the fallen painting, the Earth can spiral out of control and completely deteriorate? But Trump is ignoring the climate issues. Does he care about our grandchildren? I am horrified that Trump’s policies will push climate catastrophe beyond the point of no return.

The Truth. Wiretapping is not wiretapping. Phony jobs numbers stopped being phony as soon as Trump decided that he deserved the credit. The news is fake when Trump doesn’t like it. Trump is a pathological liar; he assaults the truth. Being a scientist I am in search of truth, and Trump diminishes it. I do not understand why people ignore his lies. Two plus two is four whether you are a democrat, or a republican, or whomever. Facts are facts, alternative facts are lies. I am scared that lies have become acceptable and no one cares about the truth any more.

Russia. I lived in Russia for the first unhappy half of my life, and in the US for the second happy half. I do not want to go back. There is something fishy between Putin and Trump. Whether it is blackmail or money, or both, I do not know the details yet, But Trump is under Putin’s influence. Trump didn’t win the elections: Putin won. This horrifies me. I do not want to go back to being under Russian rule.

Gender Issues. I grew up in a country where the idea of a good husband was a man who wasn’t a drunkard. That wasn’t enough for me. I dreamed of a relationship in which there would be an equal division of work, both outside and inside the home. I could not achieve that because in Russian culture both people work full-time and the wife is solely responsible for all the house chores. Moreover, Russia was much poorer than the US: most homes didn’t have washing machines; we never heard of disposable diapers; and there were very long lines for milk and other necessities.

The life in USSR was really unfair to women. Most women had a full-time job and several hours of home chores every day. When I moved to the US, I thought I was in paradise. Not only did I have diapers and a washing machine, I was spending a fraction of the time shopping, not to mention that my husband was open to helping me, and didn’t mind us paying for the occasional babysitter or cleaner.

For some time I was blind to gender issues in the US because it was so much better. Then I slowly opened my eyes and became aware of the bias. For some years it has felt like gender equity was improving. Now, with a misogynistic president, I feel that the situation might revert to the dark ages. When women are not happy, their children are not happy, and they grow up to be not happy. If the pursuit of happiness is the goal, the life has to be fair to all groups. But Trump insults not only women but also immigrants, Muslims, members of the LGBTQ community, as well as the poor and the sick. The list is so long, that almost everyone is marginalized. This is not a path towards a happy society.

Democracy. Trump attacks the press and attempts to exclude them. Trump has insulted the intelligence community and the courts. He seems to be trying to take more power to the presidency at the expense of the other branches of government. He ignores his conflicts of interest. Trump disregards every rule of democracy and gets away with it. I am horrified that our democracy is dying.

Tax Returns. Trump’s tax returns could either exonerate him or prove that he is Putin’s puppet. The fact that he is hiding the returns makes me believe that the latter is more probable. Why the Republicans refuse to demand to see his returns is beyond my understanding.

Corruption. Trump does so many unethical things. Most of his decisions as president seem to be governed by Trump trying to get richer. Let us consider his hotel in Azerbaijan—a highly corrupt country. Having lived in a highly corrupt country myself, I know how it works. For example, an Azerbaijani government official who has access to their country’s money can make a deal that involves a personal kickback. This means that their government is paying more than necessary for a service or product in order to cover that kickback. This is how national money makes its way into individual pockets. Since all the deals in Azerbaijan are reputed to be like that, I imagine that when Trump built his hotel there, the Trump organization was overpaid in order to cover the bribe to local officials. Will our country become as corrupt as Azerbaijan?

Americans. The biggest shock of the election was that so many people were so gullible and actually voted for Trump. They didn’t see that his agenda is focused on his own profit, and that he lies and makes promises he doesn’t plan to deliver. It really terrifies me that there are some people who are not gullible but still voted for Trump.

Is there hope?

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Winning Nim Against a Player who Plays Randomly

I recently wrote about my way of playing Nim against a player who doesn’t know how to play. If my move starts in an N-position, then I obviously win. If my move starts in a P-position, I would remove one token hoping that more tokens for my opponent means more opportunity for them to make a mistake. But which token to remove? Does it make a difference from which pile I choose?

Consider the position (2,4,6). If I take one token, my opponent has 11 different moves. If I choose one token from the first or the last pile, my opponent needs to get to (1,4,5) not to lose. If I choose one token from the middle pile, my opponent needs to get to (1,3,2) not to lose. But the first possibility is better, because there are more tokens left, which gives me a better chance to have a longer game in case my opponent guesses correctly.

That is the strategy I actually use: I take one token so that the only way for the opponent to win is to take one token too.

This is a good heuristic idea, but to make such a strategy precise we need to know the probability distribution of the moves of my opponent. So let us assume that s/he picks a move uniformly at random. If there are n tokens in a N-position, then there are n − 1 possible moves. At least one of them goes to a P-position. That means my best chance to get on the winning track after the first move is not more than n/(n−1).

If there are 2 or 3 heaps, then the best strategy is to go for the longest game. With this strategy my opponent always has exactly one move to get to a P-position, I win after the first turn with probability n/(n−1). I lose the game with probability 1/(n−1)!!.

Something interesting happens if there are more than three heaps. In this case it is possible to have more than one winning move from a N-position. It is not obvious that I should play the longest game. Consider position (1,3,5,7). If I remove one token, then my opponent has three winning moves to a position with 14 tokens. On the other hand, if I remove 2 tokens from the second or the fourth pile, then my opponent has one good move, though to a position with only 12 tokens. What should I do?

I leave it to my readers to calculate the optimal strategy against a random player starting from position (1,3,5,7).

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Hidden Beauty

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?

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Can You Solve My Problems?

Melanoma StatsAlex 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?

Odd One Out Billboard

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Playing with Pascal’s Triangle

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

Pascal Triangle Mod 2

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 n2n + 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.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail