Tanya Khovanova's Math Blog

* * * (submitted by Sam Steingold)

I can count to 1023 on my 10 fingers. The rudest number is 132.

* * *

I kept forgetting my password, so I changed it to “incorrect”. Now, when I make a mistake during login, my computer reminds me: “Your password is incorrect.”

* * *

—You promised me 8% interest, and in reality it is 2%.
—2 is 8—to some degree.

* * * (submitted by Sam Steingold)

Quantum entanglement is simple: when you have a pair of socks and you put one of them on your left foot, the other one becomes the “right sock,” no matter where it is located in the universe.

* * *

Teacher:
—I keep telling my students that one half can’t be larger or smaller than the other. Still the larger half of my class doesn’t get it.

This famous trick puzzle is very old:

Puzzle. The professor is watching across a field how the son of the professor’s father is fighting with the father of the professor’s son. How is this possible?

This puzzle is tricky only because of gender-bias. Most people assume that the professor is male and miss the obvious intended solution, in which a female professor is watching her brother fighting with her husband.

I just gave this problem on a test. Here are other answers that I received.

• The professor is gay and is watching his brother fighting with his husband.
• The professor is watching his brother fighting with the father of the professor’s step-son.
• The father of the professor’s son is himself. So he is watching a video of himself fighting with his brother.

Years ago people couldn’t figure out this puzzle at all. So there has been progress. I was glad that my students suggested so many ideas that work. Nonetheless, many of them revealed their gender-bias by initially assuming that the professor is a man.

I can’t wait until this puzzle stops being tricky.

Puzzle. There are five houses of different colors next to each other equally spaced on the same road. In each house lives a man of a different profession.

• The blue house is adjacent to the mathematician’s and con-man’s houses.
• The first house on the left is green.
• The nurse lives immediately to the right of the mathematician.
• The teacher lives halfway between the plumber’s house and the yellow house.
• The nurse’s house is immediately to the right of the red house.

Who lives in the white house?

Correction Nov 11, 2017. Replaced “the same distance from” with “halfway between” to eliminate the possibility of the plumber living in the yellow house. Thank you to my readers for catching this mistake and to Smylers for suggesting a correction.

I do not remember where I saw this problem.

Problem. Invent a connected shape made out of squares on the square grid that cannot be cut into dominoes (rectangles with sides 1 and 2), but if you add a domino to the shape then you can cut the new bigger shape.

This problem reminds me of another famous and beautiful domino-covering problem.

Problem. Two opposite corner squares are cut out from the 8 by 8 square board. Can you cover the remaining shape with dominoes?

The solution to the second problem is to color the shape as a chess board and check that the number of black and white squares is not the same.

What is interesting about the first problem is that it passes the color test. It made me wonder: Is there a way to characterize the shapes on a square grid that pass the color test, but still can’t be covered in dominoes?

* * *

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.

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.

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 2ⁿ letters are generated from the first 2ⁿ 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 2^k+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 F_n + F_n-3 + F_n-5 + F_n-6. Bob will have F_n-1 + F_n-2 + F_n-4. We see that Alice gets more by F_n-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.

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?

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.