Tanya Khovanova's Math Blog

I heard this problem many years ago when I was working for Math Alive.

Three men are fighting in a truel. Andrew is the worst shot; he misses 2/3 of the time. Bob is better; he misses 1/3 of the time. Connor is the best shot; he always hits. Each of the three men have an infinite number of bullets. Each shot is either a kill or a miss. They have to shoot at each other in order until two of them are dead. To make it more fair they decide to start with Andrew, followed by Bob, and then Connor. We assume that they choose their strategies to maximize their probability of survival. At whom should Andrew aim for his first shot?

This is a beautiful probability puzzle, and I will not spoil it for you by writing a solution. Recently, I watched an episode of Numb3rs: The Fifth Season (“Frienemies”) which featured a version of this puzzle. Here is how Dr. Marshall Penfield, a frienemy of the protagonist Charlie Eppes, describes it:

Imagine a duel between three people. I’m the worst shot; I hit the target once every three trials. One of my opponents [Charlie] is better; hits it twice every three shots. The third guy [Colby] is a dead shot; he never misses. Each gets one shot. As the worst I go first, then Charlie, then Colby. Who do I aim for for my one shot?

This is a completely different problem; it’s no longer about the last man standing. Colby doesn’t need to shoot since the other two truelists have already expended their only shots. If Charlie believes that Colby prefers nonviolence, all else being equal, then Charlie doesn’t need to shoot. Finally, the same is true of Marshall. There is no point in shooting at all.

To make things more mathematically interesting, let’s assume that the truelists are bloodthirsty. That is, if shooting doesn’t decrease their survival rate, they will shoot. How do we solve this problem?

If he survives, Colby will kill someone. If Charlie is alive during his turn, he has to shoot Colby because Colby might kill him. What should Marshall do? If Marshall kills Colby, then Charlie misses Marshall (hence Marshall survives) with probability 1/3. If Marshall kills Charlie, then Marshall is guaranteed to be killed by Colby, so Marshall survives with probability 0. If he doesn’t kill anyone, things look much better: with probability 2/3, Colby is killed by Charlie and Marshall survives. Even if Colby is alive, he does not necessarily shoot Marshall, so Marshall survives with probability at least 2/3. Overall, Marshall’s chances of staying alive are much better if he misses. He should shoot in the air!

The sad part of the story is that Charlie Eppes completely missed. That is, he completely missed the solution. In the episode he suggested that Marshall should shoot Charlie. If Marshall shoots Charlie, he will be guaranteed to die.

It is disappointing that a show about math can’t get its math right.

From the 1966 Moscow Math Olympiad:

Prove that you can choose six weights from a set of weights weighing 1, 2, …, 26 grams such that any two subsets of the six have different total weights. Prove that you can’t choose seven weights with this property.

Let us define the sequence a(n) to be the largest size of a subset of the set of weights weighing 1, 2, …, n grams such that any subset of it is uniquely determined by its total weight. I hope that you agree with me that a(1) = 1, a(2) = 2, a(3) = 2, a(4) = 3, and a(5) = 3. The next few terms are more difficult to calculate, but if I am not mistaken, a(6) = 3 and a(7) = 4. Can you compute more terms of this sequence?

Let’s see what can be said about upper and lower bounds for a(n). If we take weights that are different powers of two, we are guaranteed that any subset is uniquely determined by the total weight. Thus a(n) ≥ log₂n. On the other hand, the total weight of a subset has to be a number between 1 and the total weight of all the coins, n(n+1)/2. That means that our set can have no more than n(n+1)/2 subsets. Thus a(n) ≤ log₂(n(n+1)/2).

Returning back to the original problem we see that 5 ≤ a(26) ≤ 8. So to solve the original problem you need to find a more interesting set than powers of two and a more interesting counting argument.

Fifteen years ago I attended Silvio Micali‘s cryptography course. During one of the lectures, he asked me to close my eyes. When I did, he wrote a random sequence of coin flips of length six on the board and invited me to guess it.

