Masturbating With an Accent

I once took an accent reduction course, to modify my Russian accent in English. In the first class the teacher explained that the biggest reason people have strong accents is that they stop learning and trying to improve their speech as soon as they can be understood. I promised myself to never stop learning and to continue working on my accent reduction forever.

Once I was giving a lecture on probability and statistics at the IAP mathematical series. My last slide was about the research on the correlation between masturbation male habits and prostate cancer. Their interpretation of the data had been wrong and a very good example of what not to do.

So I looked directly into the eyes of the course coordinator, who was observing my lecture, and without realizing what I was saying, asked, “Do we have time for masturbation?”

Everyone started laughing and I had to present my slide in order to explain myself.

The news of my double entendre spread. Soon after that I was asked to give a lecture at the Family Weekend at MIT. I wonder if that is why the lecture coordinator asked me not to discuss masturbation as small children might be present.

Luckily that was the only fallout from my blooper. Anyway, I decided to stop working on my accent. When people understand that English is not my first language they forgive more readily my slips of tongue.


Computer Security Jokes

* * *

—Honey, have you blocked our computer?
—What’s the password?
—Our wedding date.

* * *

—What’s the pin on our card?
—We’re on a public chat, honey. Why don’t I sms it?
—But I forgot my phone. Please tell me, cupcake!
—Okay. By digit: the second digit of our apartment number, the fourth digit of your phone number, the month of my birthday, and the number of our children.
—Got it. How clever! 8342, right?

* * *

—Where is the report?
—We are stuck. The tech people took our monitor with passwords.
—Our monitor got broken so the techs took it for repair. Our passwords were written on the stand.


Hat Puzzle: Create a Distribution

Here is a setup that works for the several puzzles that follow it:

The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat—from his inexhaustible supply—on every wizard’s head. Each wizard will be able to see every hat but his own. The wizards will not be allowed to exchange any kind of information whatsoever. At the sultan’s signal, each wizard needs to write down the color of his own hat. Every wizard who guesses wrong will be executed. The wizards have one day to decide together on a strategy.

I wrote about puzzles with this setup before in my essay The Wizards’ Hats. My first request had been to maximize the number of wizards who are guaranteed to survive. It is easy to show that you cannot guarantee more than 50 survivors. Indeed, each wizard will be right with probability 0.5. That means whatever the strategy, the expected number of wizards guessing correctly is 50. My second request had been to maximize the probability that all of them will survive. Again, the counting argument shows that this probability can’t be more than 0.5.

Now here are some additional puzzles, including the first two mentioned above, based on the same setup. Suggest a strategy—or prove that it doesn’t exist—in which:

  1. 50 wizards will be guaranteed to survive.
  2. 100 wizards will survive with probability 0.5.
  3. 100 wizards will survive with probability 0.25 and 50 wizards will survive with probability 0.5.
  4. 75 wizards will survive with probability 1/2, and 25 wizards survive with probability 1/2.
  5. 75 wizards will survive with probability 2/3.
  6. The wizards will survive according to a given distribution. For which distributions is it possible?

As I mentioned, I already wrote about the first two questions. Below are the solutions to those questions. If you haven’t seen my post and want to think about it, now is a good time to stop reading.

To guarantee the survival of 50 wizards, designate 50 wizards who will assume that the total number of red hats is odd, and the rest of the wizards will assume that the total number of red hats is even. The total number of red hats is either even or odd, so one of the groups is guaranteed to survive.

To make sure that all of them survive together with probability 0.5, they all need to assume that the total number of red hats is even.


Linear Algebra on a Mission Impossible

I love making math questions out of the movies. Here is a Mission Impossible III question.

Tom Cruise is cute. He plays Ethan Hunt in Mission Impossible movies. In Mission Impossible III he needs to steal the Rabbit’s Foot from a secure skyscraper in Shanghai. He arrives in Shanghai and studies the skyscraper looking out his window. He decides to break in through the roof. And the way to get to the roof is to use a rope and swing across from another, even taller, skyscraper. 1:21 minutes into the movie, Ethan Hunt calculates the length of the rope he will need by using the projection of a skyline on his window, as seen on the first picture.

MI3 Skyline

Explain why the projection is not enough to calculate the length of the rope. What other data does he need for that? Ethan Hunt does request extra data. But he makes one mistake. He uses his pencil as a compass to draw the end of the rope curve, as seen on the second picture. Explain what his mistake is.

