Tanya Khovanova's Math Blog

The following problem was sent to me by Joel Lewis.

You have 12 mice, one of which eats faster than all the others. You need to find it. You have a supply of standard cupcakes that you value very much and want to minimize how many of them you have to use. The only way you can find the mouse is to give cupcakes to several groups of mice and see which group is the fastest.

We assume that mice chew at a constant speed and all the mice in one group can attack the cake at the same time. I love this puzzle because I love coin problems. Let me restate the puzzle as a coin problem:

You have 12 coins, one of which is fake and weighs less than all the others. You have a balance scale with multiple pans, that is you can weigh several things at once and order them by weight. You do not care about the total number of weighings as in most classical coin puzzles, instead, this time using a pan is expensive and you want to find the fake coin with as few pan-uses as possible.

Spoiler warning: below I will discuss the solution for n mice.

You can, of course, give a cake to every mouse and see which one finishes first. You can save one cake by giving cakes at the same time to all but one of the mice. If everyone finishes simultaneously, the faster mouse is the unfed one.

It wastes cakes to give them to unequally-sized groups of mice. We can do better by copying the classical way to find a fake coin with the minimum number of weighings. That is, for each test, divide the mice into three groups as evenly as possible and give a cake to each of two equally-sized groups. The number of cakes you use is about 2log₃n.

I wouldn’t have written this essay if that was the solution. Sometimes you can do even better. For example, you can find the faster mouse out of 12 using only 5 cakes.

First, if you give out k cakes in one test, the test tells you which of k+1 groups the mouse is in. In the worst case, the faster mouse will be in the biggest group, so you should minimize the biggest group. Hence, your groups that get cakes should have ⌈n/(k+1)⌉ mice.

A test with one cake gives no information. I argue that giving out more than three cakes doesn’t gain anything. Indeed, suppose we use four cakes in a test. That is, we divide the mice into five groups A, B, C, D and E, of which the first four are the same size. We can simulate the test by two tests in each of which we give out two cakes. In the first test we give cakes to A+B and C+D. If one of the groups is faster, say A+B, then in the second test give cakes to A and B; if not, E has the faster mouse. I leave it as an exercise to simulate a test with more than four cakes.

Thus, in an optimal strategy we can use two or three cakes per test. Also, if you give one test with k − 1 cakes and the next one with m − 1 cakes, you can switch them with the same effect. The largest group after either order of tests will have at most ⌈n/km⌉ mice.

I don’t need two tests of three cakes each, which would give me a group of size at least ⌈n/16⌉. I can achieve the same result with three tests of two cakes each, with the faster mouse restricted to a group of size at most ⌈n/27⌉.

That means all my tests use two cakes, except I might use three cakes once. It doesn’t matter in what order I conduct the tests, so I can wait until the end to use three cakes. I leave it as an exercise to the reader that the only small number of mice for which we would prefer three cakes is four. From this it follows quickly that for numbers of mice between 3 * 3ⁱ + 1 and 4 * 3ⁱ, the number of cakes is 2i + 1. For numbers between 4 * 3ⁱ + 1 and 3ⁱ⁺² the answer is 2i + 2.

A week ago I chatted with my son Sergei about memorable math problems. He mentioned problem 5 from USAMO 2007. The problem can be reduced to the following:

Prove that (x⁷ + 1)/(x + 1) is composite for x = 7⁷ⁿ, where n is a non-negative integer.

Perhaps Sergei remembered this problem because as far as he knew, he was the only one in that competition to solve it. That made me curious as to how he solved it. His solution is available as solution 2 at the Art of Problem Solving website. His solution seemed mysterious and impossible to invent on the spot. I became even more curious to understand the thought process underlying his solution.

Here is his recollection:

We need to factor x⁶ − x⁵ + x⁴ − x³ + x² − x + 1. If such factoring existed it would have been known. Therefore, we need to somehow use the fact that x = 7⁷ⁿ. What is the simplest way to factor? We should try to represent the polynomial in question as the difference of squares. Luckily, x is an odd power of 7. We can make it a square if we multiply or divide it by 7 or another odd power of 7. So with a supply of squares on one side, we need to find a match for one of them to build the difference.

