Tanya Khovanova's Math Blog

I remember a math problem from my childhood: divide an L-shaped triomino into four congruent parts. The answer is in the picture on the left. Such division is quite appropriately called a reptile (repetitive tiling). Solomon Golomb invented the name many years ago. He wasn’t aware that his definition would end up creating Googling problems, for when you search for such a mathematical object you will stumble upon a lot of amphibians.

Similarly, you can divide the same shape into 9 congruent pieces (see the figure on the left).

Suppose you want to divide a shape into pieces that are similar, but not necessarily of the same size. Such tiling is called an irreptile (irregular reptile).

At the Gathering for Gardner 9 I listened to Carolyn Yackel‘s talk about the L-reptiles and L-irreptiles. One of the ways to create an irreptile is to start with a reptile, then to make a sub-tiling of one of the existing tiles. This procedure can be repeated many times.

Carolyn brought a ceramic table to the Gathering for Gardner. This table is made of two L-shapes. Both shapes are irreptiles, created by this procedure. In one part of the table she started with a 9-reptile, and in the other with a 4-reptile. She sent me this picture of her table to use in this essay.

After her talk I started wondering how many tiles can an L-irreptile be comprised of. We start with one piece: the L-shape itself. If we divide a tile into four smaller tiles we add three more pieces. If we divide it into nine tiles we add eight more pieces. We can mix sub-dividing into four and nine tiles. The total number of tiles that an L-shape can be comprised of by this procedure is all the numbers you can get from 1 by adding three or eight. The sequence is 1, 4, 7, 9, 10, 12, 13, 15, 16, 17 and so on. Starting from 15 we get all the consecutive numbers.

The numbers that are not represented in the above sequence are 2, 3, 5, 6, 8, 11 and 14. Can we divide an L-shape into such numbers of tiles? Benoît Jubin reminded me that there is an L-reptile with six pieces.

Consequently, we can add 5 more pieces to any L-irreptile. Thus, there exists an L-irreptile made out of 11 (1+5+5) and out of 14 (1+8+5) pieces. The numbers that are left are 2, 3, 5 and 8.

While I was discussing L-irreptiles with fans of sequences, David Wilson suggested a conjecture.

David Wilson’s conjecture. If there is an L-irreptile, there is a corresponding square-irreptile with similarly-sized pieces.

If this conjecture is true, then we can see that L-irreptiles with 2, 3 or 5 pieces can’t exist as corresponding square-irreptiles do not exist.

For example, to prove that 2 or 3 square-irreptiles can’t exist, you need to notice that each corner of the square we are trying to tile should belong to a different small tile.

The question of the existence of an 8-irreptile of the L-shape is more interesting and challenging. The square 8-irreptile exists. If you can prove that the L-shape 8-irreptile doesn’t exist, then you will automatically prove that the converse to Wilson’s conjecture is not true.

by Tanya Khovanova, Konstantin Knop, Alexey Radul and Peter Sarnak

Let n coins weighing 1, 2, … n be given. Baron Münchhausen knows which coin weighs how much, but his audience does not. Define a(n) to be the minimum number of weighings the Baron must conduct on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins.

In the paper Baron Münchhausen’s Sequence, three of us completely described the Baron’s sequence. In particular, we proved that a(n) ≤ 2. Here we would like to outline another proof idea, which is interesting in part because it touches the Riemann hypothesis.We denote the total weight of coins in some set A as |A|.

Lemma. Numbers n that can be represented as T_i + T_j + T_k = 3n, where i ≤ j < k, such that there is a subset A of coins from j + 1 to k such that n = T_j + |A|, can be done in two weighings.

Proof. Suppose T_i + T_j + T_k = 3n and there is a subset A of coins from j + 1 to k such that n = T_j + |A|. We propose the two weighings

[1…j] + A = n

and

[1…i] + B = n + A,

where B is the complement of A in {j + 1, j + 2, … , k}.

If we sum up twice the first weighing with the second weighing we get

3[1…i] + 2[(i + 1)…j] + 2A + B = 3n + A.

In other words, three times the weight of the coins that were on the left side in both weighings, plus twice the weight of the coins that were on the left side in only the first weighing, plus the weight of the coins that were moved from the left cup to the right cup plus the weight of the coins on the left cup in only the second weighing equals three times the weight of the coin on the right cup in both weighings. Hence three times the weight of the coin on the right cup in both weighings can’t be less than the weight of the k other coins that participated plus the weight of the j coins that were on the left cup in the first weighing and weren’t moved to the right cup, plus the weight of the i coins that were one the left cup in both the first and the second weighing. But because T_i + T_j + T_k = 3n, then 3n is the smallest possible weight of any set of i plus j plus k coins, the coin on the right cup in both weighings has to be the n-coin.