MI3 Rope


Nim Automaton

I mentor three PRIMES projects. One of them, with Joshua Xiong from Acton-Boxborough Regional High School, is devoted to impartial combinatorial games. We recently found a connection between these games and cellular automata. But first I need to remind you of the rules of Nim.

In the game of Nim there are several piles with counters. Two players take turns choosing a pile and removing several counters from it. A player loses when he or she who doesn’t have a turn. Nim is the most famous impartial combinatorial game and its strategy is well known. To win, you need to finish your move in a so called P-position. Nim P-positions are easy to calculate: Bitwise XOR the number of counters in all the piles, and if the result is zero then it’s a P-position.

The total number of counters in a P-position is even. So we calculated the sequence a(n): the number of P-positions in the game of Nim with three piles with the total number of counters equal to 2n. As soon as we got the sequence we plugged it into the OEIS, and voilà it was there: The sequence A130665 described the growth of the three branches of the Ulam-Warburton cellular automaton.

U-W automaton

The first picture shows the automaton after 6 generations. The automaton consists of cells that never die and it grows like this: start with a square on a square grid. In the next generation the squares that share exactly one side with the living squares are born. At the end remove the Southern branch.

Everything fell into place. We immediately realized that the language of the automata gives us the right words to describe what we know about the game of Nim.

Now we want to describe the automaton related to any impartial combinatorial game. Again, the cells never die and the initial cells correspond to terminal P-positions. People who write programs for calculating P-positions will find a notion of the next generation very natural. Indeed, the program usually starts with the terminal P-positions: they are generation 0. Then we can proceed by induction. Suppose we have found P-positions up to generation i. Denote the positions that are one move away from generation i and earlier as Ni. Then the P-positions that do not belong to generation i and earlier and from which all moves belong to Ni are the P-positions from generation i + 1.

This description explains the generations, but it doesn’t explain who is the parent of a particular P-position. The parent-child relations are depicted as edges on the cellular automaton graph. The parent of position P1 from generation i + 1 is a P-position P2 in generation i that can be reached from P1 in the game.

The parent-child relationship in the game of Nim is especially easy to explain. A P-position P1 is a parent of a P-position P2 if P1 differs from P2 in exactly two piles and it has one fewer counter in each of these piles. For example, a P-position (1,3,5,7) has six parents, one of them is (1,3,4,6). In the game with thee piles a P-position always has exactly one parent.

A position in the game of Nim with three piles is naturally depicted as a triple of numbers, that is as a point in 3D. The picture below shows the Nim automaton in 3D at generation 6.

Nim Automaton

Our paper, Nim Fractals, about sequences enumerating P-positions and describing the automaton connection in more detail is posted at the arXiv:1405.5942. We give a different, but equivalent definition of a parent-child relationship there. A P-position P1 is a parent of P2 if there exists an optimal game such that P1 is achieved from P2 in exactly two moves in a game which takes the longest number of possible moves.


Kolmogorov Student Olympiad in Probability

There are too many Olympiads. Now there is even a special undergraduate Olympiad in probability, called Kolmogorov Student Olympiad in Probability. It is run by the Department of Probability Theory of Moscow State University. I just discovered this tiny Olympiad, though it has been around for 13 years.

A small portion of the problems are accessible for high school students. These are the problems that I liked. I edited them slightly for clarity.

Second Olympiad. Eight boys and seven girls went to movies and sat in the same row of 15 seats. Assuming that all the 15! permutations of their seating arrangements are equally probable, compute the expected number of pairs of neighbors of different genders. (For example, the seating BBBBBBBGBGGGGGG has three pairs.)

Third Olympiad. One hundred passengers bought assigned tickets for a 100-passenger railroad car. The first 99 passengers to enter the car get seated randomly so that all the 100! possible permutations of their seating arrangements are equally probable. However, the last passenger decides to take his reserved seat. So he arrives at his seat and if it is taken he asks the passenger in his seat to move elsewhere. That passenger does the same thing: she arrives at her own seat and if it is taken, she asks the person to move, and so on. Find the expected number of moved passengers.

Third Olympiad. There are two 6-sided dice with numbers 1 through 6 on their faces. Is it possible to “load” the dice so that when the two dice are thrown the sum of the numbers on the dice are distributed uniformly on the set {2,…,12}? By loading the dice we mean assigning probabilities to each side of the dice. You do not have to “load” both dice the same way.