I am a teacher at heart, so I imagined a random sequence I would write for my students. Suppose I start with 0. I will not continue with zero, because 00 looks like a constant sequence, which is not random enough. So my next step would be sequence 01. For the next character I wouldn’t say zero, because 010 seems to promise a repetitive pattern 010101. So my next step would be 011. After that I do not want to say one, because I will have too many ones. So I would follow up with 0110. I need only two more characters. I do not want to end this with 11, because the result would be periodic, I do not want to end this with 00, because I would have too many zeroes. I do not want to end this with 01, because the sequence 011001 has a symmetry: reversing and negating this sequence produces the same sequence.

During the lecture all these considerations happened in the blink of an eye in my mind. I just said: 011010. I opened my eyes and saw that Micali had written HTTHTH on the board. He was not amused and may even have thought that I was cheating.

Many teachers, when writing a random sequence, do not flip a coin. They choose a sequence that looks “random”: it doesn’t have too many repetitions and the number of ones and zeroes is balanced (that is, approximately the same). When they write it character by character on the board, they often choose a sequence so that any prefix looks “random” too.

As a result, the sequence they choose stops being random. Actually, they’re making a choice from a small set of sequences that look “random”. So the fact that I guessed Micali’s sequence is not surprising at all.

If you have gone to many math classes, you’ve seen a lot of professors choosing very similar-looking “random” sequences. This discriminates against sequences that do not look “random”. To restore fairness to those under-represented sequences, I have decided that the next time I need a random sequence, I will choose 000000.

Two month ago I made a minor rearrangement of my math humor page. The traffic to that page tripled. Would you like to know what I did? I collected all the suggestive jokes in one chapter and named it Dirty Math Jokes.

Mathematics is so far from sex that stumbling on a math sex joke is always a special treat.

Combinatorialists do it discretely.

When those jokes were randomly placed in my joke file, it was easy to miss flirtatious connotations.

She was only a mathematician’s daughter, and she sure learned how to multiply using square roots.

So I decided to collect them together in one place.

Math Problem: A mother is 21 years older than her son. In 6 years she will be 5 times as old as her son. Where is the father?

Sergei Bernstein and Nathan Benjamin brought back a variation of the “Rock, Paper, Scissors” game from the Mathcamp. They call it “Rock, Paper, Scissor.” In this variation one of the players is not allowed to play Scissors. The game ends as soon as someone wins a turn.

Can you suggest the best strategy for each player?

They also invented their own variation of the standard “Rock, Paper, Scissors.” In their version, players are not allowed to play the same thing twice in a row.

If there is a draw, then it will remain a draw forever. So the game ends when there is a draw. The winner is the person who has more points.

They didn’t invent a nice name for their game yet, so I am open to suggestions.

Let me describe a variation of Nim that is at the same time a variation of Chomp. Here’s a reminder of what Nim and Chomp are.

In the game of Nim, there are several piles of matches and two players. Each of the players, in turn, can take any number of matches, but those matches must come from the same pile. The person who takes the last match wins. Some people play with a different variation in which the person who takes the last match loses.

Mathematicians do not differentiate between these two versions since the strategy is almost the same in both cases. The classic game of Nim starts with four piles that have 1, 3, 5 and 7 matches. I call this configuration “classic” because it is how Nim was played in one of my favorite movies, “Last Year at Marienbad”. Recently that movie was rated Number One by Time Magazine in their list of the Top 10 Movies That Mess with Your Mind.

In the game of Chomp, also played by two people, there is a rectangular chocolate bar consisting of n by m squares, where the lowest left square is poisoned. Each player in turn chooses a particular square of the chocolate bar, and then eats this square as well as all the squares to the right and above. The player who eats the poisonous square loses.

Here is my Nim-Chomp game. It is the game of Nim with an extra condition: the piles are numbered. With every move a player is allowed to take any number of matches from any pile, with one constraint: after each turn the i-th pile can’t have fewer matches than the j-th pile if i is bigger than j.

That was a definition of the Nim-Chomp game based on the game of Nim, so to be fair, here is a definition based on the game of Chomp. The game follows the rules of Chomp with one additional constraint: the squares a player eats in a single turn must all be from the same row. In other words, the chosen square shouldn’t have a square above it.