We checked that any number up to 600,000 except 20 can be represented so as to satisfy the Lemma. To show how to solve 20 coins in two weighings is easy, and, as usual, is left as an exercise for the reader. Next, we want to look at the following lemma.

Lemma. Given a set of consecutive numbers {(j + 1), … , k}, if k > 2j + 2, then it is possible to find a subset in the set that sums up to any number in the range from j + 1 to (j + k + 1)(k – j)/2 – j – 1.

We won’t prove the lemma, but it means that if k is about twice larger than j, then we have a lot of flexibility for building our set A in the weighing above. For moderately large n (where 600000 >> “moderately large”), it is not hard to prove that this flexibility is sufficient.

Now the question becomes: can we find such a decomposition into triangular numbers? It is enough to find a representation T_i + T_j + T_k = 3n, where T_k is at least 81% of 3n.

We know that decompositions into triangular numbers are associated with decompositions into squares. Namely, if T_i + T_j + T_k = 3n, then (2i + 1)² + (2j + 1)² + (2k + 1)² = 24n + 3. If the largest square is at least 81% of 24n + 3, then the largest triangular number in the decomposition of 3n is at least 81%.

There is a theorem (W. Duke, Hyperbolic distribution problems and half-integral weight Maass forms, in Inventiones Math 92 (1988) p.73-90) that states that in the limit the decompositions of numbers into three squares are equidistributed. That is, if we take some region on the unit sphere x² + y² + z² = 1 (for example, the region |z| > 0.8) and view decompositions of 24n + 3 into squares as points on the sphere x² + y² + z² = 24n + 3, then, as n grows, decompositions whose projections fall into our chosen region are guaranteed to appear.

This theorem is great, because it tells us that for large enough n we will always be able to find a decomposition of 24n + 3 into triangle numbers where one of the triangle numbers will be much bigger than the others, and it will be possible to prove the weight of the n coin in two weighings. Unfortunately, this summary, as stated, does not tell us how large that n needs to be. So we need some exact estimates.

The number of decompositions of m into sums of three squares is about the square root of m. More precisely, it is possible to compute a number N, such that for any number m > N, with at most one exception, the number of decompositions is at least Cm^1/2−1/30, where C is a known constant.

The more specific statement of Duke’s theorem is that if the number of solutions to the quadratic x² + y² + z² = 24n + 3 is large, for a computable value of “large”, then the solutions are equidistributed. More precisely, let us denote 3n by m and fix an area Ω on the unit sphere. Then the number of solutions (x, y, z) such that the unit vector (x, y, z)/|(x, y, z)| belongs to Ω is

1/(4π) Ωh(8m+3) + E(m),

where h(8m+3) is the total number of solutions of x² + y² + z² = 24n + 3, and E(m) is an error term, which starting from some number satisfies the inequality: E(m) ≤ 1000m^1/2-1/7.

That’s pretty good, because combining these two lets us, at least in principle, actually calculate an N such that for all n > N except maybe one a(n) = 2. After that we hoped to write a program to exhaustively search smaller numbers by computer.

This situation is still somewhat annoying, because that possible exception must then be propagated into the proof, and if we are not careful, possibly into the final theorem. (“No matter how many coins the Baron has, he can prove the weight of one in at most two weighings, except maybe one number of coins, and we don’t know which…”) This is where the Riemann Hypothesis comes in. If the Riemann Hypothesis is true, then that exception isn’t there, and all is sunlight and flowers.

The beauty of the Baron’s puzzle is such that we actually do not need the Riemann hypothesis. As we can use unbalanced weighings, it is enough to find a good decomposition for one out of the four numbers 3n, 3n-1, 3n-2, or 3n-3.

Instead of finding all these exact estimates we found a different elementary proof of our theorem. But we are excited that methods that are used in very advanced number theory can be used to solve a simple math problem that can be described to middle school children.

It would be great if someone decided to finish this proof.

I just invented a two-player game. To start, you have an empty n by n board. When it’s your turn you must write an integer between 1 and n into an empty cell on the board. Your integer has to differ from the integers that are already present in the same row or column. If you finish filling up the board, you will get a Latin square and the game will be a tie. The person who doesn’t have a move loses. What is the best strategy?

Let’s see what happens if n is 2. The first player puts any number in one of the four corners of the 2 by 2 board. The second player wins by placing a different number in the opposite corner.

I played this game with my son Sergei Bernstein on a 3 by 3 board. We discovered that the first player can always win. Since this game is so much fun, I’ll leave it to the reader to play it and to find the winning strategy for the first player.

Can you analyze bigger boards? Remember that this game has many symmetries. You can permute rows and columns. Also, you can permute numbers.

