Archive for February 2011

## Puzzles for Lawyers

One day we may all face the necessity of hiring a lawyer. If the case is tricky the lawyer must be smart and inventive. I am collecting puzzles to give to a potential lawyer during an interview. The following puzzle is one of them. It was given at the second Euler Olympiad in Russia:

At a local Toyota dealership, you are allowed to exchange brand new cars. You can exchange three Camrys for one Prius and one Avalon, and three Priuses for two Camrys and one Avalon. Assuming an unlimited supply of cars at the dealership, can collector Vasya exchange 700 Camrys for 400 Avalons?

The beauty of this puzzle is that the answer I may find acceptable from a mathematician is not the same as I want from my future lawyer.

Have I intrigued you? Get to work and send me your solutions.

## Criminal Probability Theory

I am sitting in front of my computer and scheming, or, more precisely, scamming. I am inventing scams as a way of raising awareness of how probability theory can be used for deception.

My first scam is my lottery project. Suppose I create and run a private lottery. I will award minor payments to some participants, while promising a grand prize of one hundred million dollars. However, there will be a very small probability that anyone will win the big payout. My plan is to live lavishly on my proceeds, hoping no one ever wins the big ticket.

The beauty of this scheme is that nobody will complain until someone scores the top prize. After all, everyone has been receiving what I promised, and no one realizes my fraud. If nobody wins the big award until I retire, I will have built my life style on deception without having been caught.

Suppose someone wins the hundred million dollars. Oops. I am in big trouble. On the other hand, maybe I can avoid jail time. I could tell the winner that the money is gone and if s/he complains to the police, I will declare bankruptcy and we will all lose. Alternatively, I can suggest a settlement in exchange for silence. For example, we could share future proceeds. Probability theory will help me run this lottery with only a small chance of being exposed.

But even a small chance of failure will cause me too much stress, so I have come up with an idea for another scam. I will write some complicated mathematical formulas with which to persuade everyone that global warming will necessarily produce earthquakes in Boston in the near future. Then I’ll open an insurance company and insure everyone against earthquakes. As I really do not expect earthquakes in my lifetime, I can spend the money. I’ll just need to keep everyone scared about earthquakes. This time I can be sure that I won’t be caught as no one will have a reason to complain. The only danger is that someone will check my formulas and prove that I used mathematics to lie.

Perhaps I need a scam that covers up the lie better. Instead of inventing an impossible catastrophe, I need to insure against a real but rare event. Think Katrina. I collect the money and put aside money for payouts and pocket the rest. But I actually tweak my formulas and put aside less than I should, boosting my bank account. I will be wealthy for many years, until this event happens. I might die rich but if this catastrophe happens while I’m still alive, I’ll declare bankruptcy.

Though I was lying to everyone, I might be able to avoid jail time. I might be able to prove that it was an honest mistake. Mathematical models include some subjective parameters; besides, everyone believes that nature is unpredictable. Who would ever know that I rigged my formulas in my favor? I can claim that the theory ended up being more optimistic than reality is. Who could punish me for optimism?

Maybe I can be accused of lying if someone proves that I knew that the optimistic model doesn’t quite match the reality. But it is very difficult for the courts to punish a person for a math mistake.

When I started writing this essay, I wanted to write about the financial crisis of 2008. I ended up inventing scams. In a way, I did write about the financial crisis. My scams are simplified versions of what banks and hedge funds did to us. Will we ever see someone punished?

## Fermat’s Room

Most movies related to mathematics irritate me because of simplifications. I especially do not like when a movie pretends to be intelligent and then dumbs it down. I recently watched the Spanish movie Fermat’s Room, which, as you may guess, annoyed me several times. In spite of that I enjoyed it very much.

The movie opens with people receiving invitations to attend a meeting for geniuses. To qualify for the meeting they need to solve a puzzle. Within ten days, they must guess the order underlying the following sequence: 5, 4, 2, 9, 8, 6, 7, 3, 1. Right away, at the start of the movie, I was already annoyed because of the simplicity of the question. You do not have to be a genius to figure out the order, not to mention how easy it would be to plug this sequence into the Online Encyclopedia of Integer Sequences to find the order in five minutes.

The participants were asked to hide their real names, which felt very strange to me. All famous puzzle solvers compete in puzzle championships and mystery hunts and consequently know each other.