Let us simplify the problem and see what happens for (y³ + 1)/(y + 1) for y = 3³ⁿ, when n = 1. In other words we want to represent 703 as a difference of squares. This can be done: 703 = 28² − 9². Now let us see how we can express 28² and 9² through y which in this case is equal to 27. The first term is (y + 1)², and the second is 3y.

Now let’s go back to 7 and x, and check whether (x + 1)⁶ − (x⁶ − x⁵ + x⁴ − x³ + x² − x + 1) is 7x. Oops, no. The difference is 7x⁵ + 14x⁴ + 21x³ + 14x² +7x. On the plus side, it is divisible by 7x which we know is a square. The leftover factor is x⁴ + 2x³ + 3x² +2x + 1, which is a square of x² +x + 1.

The problem is solved, but the mystery remains. The problem can’t be generalized to numbers other than 3 and 7.

I am usually disappointed with American math text books. I have had an underwhelming experience with them. Often I open a book and in the next 15 minutes, I find a mistake, a typo, a misguided explanation, sloppiness, a misconception or some other annoyance.

I was pleasantly surprised when I opened the book Introduction to Algebra by Richard Rusczyk. I didn’t find any flaws in it — not in the first 15 minutes, and not even in the first hour. In fact, having used the book many times I have never found any mistakes. Not even a typo. This was disturbing. Is Richard Rusczyk human? It was such an unusual experience with an American math book, that I decided to deliberately look for a typo or a mistake. After half a year of light usage, I finally found something.

Look at problem 7.3.1.

Five chickens can lay 10 eggs in 20 days. How long does it take 18 chickens to lay 100 eggs?

There is nothing wrong with this problem. But the book is accompanied by the Introduction to Algebra Solutions Manual in which I found the following solution, that I’ve shortened for you:

The number of eggs is jointly proportional to the number of chickens and the amount of time. One chicken lays one egg in 10 days. Hence, 18 chickens will lay 100 eggs in 1000/18 days, which is slightly more than 55 and a half days.

What is wrong with this solution? Richard Rusczyk is human after all.

I like this book for its amazing accuracy and clean explanations. There are also a lot of diverse problems in terms of difficulty and ideas. Richard Rusczyk has good taste. Many of the problems are from different competitions and require inventiveness. I like that there are a lot of challenge problems that go beyond the boring parts of algebra. Also, I like that important points of algebra are chosen wisely and are emphasized.

This book might not be for everyone. It doesn’t have pretty pictures. It doesn’t have color at all. This is not a flaw for a math book. The book concentrates on ideas and problems, not entertainment. So if you’re looking for math entertainment, you’ll find it on my blog. For solid study, try Richard Rusczyk’s books.

I love Raymond Smullyan’s books , especially the trick puzzles he includes. The first time I met him in person, he played a trick on me.

This happened at the Gathering for Gardner 8. We were introduced and then later that day, the conference participants were treated to a dinner event that included a magic show. In one evening I saw more close-up magic tricks than I had in my whole life. This left me lightheaded, doubting physics and my whole scientific outlook on life.

Afterwards, Raymond Smullyan joined me in the elevator. “Do you want to see a magic trick?” he asked. “I bet I can kiss you without touching you.” I was caught off guard. At that moment I believed anything was possible. I agreed to the bet.

He asked me to close my eyes, kissed me on the cheek and laughed, “I lost.”

by Peter Winkler

As a writer of books on mathematical puzzles I am often faced with delicate issues of phrasing, none more so than when it comes to questions about conditional probability. Consider the classic “X has two children and at least one is a boy. What is the probability that the other is a boy?”

It is reasonable to interpret this puzzle as asking you “What is the probability that X has two boys, given that at least one of the children is a boy” in which case the answer is unambiguously 1/3—given the usual assumptions about no twins and equal gender frequency.

This puzzle confounds people *legitimately*, however, because most of the ways in which you are likely to find out that X has at least one boy contain an implicit bias which changes the answer. For example, if you happen to meet one of X‘s children and it’s a boy, the answer changes to 1/2.

Suppose the puzzle is phrased this way: X says “I have two children and at least one is a boy.” What is the probability that the other is a boy?

Put this way, the puzzle is highly ambiguous. Computer scientists, cryptologists and others who must deal carefully with message-passing know that what counts is not what a person says (even if she is known never to lie) but *under what circumstances would she have said it.*

Here, there is no context and thus no way to know what prompted X to make this statement. Could he instead have said “At least one is a girl”? Could he have said “Both are boys”? Could he have said nothing? If you, the one faced with solving the puzzle, are desperate to disambiguate it, you’d probably have to assume that what really happened was: X (for some reason unconnected with X‘s identity) was asked whether it was the case that he had at least one son, and, after being warned—by a judge?—that he had to give a yes-or-no answer, said “yes.” An unlikely scenario, to say the least, but necessary if you want to claim that the solution to the puzzle is 1/3.

Consider the puzzle presented (according to Alex Bellos) by Gary Foshee at the recent 9th Gathering for Gardner:

I have two children. One is a boy born on a Tuesday. What is the probability I have two boys?

If the puzzle was indeed put exactly this way, and your life depended on defending any particular answer, God help you. You cannot answer without knowing, for example, what the speaker would have said if he had one boy and one girl, and the boy was born on Wednesday. Or if he had two boys, one born on Tuesday and one on Wednesday. Or two girls, both born on Tuesday. Et cetera.

Now, there is nothing mathematically wrong (given the usual assumptions, including X being random) about saying that “The probability that X has two sons, given that at least one of X‘s two children is a boy born on Tuesday, is 13/27.” But if that is to be turned into an unambiguous puzzle attached to a presumed situation, some serious hypothesizing is necessary. For instance: you get on the phone and start calling random people. Each is asked if he or she has two children. If so, is it the case that at least one is a boy born on a Tuesday? And if the answer is again yes, are the children both boys? Theoretically, of the times you reach the third question, the fraction of pollees who say “yes” should tend to 13/27.

Kind of takes the fun out of the puzzle, though, doesn’t it? Kudos to Gary for stirring up controversy with a quickie.

I recently discussed the following problem:

You run into an old friend. He has two children, but you do not know their genders. He says, “I have a son born on Tuesday.” What is the probability that his second child is also a son?

I had heard this problem at the Gathering for Gardner 9 in a private conversation. My adversary had been convinced that the answer to the problem is 13/27. I came back to Boston from the gathering and wrote my aforementioned essay in which I disagreed with his conclusion.

I will tell you my little secret: when I started writing I substituted Wednesday for Tuesday. Then I checked my sons’ birthdays and they were born on Saturday and Tuesday. So I changed my essay back to Tuesday.

After I published it people sent me several links to other articles discussing the same problem, such as those of Keith Devlin and Alex Bellos, both of whom think the answer is 13/27. So I invented a fictional opponent — Jack, and here is my imaginary conversation with him.

Jack: The probability that a father with two sons has a son born on Tuesday is 13/49. The probability that a father with a son and a daughter has a son born on Tuesday is 1/7. A dad with a son and a daughter is encountered twice as often as a dad with just two sons. Hence, we compare 13/49 with 14/49, and the probability of the father having a second son is 13/27.

Me: What if the problem is about Wednesday?

Jack: It doesn’t matter. The particular day in question was random. The answer should be the same: 13/27.

Me: Suppose the father says, “I have a son born on *day.” He mumbles the day, so you do not hear it exactly.

Jack: Well, as the answer is the same for any day, it shouldn’t matter. The probability that his second child will also be a son is still 13/27.

Me: Suppose he says, “I have a son born …”. So he might have continued and mentioned the day, he might not have. What is the probability?

Jack: We already decided that it doesn’t depend on the day, so it shouldn’t matter. The probability is still 13/27.

Me: Suppose he says, “I have a son and I do not remember when he was born.” Isn’t that the same as just saying, “I have a son.” And by your arguments the probability that his second child is also a son is 13/27.

Jack: Hmm.

Me: Do you remember your calculation? If we denote the number of days in a week as d, then the probability of him having a second son is (2d−1)/(4d−1). My point is that this probability depends on the number of days of the week. So, if tomorrow we change a week length to another number his probability of having a son changes. Right?

At this point my imaginary conversation stops and I do not know whether I have convinced Jack or not.

Now let me give you another probability problem, where the answer is 13/27:

You pick a random father of two children and ask him, “Yes or no, do you have a son born on Tuesday?” Let’s make a leap and assume that all fathers know the day of the births of their children and that they answer truthfully. If the answer is yes, what is the probability of the father having two sons?

Jack’s argument works perfectly in this case.

My homework for the readers is: Explain the difference between these two problems. Why is the second problem well-defined, while the first one is not?

I gave you the Wise Men Without Hats puzzle in one of my previous posts:

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 pebble or is empty. The first wise man has to decide whether to remove one pebble or to add one pebble 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 their strategy beforehand. What strategy can they find to ensure that the second wise man will always guess the chosen cell?

My readers solved it. The solution is the following. Let us assign a number between 0 and 63 to every cell of the board. The second wise man takes numbers corresponding to cells with pebbles, converts them to binary and XORs the result. The answer is the cell number that he is seeking. The first wise man can always add or remove a pebble to make the XORing operation of the remaining pebbles produce any given number from 0 to 63.

This solution only works for boards that have a power of two as the number of cells.

Let’s look at the solution more closely. Let us create a graph corresponding to this problem. The vertices of the graph will correspond to the positions of pebbles. That means vertices are in one-to-one correspondence with the subsets of the set of 64 elements. Let us connect two vertices if we can get from one position to another by removing or adding a pebble. That means vertices are connected if two corresponding sets differ by exactly one element. We can see that the resulting graph is regular and each vertex is connected to exactly 64 other vertices.

Let us assign one out of 64 colors to each cell of the chessboard. The second wise man can guess the cell by looking at the chessboard. From this we can conclude that there is a bijection from the vertices of the graph to chessboard cells. In other words, we can color the graph in 64 colors. The existence of the strategy for wise men means that we can color the graph in such a way that each vertex is connected to the vertices of all colors.

As each vertex in our graph has exactly 64 neighbors, the graph has the following property: It can be colored in 64 colors in such a way that every vertex is connected to exactly one vertex of every color.

As soon as I realized that there is such a graph-theoretical object, I started to run around MIT asking everyone if such objects were studied or have a name.

It appears that indeed such an object has a name. A graph that can be colored into k colors in such a way that every vertex has exactly one neighbor of every color is called a rainbow graph.

Andrew Woldar discusses properties of such graphs in his paper. In particular, rainbow graphs are matching graphs. Indeed, every vertex is connected to exactly one vertex of the same color. Hence there is a natural pairing on vertices. From here, we can conclude that the smallest size of a rainbow graph is 2k.

Several MIT students liked the wise men problem and the associated graph object so much that they decided to study them. Hwanchul Yoo, SuHo Oh, and Taedong Yun enumerated all rainbow graphs of size 2k. The number of non-isomorphic rainbow graphs of size 2k equals mitthe number of switching classes of graphs with k vertices. The corresponding sequence A002854 starts as: 1, 1, 2, 3, 7, 16, 54. The paper is soon to appear. It is titled “Rainbow Graphs and Switching Classes.”

New additions to my trick problems collection:

* * *

It takes 12 minutes to saw a log into 3 parts. How much time will it take to saw it into 4 parts?

* * *

The Davidsons have five sons. Each son has one sister. How many children are there in the family?

* * *

A caterpillar wants to see the world and decides to climb a 12-meter pole. It starts every morning and climbs 4 meters in half a day. Then it falls asleep for the second half of the day during which it slips 3 meters down. How much time will it take the caterpillar to reach the top?

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.