While we were playing Sergei invented two theorems.

Sergei’s theorem 1. If n is odd the first player can guarantee a tie.

Proof. In the first move the first player writes (n+1)/2 in the center cell. If the second player puts number x in any cell the first player puts number n+1−x into the cell that is rotationally symmetric to the second player’s cell with respect to the center. With this strategy the first player will always have a legal move.

Sergei’s theorem 2. If n is even the second player can guarantee a tie.

Proof. If the first player puts number x in any cell the second player puts number n+1−x into the cell that is vertically symmetric to the first player’s cell with respect to the vertical line of symmetry of the board. With this strategy the second player will always have a legal move.

As you play the game, let me know if you develop any theorems of your own.

Suppose you meet a friend who you know for sure has two children, and he says: “I have a son born on Tuesday.” What is the probability that the second child of this man is also a son?

People argue about this problem a lot. Although I’ve discussed similar problems in the past, this particular problem has several interesting twists. See if you can identify them.

First, let us agree on some basic assumptions:

1. Sons and daughters are equally probable. This is not exactly true, but it is a reasonable approximation.
2. For our purposes, twins do not exist. Not only is the proportion of twins in the population small, but because they are born on the same day, twins might complicate the calculation.
3. All days of the week are equally probable birthdays. While this can’t actually be true — for example, assisted labors are unlikely to be scheduled for weekends — it is a reasonable approximation.

Now let us consider the first scenario. A father of two children is picked at random. He is instructed to choose a child by flipping a coin. Then he has to provide information about the chosen child in the following format: “I have a son/daughter born on Mon/Tues/Wed/Thurs/Fri/Sat/Sun.” If his statement is, “I have a son born on Tuesday,” what is the probability that the second child is also a son?

The probability that a father of two daughters will make such a statement is zero. The probability that a father of differently-gendered children will produce such a statement is 1/14. Indeed, with a probability of 1/2 the son is chosen over the daughter and with a probability of 1/7 Tuesday is the birthday.

The probability that a father of two sons will make this statement is 1/7. Among the fathers with two children, there are twice as many who have a son and a daughter than fathers who have two sons. Plugging these numbers into the formula for calculating the conditional probability will give us a probability of 1/2 for the second child to also be a son.

Now let us consider the second scenario. A father of two children is picked at random. If he has two daughters he is sent home and another one picked at random until a father is found who has at least one son. If he has one son, he is instructed to provide information on his son’s day of birth. If he has two sons, he has to choose one at random. His statement will be, “I have a son born on Mon/Tues/Wed/Thurs/Fri/Sat/Sun.” If his statement is, “I have a son born on Tuesday,” what is the probability that the second child is also a son?

The probability that a father of differently-gendered children will produce such a statement is 1/7. If he has two sons, the probability will likewise be 1/7. Among the fathers with two children, twice as many have a son and a daughter as have two sons. Plugging these numbers into the formula for calculating the conditional probability gives us a probability of 1/3 for the second child to also be a son.

Now let us consider the third scenario. A father of two children is picked at random. If he doesn’t have a son who is born on Tuesday, he is sent home and another is picked at random until one who has a son that was born on Tuesday is found. He is instructed to tell you, “I have a son born on Tuesday.” What is the probability that the second child is also a son?

The probability that a father of two daughters will have a son born on Tuesday is zero. The probability that a father of differently-gendered children will have a son who is born on Tuesday is 1/7. The probability that a father of two sons will have a son born on Tuesday is 13/49. Among the fathers with two children, twice as many have a son and a daughter than two sons. Plugging these numbers into the formula for calculating the conditional probability will give us a probability of 13/27 for the second child to also be a son.

Now let’s go back to the original problem. Suppose you meet your friend who you know has two children and he tells you, “I have a son born on Tuesday.” What is the probability that the second child is also a son?

What puzzles me is that I’ve never run into a similar problem about daughters or mothers. I’ve discussed this math problem about these probabilities with many people many times. But I keep stumbling upon men who passionately defend their wrong solution. When I dig into why their solution is wrong, it appears that they implicitly assume that if a man has a daughter and a son, he won’t bother talking about his daughter’s birthday at all.

I’ve seen this so often that I wonder if this is a mathematical mistake or a reflection of their bias.

How to solve the original problem? The problem is under-defined. The solution depends on the reason the father only mentions one child, or the Tuesday.

The funny part of this story is that I, Tanya Khovanova, have two children. And the following statement is true: “I have a son born on Tuesday.” What is the probability that my second child is a son?

How many different months’ lengths are possible?

For “simplicity” let’s stick to the Gregorian calendar.