The meeting presumably targets the brightest minds and promises to provide “the greatest enigma.” During the meeting they are given seven puzzles to solve. All of them are from children’s books and the so-called “greatest enigma” could easily be solved by kids. Though I have to admit that these were among the cutest puzzles I know. For example:

There are three boxes: one with mint sweets, the second with aniseed sweets, and the last with a mixture of the two. The boxes are labeled, but all the labels are wrong. What is the minimum number of sweets you need to taste to correctly re-label all the boxes?

Another of the film’s puzzles includes a light bulb in a room and three switches outside, where you have to correctly find the switch that corresponds to the bulb, but you can only enter the room once. In another puzzle you need to get out of prison by deciding which of two doors leads to freedom. You are allowed to ask exactly one question to one of the two guards, one of whom is a truth-teller and the other is a liar.

The other four puzzles are similar to these three I have just described. To mathematicians they are not the greatest enigmas. They are nice material for a children’s math club. For non-mathematicians, they may be fascinating. Certainly it’s a good thing that such tasteful puzzles are being promoted to a large audience. But they just look ridiculous as “the greatest enigmas.”

The intensity of the movie comes from the fact that the people are trapped in a room that starts shrinking when they take more than one minute to solve a puzzle.

I well remember another shrinking room from Star Wars: A New Hope. When Princess Leia leads her rescuers to a room, it turns out to be a garbage compactor. The bad guys activate the compactor and two opposite walls start moving in. In contrast, Fermat’s room is shrinking in a much more sophisticated way: all four walls are closing in. Each of the walls in the rectangular room is being pressured by an industrial-strength press. The walls in the corners do not crumble, but rather one wall glides along another. I was more puzzled by this shrinking room than I was by the math puzzles. I recommend that you try to figure out how this can be done before seeing the movie or its poster.

However, the best puzzle in the movie is the plot itself. Though I knew all the individual puzzles, what happened in between grabbed me and I couldn’t wait to see what would happen next. I saw the movie twice. After the first time, I decided to write this review, so I needed to check it again. I enjoyed it the second time even better than the first time. The second time, I saw how nicely the plot twists were built.

Maybe I shouldn’t complain about the simplicity and the familiarity of the puzzles. If they were serious new puzzles I would have started solving them instead of enjoying the movie. The film’s weakness might be its strength.

## The Wizards’ Hats

I collect hats puzzles. A puzzle about hats that I hadn’t heard before appeared on the Konstantin Knop’s blog (in Russian):

The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat — for both of which he has an 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 on a strategy to maximize the number of survivors. Suggest a strategy for them.

I’ll start the discussion with a rather simple idea: Each wizard writes down a color randomly. In this case the expected number of survivors is 50. Actually, if each wizard writes “red”, then the expected number of survivors is 50, too. Can you find a better strategy, with a greater expected number of survivors or prove that such a strategy doesn’t exist?

As a bonus question, can you suggest a strategy that guarantees 50 survivors?

Now that you’ve solved that issue, here’s my own variation of the problem.

The wizards are all very good friends with each other. They decide that executions are very sad events and they do not wish to witness their friends’ deaths. They would rather die themselves. They realize that they will only be happy if all of them survive together. Suggest a strategy that maximizes the probability of them being happy, that is, the probability that all of them will survive.

## Mr. Jones

The following two problems appeared together in Martin Gardner’s Scientific American column in 1959.

Mr. Smith has two children. At least one of them is a boy. What is the probability that both children are boys?

Mr. Jones has two children. The older child is a girl. What is the probability that both children are girls?

Many people, including me and Martin Gardner, wrote a lot about Mr. Smith. In his original column Martin Gardner argued that the answer to the first problem is 1/3. Later he wrote a column titled “Probability and Ambiguity,” where he corrected himself about Mr. Smith.

… the answer depends on the procedure by which the information “at least one is a boy” is obtained.

This time I would like to ignore Mr. Smith, as I wrote a whole paper about him that is now under consideration for publication at the College Mathematics Journal. I would rather get back to Mr. Jones.

Mr. Jones failed to stir a controversy from the start and was forgotten. Olivier Leguay asked me about Mr. Jones in a private email, reminding me that the answer to the problem about his children also depends on the procedure.

One of the reasons Mr. Jones was forgotten is that for many natural procedures the answer is 1/2. For example, the following procedures will produce an answer of 1/2:

• We ask Mr. Jones whether his older child is a daughter and he says “yes.”
• Mr. Jones flips a coin deciding which child to talk about. After that he has to tell us the gender and whether the child is the oldest.
• Mr. Jones is asked to say nothing if he doesn’t have a daughter, to select the daughter if has just one, or to pick one at random if he has two daughters. After that he has to tell us whether the daughter he has selected is the oldest.

Suppose I know Mr. Jones, and also know that he has two children. I meet Mr. Jones at a mall, and he tells me that he is buying a gift for his older daughter. Most probably I would assume that the other child is a daughter, too. In my experience, people who have a son and a daughter would say that they are buying a gift for “my daughter.” Only people with two daughters would bother to specify that they are buying a gift for “my older daughter.”

In some sense I didn’t forget about Mr. Jones. I wrote about him implicitly in my essay Two Coins Puzzle. His name was Carl and he had two coins instead of two children.

## Tetrahedron Problems

My blog is getting more famous. Now I don’t need to look around for nice problems, for my readers often send them to me. In response to my blog about him, Sergey Markelov’s Best, Markelov sent me more of his problems. Here is a cute tetrahedron problem that he designed:

Six segments are such that you can make a triangle out of any three of them. Is it true that you can build a tetrahedron out of all six of them?

Another reader, Alexander Shen, sent me a different tetrahedron problem from a competition after reading my post on Problem Design for Multiple Choice Questions:

Imagine the union of a pyramid based on a square whose faces are equilateral triangles and a regular tetrahedron that is glued to one of these faces. How many faces will this figure have?

Shen wrote that the right answer to this problem had been rumored to have a negative correlation with the result of the entire test.

## 86 Conjecture

86 is conjectured to be the largest power of 2 not containing a zero. This simply stated conjecture has proven itself to be proof-resistant. Let us see why.

What is the probability that the nth power of two will not have any zeroes? The first and the last digits are non-zeroes; suppose that other digits become zeroes randomly and independently of each other. This supposition allows us to estimate the probability of 2n not having zeroes as (9/10)k-2, where k is the number of digits of 2n. The number of digits can be estimated as n log102. Thus, the probability is about cxn, where c = (10/9)2 ≈ 1.2 and x = (9/10)log102 ≈ 0.97. The expected number of powers of 2 without zeroes starting from the power N is cxN/(1-x) ≈ 40 ⋅ 0.97N.

Let us look at A007377, the sequence of numbers such that their powers of 2 do not contain zeros: 1, 2, 3, 4, 5, 6, 7, 8, 9, 13, 14, 15, 16, 18, 19, 24, 25, 27, 28, 31, 32, 33, 34, 35, 36, 37, 39, 49, 51, 67, 72, 76, 77, 81, 86. Our estimates predicts 32 members of this sequence starting from 6. In fact, the sequence has 30 conjectured members. Similarly, our estimate predicts 2.5 members starting from 86. It is easy to check that the sequence doesn’t contain any more numbers below 200 and our estimate predicts 0.07 members after 200. As we continue checking larger numbers and see that they do not belong to the sequence, the probability that the sequence contains more elements vanishes. With time we check more numbers and become more convinced that the conjecture is true. Currently, it has been checked up to the power 4.6 ⋅ 107. The probability of finding something after that is about 1.764342396 ⋅10-633620.

Let us try to approach the conjecture from another angle. Let us check the last K digits of powers of two. As the number of possibilities is finite, these last digits eventually will start cycling. If we can show that all the elements inside the period contain zeroes, then we need to check the finite number of powers of two until this period starts. If we can find such K, we can prove the conjecture.

Let us look at the last two digits of powers of two. The sequence starts as: 01, 02, 04, 08, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 04. As we would anticipate, it starts cycling. The cycle length is 20, and 90% of numbers in the cycle don’t have zeroes.

Now let’s continue to the last three digits. The period length is 100, and 19 of them either start with zero or contain zero. The percentage of elements in the cycle that do not contain zero is 81%.

The cycle length for the last n digits is known. It is 4 ⋅ 5n-1. In particular the cycle length grows by 5 every time. The number of zero-free elements in these cycles form a sequence A181610: 4, 18, 81, 364, 1638, 7371, 33170. If we continue with our supposition that the digits are random, and study the new digits that appear when we move from the cycle of the last n digits to the next cycle of the last n+1 digits, we can expect that 9/10 of those digits will be non-zero. Indeed, if we check the ratio of how many numbers do not contain zero in the next cycle compared to the previous cycle, we get: 4.5, 4.5, 4.49383, 4.5, 4.5, 4.50007. All of these numbers are quite close to our estimation of 4.5. If this trend continues the portion of the numbers in the cycle that don’t have zeroes tends to zero; however, the total of such numbers grows exponentially. We can even estimate that the expected growth is 4 ⋅ 4.5n-1. From this estimation, we can derive the conjecture:

Conjecture. For any number N, there exists a power of two such that its last N digits are zero-free.

Indeed, the last N digits of powers of two cycle, and there are an increasing number of members inside that cycle that do not contain zeroes. The corresponding powers of two don’t have zeroes among N rightmost digits.

So, how do we combine the two results? First, the expected probability of finding the power of two larger than 86 that doesn’t contain zero is minuscule. And second, we most certainly can find a power of two that has as many zeroless digits at the end as we want.

To combine the two results, let us look at the sequences A031140 and A031141. We can deduce from them that for the power 103233492954 the first zero from the right occupies the 250th spot. The total number of digits of that power is 31076377936. So 250 is a tiny portion of the digits.

As time goes by we grow more and more convinced that 86 is the largest power of two without zeroes, but it is not at all clear how we can prove the conjecture or whether it can be proven at all.

My son, Sergei, suggested that I claim that I have a proof of this conjecture, but do not have enough space in the margin to fit my proof in. The probability that I will ever be shamed and disproven is lower than the probability of me winning a billion dollars in the lottery. Though then, if I do win the big bucks, I will still care about being shamed and disproven.

## The Second IMO Gold Girl

Janet Mertz encouraged me to find IMO girls and compare their careers to that of their teammates. I had always wanted to learn more about the legendary Lida Goncharova — who in 1962 was the first girl to win an IMO gold medal. So I located her, and after an interview, wrote about her. Only 14 years later, in 1976, did the next girl get a gold medal. That was me. I was ranked overall second and had 39 points out of 40.

As I did in the article about Lida, I would like to compare my math career to that of my teammates.

I got my PhD in 1988 and moved to the US in 1990. My postdoc at MIT in 1993 was followed by a postdoc at Bar-Ilan University. In 1996 I got a non-paying visiting position at Princeton University. In 1998 I gave up academia and moved to industry, accepting an offer from Bellcore. There were many reasons for that change: family, financial, geographical, medical and so on.

On the practical level, I had had two children and raising them was my first priority. But there was also a psychological element to this change: my low self-esteem. I believed that I wasn’t good enough and wouldn’t stand a chance of finding a job in academia. Looking back, I have no regrets about putting my kids first, but I do regret that I wasn’t confident enough in my abilities to persist.

I continued working in industry until I resigned in January 2008, due to my feeling that I wasn’t doing what I was meant to do: mathematics. Besides, my children were grown, giving me the freedom to leave a job I did not like and return to the work I love. Now I am a struggling freelance mathematician affiliated with MIT. Although my math blog is quite popular and I have been publishing research papers, I am not sure that I will ever be able to find an academic job because of my non-traditional curriculum vitae.

The year 1976 was very successful for the Soviet team. Out of nine gold medals our team took four. My result was the best for our team with 39 points followed by Sergey Finashin and Alexander Goncharov with 37 points and by Nikita Netsvetaev with 34 points.

Alexander Goncharov became a full professor at Brown University in 1999 and now is a full professor at Yale University. His research is in Arithmetic Algebraic Geometry, Teichmuller Theory and Integral Geometry. He has received multiple awards including the 1992 European Math Society prize. Sergey Finashin is very active in the fields of Low Dimensional Topology and Topology of Real Algebraic Varieties. He became a full professor at Middle East Technical University in Ankara, Turkey in 1998. Nikita Netsvetaev is an expert in Differential Topology. He is a professor at Saint Petersburg State University and the Head of the High Geometry Department.

Comparing my story to that of Lida, I already see a pattern emerging. Now I’m curious to hear the stories of other gold-winning women. I believe that the next gold girl, in 1984, was Karin Gröger from the German Democratic Republic. I haven’t yet managed to find her, so can my readers help?