Tanya Khovanova's Math Blog

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.

I am a milk person. I can easily drink half a gallon of milk a day. The problem with half a gallon of milk a day is that it is about half of my target calorie intake. That is why I switched to the reduced-fat milk. It didn’t taste good, but I was very proud of myself. That is, I was proud for about a year until I finally decided to read the labels. One serving of whole milk is 150 calories, while one serving of reduced-fat milk is 130 calories. All this year-long suffering saved me an insignificant 13%. Not to mention that the amount of sugar is the same.

I decided to look into this more closely. I went to my nearest super-market and checked the milk. The low-fat milk is 110 calories per serving, while non-fat milk is 90 calories.

If I had just reduced my milk intake by half, I would have consumed fewer calories than by replacing whole milk with non-fat milk, but I would have enjoyed it so much more. The lesson? Read the labels and do the math!

by John H. Conway as told to Tanya Khovanova

Forty years ago, it took about 18 months for us to find the rules that eventually became the Game of Life. We thought in terms of birth rules and death rules. Maybe one day’s death rule would be a bit too strong compared to its birth rule. So the next day at coffee time we’d either try to weaken the death rule or strengthen the birth rule, but either way, only by a tiny bit. They had to be extremely well-balanced; if the death rule was even slightly too strong then almost every configuration would die off. And conversely, if the birth rule was even a little bit stronger than the death rule, almost every configuration would grow explosively.

What’s wrong with that, you might ask. Well, if the “radius” grows by 1 unit per generation, then after 9 or 10 moves, it’s off the (19 by 19) Go board. We can probably find more Go boards, of course, but after another 20 or so moves it will outflow the coffee table and then it is awfully hard to keep track. We wanted to be able to study configurations for much longer than that, which meant that we had to disallow rules that might lead to linear growth. Of course, we weren’t interested in rules that usually led to collapse.

Who were “we”? Well, I was the chief culprit and had an aim in mind — to find a simple set of rules that would lead to a system able to simulate a universal computer. Von Neumann had already shown that this was possible, but his system had 29 states and a very complicated set of rules. The rest of “us” were mostly graduate students who had no higher aim than amusing themselves. Every now and then some rather older colleagues or visitors took an interest.

So my plan was, first, to find a set of rules that almost always prevented explosive growth and catastrophic collapse. Second, I wanted to study it long enough to learn how it could be “programmed”. I hoped to find a system whose rules were much simpler than Von Neumann’s, preferably with only two states (on and off) per cell, rather than his 29.

I’ll just describe the last few rule fiddles. We had in fact given up on finding a two-state system, in favor of one with three states: 0, A, B. State 0 represented an empty cell, and it was natural to think of A and B as two sexes, but we only found their proper names when Martin Huxley walked by and said, “Actresses and bishops!”

Perhaps I should explain this. There is a British anecdote that starts like this:

“The actress sat on the left side of the bed, and removed her stockings. The bishop, on the right side of the bed, removed his gaiters. Then she unbuttoned her blouse and he took off his shirt…”

You are supposed to be getting excited, but it all ends quite tamely, because it turns out that the bishop was in his palace, while the actress was in her bedsit near the theater. There are lots of stories in England about the actress and the bishop, and if a person says something that has a salacious double meaning, it’s standard to respond “as the actress said to the bishop,” or “as the bishop said to the actress”.

Okay, back to Life! To inhibit explosive growth, we decided to imitate biology by letting death be a consequence of either overcrowding or isolation. The population would only grow if the number of neighbors was neither too large nor too small. Rather surprisingly, this turned out to mean that children had to have three or more parents. Let’s see why. If two parents could give birth, then in the figure below, the parents A and B, who are on the border of the population, would produce children A’ and B’ at the next time step, followed by grandchildren A” and B” and so on, thus giving us linear growth!

So we moved to threesomes. Children were born to three parents, made up of both sexes. Moreover, the sex of the child was determined by the sex of its parents — two bishops and one actress would give birth to a little actress, while two actresses and one bishop would produce a tiny bishop. This was “the weaker-sex birth rule,” and it was accompanied by “the sexual frustration death rule,” which made death the punishment for not touching somebody of the opposite sex!

However, the weaker-sex birth rule lived up to its name, by being weaker than the death rule. Remember we weren’t interested in rules that led to disappointingly swift collapses, as the actress said to the bishop. Therefore, we strengthened the birth rule by allowing same-sex conception, but again by applying the weaker-sex rule — so that three actresses would produce a bishop or three bishops an actress. However this strengthened the birth rule too much, causing us to apply the death penalty more often.

We decided to apply the death penalty to those who weren’t touching at least two other people, whatever their sex. At first sight it was not obvious that this was stronger than the sexual frustration rule, but in fact it was, because the weaker-sex rule ensured that the sexes were fairly evenly mixed, so if you were touching at least two other people, there was a good chance that one of them would be of the opposite sex.

According to our new set of rules, the sex of parents played no role except to determine the sex of the children, so we abolished sex. After all, according to the bishop, Life without sex is much cleaner.