Lennart Green is an amazing magician who performs card tricks. He is so good that the judges at the competition of the International Federation of Magic Societies didn’t believe his tricks. They assumed that he used the help of stooges, and unfairly disqualified him. At the next competition he used a judge to assist him and won first place in the cards category.

I saw his performance twice. Both times he brought a woman to the stage, but each time it was a different woman. It was clear that he talked to each woman before the performance, presumably asking her permission. Furthermore, during his performances, both of the women looked slightly bored, implying that it might be not their first time. My first impression was that the women were a part of the act. I was fooled just as the judges had been fooled.

What can I say? Lennart Green isn’t skilled at picking up the right women. Watch his performance at TED, and remember that he proved that the assistants were clueless.

I got this problem from my friend, a middle-school math teacher, Tatyana Finkelstein.

We have N coins that look identical, but we know that exactly one of them is fake. The genuine coins all weight the same. The fake coin is either lighter or heavier than a real coin. We also have a balance scale.
Unlike in classical math problems where you need to find the fake coin, in this problem your task is to figure out whether the fake coin is heavier or lighter than a real coin. Your challenge is that you are only permitted to use the scale twice. Find all numbers N for which this can be done.

I would like to add an extra twist to the problem above. It is conceivable that there might be several different strategies for finding the direction in which the weight of the fake coin deviates from the real coins. In this case it is better to choose a strategy that can redeem as many coins as possible — that is, to identify the maximum number of coins as real.

The number of coins you identify as real depends on the outcomes of your weighings. Then what is the precise definition of the best strategy?

Let us call a strategy k-redeem if after the weighings you are guaranteed to demonstrate that k coins are real, but you are not guaranteed to demonstrate that k+1 coins are real. Your task is to analyze two-weighing strategies and choose the most profitable one — the strategy that guarantees to redeem the largest possible number of coins, that is, a k-redeem strategy for the largest k.

Sara was born in Boston on February 29, 2008 at 11:00 am. Her parents were quite upset that their calendar-challenged daughter would only be able to celebrate her birthday once in four years. Luckily, science can help Sara’s parents. How? Sara can celebrate her birthday every year at the moment when the Earth passes the same point on its orbit around the Sun as when Sara was born.

Assuming that Sara lives her entire life in Boston and that the daylight savings time is not moved earlier into February, your task is to calculate the schedule of Sara’s birthday celebrations for 100 years starting from her birth. To simplify your homework, you can approximate one year as 365 days and 6 hours.

Joseph DeVincentis heard my prayers and created an index for MIT mystery hunt puzzles. He created it not because I requested it, but rather because he was on the writing team this year and they needed it. Anyway, finally there is an index.

I have to warn you, though, that this index was created for people who have already solved the puzzles, so the index contains hints for many of the problems and, on rare occasions, solutions.

Now I will do the math index for this year, and I promise that I will avoid big hints.

• Fun with Numbers — I got a very warm feeling from this puzzle. Some questions were right from my Number Gossip page and I knew some answers by heart.
• Planar Complex — A puzzle with complex numbers.
• Seeking Syren Scotchy — An advanced non-rectangular Nurikabe variation with colors and knight’s moves.
• Side by Side by Side — A massive logic puzzle.
• Counter Culture — So as not to reveal much info, I will just say that some math is involved in solving this puzzle.
• Expeditions — A logic puzzle that requires extra knowledge.
• Lighten Up — A Light-Up variation.
• Directions — I shouldn’t say.
• Message From Above — A math puzzle at the second stage.
• The Prodigious Riddle of Juno — A logic puzzle with a lot of if-then clauses.
• Bulls and Cows — Not surprisingly, a variation on Bulls and Cows
• Building a Mystery — Create a polyhedron.
• Trance State — Logic gates.
• Sequencer — Mirrors.
• 20,000 Leagues Under the Sea — A Battleship puzzle at the second stage.

I am so used to wise-men puzzles about hats, that I was pleasantly surprised when Leonid Makar-Limanov gave me a wise-men puzzle that didn’t include them.

A sultan decides to check how wise his two wise men are. The sultan chooses a cell on a chessboard and shows it to the first wise man. In addition, each cell on the chessboard either contains a rock or is empty. The first wise man has to decide whether to remove one rock or to add one rock to an empty cell. Next, the second wise man must look at the board and guess which cell was chosen by the sultan. The two wise men are permitted to agree on the strategy beforehand. What strategy can they find to ensure that the second wise man will always guess the chosen cell?

If you are stuck, there are many approaches to try. You can attempt to solve the puzzle for a board of size 1 by 2, or for a board of size 1 by 3. Some might find it easier to solve a version in which you are allowed to have a multiple number of rocks on a cell, and the first wise man is permitted to add a rock to a cell that already contains rocks.