Sixth Olympiad. There are M green and N red apples in a basket. We take apples out randomly one by one until all the apples left in the basket are red. What is the probability that at the moment we stop the basket is empty?

Seventh Olympiad. Prove that there exists a square matrix A of order 11 such that all its elements are equal to 1 or −1, and det A > 4000.

Twelfth Olympiad. In a segment [0,1] n points are chosen randomly. For every point one of the two directions (left or right) is chosen randomly and independently. At the same moment in time all n points start moving in the chosen direction with speed 1. The collisions of all points are elastic. That means, after two points bump into each other, they start moving in the opposite directions with the same speed of 1. When a point reaches an end of the segment it sticks to it and stops moving. Find the expected time when the last point sticks to the end of the segment.

Thirteenth Olympiad. Students who are trying to solve a problem are seated on one side of an infinite table. The probability that a student can solve the problem independently is 1/2. In addition, each student will be able to peek into the work of his or her right and left neighbor with a probability of 1/4 for each. All these events are independent. Assume that if student X gets a solution by solving or copying, then the students who had been able to peek into the work of student X will also get the solution. Find the probability that student Vasya gets the solution.


IQ Migration

The Russian website has a big collection of math problems. I use it a lot in my work as a math Olympiad coach. Recently I was giving a statistics lesson. While there was only one statistics problem on the website, it was a good one.

Assume that every person in every country was tested for IQ. A country’s IQ rating is the average IQ of the population. We also assume that for the duration of this puzzle no one is born and no one dies.

  • A group of citizens of country A emigrated to B. Show that the rating of both countries can go up.
  • After that a group of citizens of B (which may include former citizens of A) emigrated to A. Is it possible that the ratings of both countries go up again?
  • A group of citizens of A emigrated to B, and a group of citizens of B emigrated to C. As a result, the ratings of each country increased. After that the migration went the opposite way: some citizens of C moved to B, and some citizens from B moved to A. As a result, the ratings of all three counties went up once more. Is this possible? If yes, then how? If no, then why not?

Math Kangaroo’s Logic Puzzle

My AMSA students loved the following puzzle from the 2003 Math Kangaroo contest for grades 7-8:

The children A, B, C and D made the following assertions.

  • A: B, C and D are girls.
  • B: A, C and D are boys.
  • C: A and B are lying.
  • D: A, B and C are telling the truth.

How many of the children were telling the truth?
A) 0   B) 1   C) 2   D) 3   E) Impossible to determine


Express 6

I was given this puzzle at the last Gathering for Gardner.

Use arithmetic operations to express 6 using three identical digits. For each digit from 0 to 9 find at least one way to express 6.

For example, I can express 6 using three twos in many ways: 2 + 2 + 2, or 2 · 2 + 2, or 22 + 2. But the problem doesn’t ask for many ways. One way is enough, but you need to do it for every digit. So nine more cases to go: 0, 1, 3, 4, 5, 6, 7, 8, and 9.


The Virtue of Laziness

My son, Alexey Radul, is a programmer. He taught me the importance of laziness in programming.

One of his rules:

Not to write the same line of code in the same program twice.

If you need the same line of code in the same program, that means you should either use a loop or outsource the line to a function. This style of coding saves time; it makes programs shorter and more elegant. Such programs are easier to debug and understand.

I remember how I copied and pasted lines of code before he taught me this rule. Then I needed to change parameters and missed some of the lines during changing. Debugging was such a headache.

Mathematicians are way lazier than programmers. Consider the system of two equations: x+2y=3 and 4x+5y=6. There are no repeating lines here. Only letters x and y appear twice. Mathematicians invented the whole subject of linear algebra and matrices so that they would not need to rewrite variables.

Mathematicians are driven by laziness. Once ancient mathematicians first solved a quadratic equation, they didn’t want to do it again. So they invented a formula that solves all quadratic equations once and for all.

I try to keep up with tradition. I try to make my theorems as general as possible. When I write my papers, I try to make them short and simple. When I think about mathematics I try to get to the stage where the situation is so clear I can think about it without paper and pencil. I often discover new theorems while I am in bed, about to fall asleep. Sometimes I wake up with a good idea. So I do my job while I sleep.

I love my profession. I get paid for being lazy.