This is now called the Game of Life and these rules, at last, turned out to be clean and well-balanced.

by Rebecca Frankel

The article Daring to Discuss Women in Science by John Tierney in the New York Times on June 7, 2010 purports to present a dispassionate scientific defense of Larry Summers’s claims, in particular by reviewing and expanding his argument that observed differences in the length of the extreme right tail of the bell curves of men’s and women’s test scores indicate real differences in their innate ability. But in fact any argument like this has to acknowledge a serious difficulty: it is problematic to assume without comment that the abilities of a group can be inferred from the tail of a bell curve. We are so used to invoking bell curves to talk about group abilities, we don’t notice that such arguments usually use only the mean of the curve. Using the tail is a totally different story.

Think about it: it is reasonable to question whether a single data point — the test score of an individual person — is a true indication of his/her ability. It might not be. Maybe a single test score represents a dunce with hyper-overachieving parents who push him to study all the time. So does that single false reading destroy the validity of the curve? No of course not: because some other kid might have been a super-genius who was drunk last night and can barely keep his eyes open during the test. One is testing above his “true ability” and the other is testing below his “true ability,” and the effect cancels out. Thus the means of curves are a good way to measure the ability of large groups, because all the random false readings average out.

But tails are not. On the tail this “canceling out” effect doesn’t work. Look at the extreme right tail. The relatively slow but hyper-motivated kids are not canceled out by the hoard of far-above-the-mean super geniuses who had drunken revels the night before. There just aren’t that many super-geniuses and they just don’t party that much.

Or let’s look at it another way: imagine that you had a large group which you divided in half totally at random. At this point their bell curve of test scores looks exactly the same. Lets call one of the group “boys” and the other group “girls”. But they are two utterly randomly selected groups. Now lets inject the “boys” with a chemical that gives the ones who are very good already a burning desire to dominate any contest they enter into. And let us inject the “girls” with a chemical that makes the ones who are already good nonetheless unwilling to make anyone feel bad by making themselves look too good. What will happen to the two bell curves? Of course the upper tail of the “boys'” curve will stretch out, while the “girls'” tail will shrink in. It will look like the “boys” whipped the “girls” on the right tail of ability hands down, no contest. But the tail has nothing to do with ability. Remember they started out with the same distribution of abilities, before they got their injections. It is only the effect of the chemicals on motivation that makes it look like the “boys” beat the “girls” at the tail.

So, when you see different tails, you can’t automatically conclude that this is caused by difference in underlying innate ability. It is possible that other factors are at play — especially since if we were looking to identify these hypothetical chemicals we might find obvious candidates like “testosterone” and “estrogen”.

The possibility of alternative explanations for these findings calls into question Tierney and Summers’ claims to superior dispassionate scientific objectivity. Moving from the mean to the tail of a bell curve makes systematic effects on averages irrelevant, true, but it is instead susceptible to systematic effects on deviations, which are irrelevant at the mean. An argument that uses this trick to dodge gender differences in averages cannot claim the mantle of scientific responsibility without accounting for gender differences in deviations. I am deeply disappointed that Tierney and Summers did not accompany their assertions with a suitable reminder of this fact.

I recently published a puzzle about wizards, hats of different colors and rooms. Unfortunately, I was too succinct in my description and didn’t explicitly mention several assumptions. Although such assumptions are usual in this type of puzzle, I realize now, from your responses, that I should have listed them and I apologize.

The Sultan decided to test the wisdom of his wizards. He collected them together and gave them a task. Tomorrow at noon he will put hats of different colors on each of the wizard’s heads.
The wizards have a list of the available colors. There are enough hats of each color for every wizard. The wizards also have a list of rooms. There are enough rooms to assign a different room for every color.
Tomorrow as the Sultan puts hats on the wizards, they will be able to see the colors of the hats of the other wizards, but not the color of their own. Without communicating with each other, each wizard has to choose a room. The challenge comes when two wizards have the same hat color, for they must choose the same room. On the other hand, if they have different hat colors, they must choose different rooms. Wizards have one day to decide on their strategy. If they do not all complete their task, then all of their heads will be chopped off. What strategy would you suggest for the wizards?

In his comment on the first blog about this problem, JBL beautifully described the intended solution for the finite number of wizards, and any potentially-infinite number of colors. I do not want to repeat his full solution here. I would rather describe his solution for two wizards and two colors.

Suppose the colors are red and blue. The wizards will designate one of the rooms as red and another as blue. As soon as each wizard sees the other wizard’s hat color, he chooses the room of the color he sees. The beauty of this solution is that if the colors of hats are different, the color of the rooms will not match the color of the corresponding hats: the blue-hatted wizard will go to the red room and vice versa. But the Sultan’s condition would still be fulfilled.

JBL’s solution doesn’t work if the number of wizards is infinite. I know the solution in that case, but I do not like it because it gives more power to the axiom of choice than I am comfortable with. If you are interested, you can extrapolate the solution from my essay on Countable Wise Men with Hats which offers a similar solution to a slightly different problem.