The game of Nim is easy and its strategy has been known for many years. On the other hand, the game of Chomp is very difficult. The strategy is only known for 2 by m bars. So I invented the game of Nim-Chomp as a bridge between Nim and Chomp.

More and more I stumble upon the claim that the difference in individual personal choices between men and women is one of the main contributors to the gender gap in mathematical careers. Let me tell you some stories that I’ve heard that illustrate some choices that women made. The names have been changed.

Ann got her PhD in math at the same time as her husband. They both got job offers at places very far from each other. As Ann was pregnant, she decided not to accept her offer and to follow her husband. In two years she was ready to go back to research and she started to search for some kind of position at the University where her husband worked. At that time there was a nuptial rule that prevented two spouses from working at the same place. There was no other college nearby, and Ann’s husband didn’t yet have tenure and freaked out at the thought of changing his job. They decided to have a second child. After two more years of staying home, she felt completely disqualified and dropped the idea of research.

Olga was very passionate about her children’s education. She felt that public education was insufficient and that parents needed to devote a lot of time to reading and playing with their kids. Her husband insisted that the children would be fine on their own and he refused outright to read to them or to participate in time-consuming activities. Olga took upon herself the burden she was hoping to share. At that same time, she started a tenure track position. In addition to all of this, she took her teaching very seriously. Her students loved her, but her paper-writing speed declined. She didn’t get tenure and quit academia. Later, she realized that in fact her husband had shared her sense of the importance of their children’s education, but he had played a power-game which left her doing all the work.

Maria told her husband Alex that she wanted a babysitter for their two children now that she was ready to get back to mathematics. Alex sat down with her to look at their finances. Before looking for a job Maria needed to finish her two papers. That meant they had to pay a babysitter even though Maria wasn’t bringing in any money. Maria agreed to postpone her comeback until the kids went to kindergarten. She somehow finished her papers and found her first part-time job as an adjunct lecturer. Alex sat down with her again to discuss their finances. They calculated how much time she would need to prepare to teach after such a long break. The babysitter would cost more than her income. In addition, they would have to buy a second car and some professional clothes for Maria. They summed everything up: it appeared that they couldn’t afford for her to take this job. Maria rejected the offer.

Two years later, Alex was offered an additional job as a part-time mathematical consultant. Instead of accepting it Maria’s husband suggested that the company interview Maria, who was longing to return to work. Maria got an offer, but at half the fee her husband was offered. The manager explained this difference by pointing to her husband’s superior work record. Maria and Alex sat down together again and calculated that it would more profitable for them as a couple if he took the job and dropped all his household responsibilities. Maria couldn’t find a way to argue.

I recently wrote about my own decision to quit academia twelve years ago. Although what I really wanted to do was to work in academia, my family responsibilities took precedence.

Yes, personal choices are a great contributor to the gender gap in mathematical careers. I just do not like when people assume that women chose freely. Some choices we were cornered into making.

by David Wilson

I was somewhat taken aback by the popularity of my earlier essay “Divisibility by 7 is a Walk on a Graph.” Tanya tells me it got a good number of hits. The graph in that article is rather crude, and takes a bit of care to use, because the arrows go off in random directions from each node. So taking a hint from a commenter on the first graph, I redrew the graph, sacrificing planarity in favor of ease of use. Specifically, I arranged the black arrows in a counterclockwise circle, which makes them easy to follow.

The graph is used in the same way as the first graph. To find the remainder on dividing a number by 7, start at node 0, for each digit D of the number, move along D black arrows (for digit 0 do not move at all), and as you pass from one digit to the next, move along a single white arrow.

For example, let n = 325. Start at node 0, move along 3 black arrows (to node 3), then 1 white arrow (to node 2), then 2 black arrows (to node 4), then 1 white arrow (to node 5), and finally 5 black arrows (to node 3). Finishing at node 3 shows that the remainder on dividing 325 by 7 is 3.

I fancy it to be a little animal face.