Tanya Khovanova's Math Blog


This blog has a modern version at http://blog.tanyakhovanova.com/, where you can leave comments. This page contains the copies of recent blog entries. The older copies are here:


Content

If you enjoy this page you can support it by shopping at amazon through this link. Thank you.


More Computer Jokes

* * *

Don't anthropomorphize computers: They don't like it.

* * *

I do not have dreams any more. What did I do wrong to make them delete my account?

* * *

How to restore justice: Create a folder named Justice. Delete it. Go to the trash bin and click restore.

* * *

An asocial network: When you sign up, you are friends with everyone. Then you send un-friend requests.


Derek Kisman's Ex Post Facto

I already wrote about two puzzles that Derek Kisman made for the 2013 MIT Mystery Hunt. The first puzzle is now called the Fractal Word Search. It is available on the Hunt website under its name In the Details. I posted one essay about the puzzle and another one describing its solution. The second puzzle, 50/50, is considered one of the most difficult hunt puzzles ever. Unfortunately, the puzzle is not available, but my description of it is.

Today let's look at the third puzzle Derek made for the 2013 Hunt, building on an idea from Tom Yue. This is a non-mathematical crossword puzzle. Derek tends to write multi-layered puzzles: You think you've got the answer, but the answer you've got is actually a hint for the next step.

Often multi-layered puzzles get solvers frustrated, but the previous paragraph is a hint in itself. If you expect the difficulty, you might appreciate the fantastic beauty of this puzzle.

Welcome to Ex Post Facto.


Fair-Share Sequences

Every time I visit Princeton, or otherwise am in the same city as my friend John Conway, I invite him for lunch or dinner. I have this rule for myself: I invite, I pay. If we are in the same place for several meals we alternate paying. Once John Conway complained that our tradition is not fair to me. From time to time we have an odd number of meals per visit and I end up paying more. I do not trust my memory, so I prefer simplicity. I resisted any change to our tradition. We broke the tradition only once, but that is a story for another day.

Let's discuss the mathematical way of paying for meals. Many people suggest using the Thue-Morse sequence instead of the alternating sequence of taking turns. When you alternate, you use the sequence ABABAB…. If this is the order of paying for things, the sequence gives advantage to the second person. So the suggestion is to take turns taking turns: ABBAABBAABBA…. If you are a nerd like me, you wouldn't stop here. This new rule can also give a potential advantage to one person, so we should take turns taking turns taking turns. Continuing this to infinity we get the Thue-Morse sequence: ABBABAABBAABABBA… The next 2n letters are generated from the first 2n by swapping A and B. Some even call this sequence a fair-share sequence.

Should I go ahead and implement this sequence each time I cross paths with John Conway? Actually, the fairness of this sequence is overrated. I probably have 2 or 3 meals with John per trip. If I pay first every time, this sequence will give me an advantage. It only makes sense to use it if there is a very long stretch of meals. This could happen, for example, if we end up living in the same city. But in this case, the alternating sequence is not so bad either, and is much simpler.

Many people suggest another use for this sequence. Suppose you are divorcing and dividing a huge pile of your possessions. A wrong way to do it is to take turns. First Alice choses a piece she wants, then Bob, then Alice, and so on. Alice has the advantage as the first person to choose. An alternative suggestion I hear in different places, for example from standupmaths, is to use the Thue-Morse sequence. I don't like this suggestion either. If Alice and Bob value their stuff differently, there is a better algorithm, called the Knaster inheritance procedure, that allows each of them to think they are getting more than a half. If both of them have the same value for each piece, then the Thue-Morse sequence might not be good either. Suppose one of the pieces they are dividing is worth more than everything else put together. Then the only reasonable way to take turns is ABBBB….

The beauty of the Thue-Morse sequence is that it works very well if there are a lot of items and their consecutive prices form a power function of a small degree k, such as a square or a cube function. After 2k+1 turns made according to this sequence, Alice and Bob will have a tie. You might think that if the sequence of prices doesn't grow very fast, then using the Thue-Morse sequence is okay.

Not so fast. Here is the sequence of prices that I specifically constructed for this purpose: 5,4,4,4,3,3,3,2,2,2,2,1,1,0,0,0. The rule is: every time a turn in the Thue-Morse sequence switches from A to B, the value goes down by 1. Alice gets an extra 1 every time she is in the odd position. This is exactly half of her turns. That is every four turns, she gets an extra 1.

If the prices grow faster than a power, then the sequence doesn't work either. Suppose your pieces have values that form a Fibonacci sequence. Take a look at what happens after seven turns. Alice will have pieces priced Fn + Fn-3 + Fn-5 + Fn-6. Bob will have Fn-1 + Fn-2 + Fn-4. We see that Alice gets more by Fn-3. This value is bigger than the value of all the leftovers together.

I suggest a different way to divide the Fibonacci-priced possessions. If Alice takes the first piece, then Bob should take two next pieces to tie with Alice. So the sequence might be ABBABBABB…. I can combine this idea with flipping turns. So we start with a triple ABB, then switch to BAA. After that we can continue and flip the whole thing: ABBBAABAAABB. Then we flip the whole thing again. And again and again. At the end we get a sequence that I decided to call the Fibonacci fair-share sequence.

I leave you with an exercise. Describe the Tribonacci fair-share sequence.


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.


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?

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.


The Best Writing on Mathematics 2016

Best Writing on Mathematics 2016

The 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: