Tanya Khovanova's Math Blog

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).

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 already posted a funny true story that Smullyan told me when I last visited him. Raymond Smullyan died recently at the age of 97 and my mind keeps coming back to this last visit.

The year was 2012 and I was about to drive back to Boston after my talk at Penn State. Smullyan’s place in the Catskills was on the way—sort of. I wanted to call him, but I was apprehensive. Raymond Smullyan had a webpage on which his email was invisible. You could find his email address by looking at the source file or by highlighting empty space at the bottom of the page. Making your contact information invisible sends a mixed message.

While this was a little eccentric, it meant that only people who were smart enough to find it, could access his email address. I already knew his email because he had given it to me along with his witty reply to my blog post about our meeting at the Gathering for Gardner in 2010.

In our personal interactions, he always seemed to like me, so I called Raymond and arranged a visit for the next day around lunch time. When I knocked on his door, no one answered, but the door was open, and since Smullyan was expecting me, I walked right in. “Hello? Anyone there? Hello? Hello?” As I wandered around the house, I saw an open bedroom door and inside Smullyan was sleeping. So I sat down in his library and picked up a book.

When he woke up, he was happy to see me, and he was hungry. He told me that he didn’t eat at home, so we should go out together for lunch. I was hungry too, so I happily agreed. Then he said that he wanted to drive. I do not have a poker face, so he saw the fear in me. My only other trip with a nonagenarian driver flashed in front of my eyes. The driver had been Roman Totenberg and it had been the scariest drive I have ever experienced.

I said that I wanted to drive myself. Annoyed, Raymond asked me if I was afraid of him taking the wheel. I told him that I have severe motion sickness and always prefer to drive myself. Raymond could see that I was telling the truth. I got the impression that he was actually relieved when he agreed to go in my car.

We went to Selena’s Diner. He took out playing cards with which he showed me magic tricks. I showed him some tricks too. This was probably a bad move as he abandoned me to go to the neighboring table to show his magic tricks to a couple of young girls. They were horrified at first”his unruly hair, his over-the-top energy, his ebullient behavior”but between me and the waitress, we quickly reassured them. The girls enjoyed the tricks, and I enjoyed my visit.

Like many people, I was appalled by Trump’s immigration ban. On the Internet I found many essays that explained that he did not include in the ban those majority-Muslim countries in which he has business interests. See for example, an article at Forbes with a nice map, and an article at NPR.

Now the countries that are excluded are motivated to continue to support Trump’s businesses, and to offer him bribes and good deals in exchange for staying out of the ban. The countries on the list are also motivated to approach Trump and offer him a sweet business deal.

So even if the courts stopped the ban, he has already succeeded in showing every country in the world that to be on his good side requires that they pay up. And China got the hint and granted Trump a trademark he’s been seeking for a decade.

Looks like Trump’s vision of a great America is a very rich Mr Trump.

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.

The first time I visited the US was in 1990 at the invitation of an old friend, Joseph Bernstein. After my arrival Joseph proposed and I accepted, but my essay is not about that.

Joseph reintroduced me to his daughter, Mira, who was then in her late teens. I was struck by Mira’s charm. I had never before met teenagers like her. Of course, Joseph got points for that as I was hoping to have a child with him. When I moved to the US I met some other kids who were also incredibly charming. It was too late to take points away from Joseph, but it made me realize what a huge difference there was between Soviet and American teenagers. American teenagers were happier, more relaxed, better mannered, and less cynical than Soviet ones.

My oldest son, Alexey, was born in the USSR and moved to the US when he was eight. One unremarkable day when he was in middle school (Baker public school in Brookline), the principle invited me for a chat. I came to the school very worried. The principal explained to me that there was a kid who was bugging Alexey and Alexey pushed him back with a pencil. While the principal proceeded to explain the dangers of a pencil, I tuned out. I needed all my energy to conceal my happy smile. This was one of the happiest moments of my life in the US. What a great country I live in where the biggest worry of a principal in a middle school is the waving of a pencil! I remembered Alexey’s prestigious school in Moscow. They had fights every day that resulted in bloody noses and lost teeth. When I complained to his Russian teacher, she told me that it was not her job to supervise children during big breaks. Plus the children needed to learn to be tough. No wonder American children are happier.

I was wondering if there were any advantages to a Soviet upbringing. For one thing, Soviet kids grow up earlier and are less naive. They are more prepared for harsh realities than those American kids who are privileged.

Naive children grow up into naive adults. Naive adults become naive presidents. I watched with pain as naive Bush (“I looked the man in the eye. I found him to be very straightforward and trustworthy.”) and naive Obama (Russian reset) misunderstood and underestimated Putin.

Putin is (and, according to Forbes Magazine, has been for the last four years) the most powerful person in the world. Even though the US kept its distance from Russia, he was able to manipulate us from afar. Now that Trump wants to be close to Putin, the manipulation will be even easier. Putin is better at this game. He will win and we will lose.

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?