Tanya Khovanova's Math Blog

A puzzle from the 1977 USSR math Olympiad can be solved naturally with linear algebra:

Seven dwarfs are sitting at a round table. Each dwarf has a cup partially filled with milk. Each dwarf in turn divides all his milk evenly between the six other cups. After the seventh dwarf has done this, every cup happens to contain the initial amount of milk. What was the initial distribution of milk?

Can you use linear algebra to intelligently solve this puzzle?

This puzzle is a generalization of a problem from the 1977 USSR math Olympiad:

At the beginning of the game you are given a polynomial, which has 1 as its leading coefficient and 1 as its constant term. Two people play. On your turn you assign a real value to one of the unknown coefficients. The person that goes last wins if the polynomial has no real roots at the end. Who wins?

It is clear that if the last person’s goal is for the polynomial to have a root, then the game is trivial: in this case, he can always make 1 a root with the last move. Also, an odd degree polynomial always has a real root. Therefore, to make the game interesting we should assume that the degree of the polynomial is even.

Though I can’t imaging myself ever being interested in playing this game, figuring out the strategy is a lot of fun.

Here is a math puzzle for kids from a nice collection of ThinkFun Visual Brainstorms:

Wendy has cats. All but two of them are Siamese, all but two of them are Persian, and all but two of them are Maine Coon. How many cats does Wendy have altogether?

This puzzle has two answers: the expected answer and an unexpected answer. Can you find both?

Here is a puzzle that my ex-brother-in-law, Dodik, gave to me today:

Prove that every group with more than two elements has a non-trivial automorphism.

I usually love puzzles that are solved with a counter-intuitive brilliant idea. This puzzle is different — I didn’t solve it in one elegant swoop. But I still love the puzzle: it feels so natural, and it’s solution feels so natural, that I even decided to call this puzzle “organic.” Or, maybe, I am just in an organic mood today waiting for my organic bananas to be delivered from Boston Organics.

Here is a funny puzzle from Kvant (1996, vol 4), the best Russian journal of recreational math.

When Alice goes through the looking-glass, she might meet many multi-headed, multi-armed, multi-legged beings. A being with H heads, A arms and L legs is considered:

• smart, if H > A+L,
• strong, if A > H+L,
• fast, if L > H+A.

Can there exist a well-rounded personality behind the looking-glass: someone who is smart, strong and fast at the same time?

One of Microsoft’s biggest contributions to humanity is the popularization of manhole covers. The most famous question that Microsoft asks during job interviews of geeks is probably, “Why are manhole covers round?” Supposedly the right answer is that if a manhole cover is round it can’t be dropped into the hole. See, for example, How Would You Move Mount Fuji? Microsoft’s Cult of the Puzzle – How the World’s Smartest Company Selects the Most Creative Thinkers. This book by William Poundstone is dedicated exclusively to Microsoft’s interview puzzles.

All we need, actually, is for the cover not to fit into the hole. For example, if the hole is small, the cover could be almost any shape, as long as the diameter of the cover is bigger than any straight segment that fits into the hole.

Microsoft makes an implicit assumption that the cover is about the same shape and size as the hole; otherwise we would waste a lot of extra cover material.

Even with this assumption, there is a good deal of flexibility in possible shapes if our only concern is that the cover shouldn’t fit into the hole. It is sufficient for the cover to be any shape with a constant width.

Here are some additional answers to why the cover should be round. Microsoft accepts the answer that a round cover is easier to roll. I’m not sure why a cover would ever have to be moved away from its hole. But I agree that if kids try to steal a cover, it would be much easier to escape with a round one.

Another answer that Microsoft supposedly accepts is that you do not need to rotate a round cover to align it with the opening when you are putting it back. This way if there is a lane divider painted on the cover it will point in a new random direction.

You can find many other explanations at the wiki article devoted to this subject. The most reasonable is that manhole covers are round because manholes are round. Duh!

Thanks to Microsoft there are now many websites with pictures of and discussions on the shape of manhole covers. For example, Manhole Covers Etc. or Manhole.ca or Manhole Covers of the World. As you can see many manhole covers are square or rectangular. They say that New Hampshire had triangular covers at some point.

But my favorite answer to this interview question was sent to me by Jorge Tierno:

Since manhole covers are not necessarily round, but you are asking why they are round, you are probably asking why round manhole covers are round. Round manhole covers are round by definition.

Now I have my own favorite question to ask you during a job interview: “Why are some manhole covers square?”

I love Grand Tour puzzles more than I love Sudoku. You are given a graph, for example, a square grid like the one on the left. Some edges are highlighted. You need to find a closed path that visits each vertex exactly once and includes the highlighted edges as part of the path. Mathematically speaking you need to reconstruct a Hamiltonian circuit on a graph, once you are given a part of it. The highlighted edges are chosen to guarantee a unique solution to the puzzle.

On the left you can see a sample grand tour problem with its solution. This puzzle was designed by Glenn Iba. On Glenn’s Grand Tour Puzzle Page you can find many grand tour puzzles of varying levels of difficulty. The puzzles are playable. That is, you can click or unclick an edge. You can also branch out in a different color, which is especially useful for difficult puzzles when you want to test a hypothesis. I just want to warn you: these puzzles are addictive — I couldn’t stop playing until I solved all of them.

Below there is a simple grand tour puzzle from Glenn’s collection, but this time on a triangular grid:

You do not need a grid to construct a puzzle. But these puzzles look very natural on grids. I tried to analyze square grid puzzles a little bit. The first important point is that for square grids with odd number of vertices on each side of the square, Hamiltonian cycles do not exist. This point is easier to prove for directed Hamiltonian cycles. You can make a directed cycle from an undirected one by choosing a direction. If you have a directed cycle on a square grid, then the number of edges pointing up should be the same as the number of edges pointing down. We can say the same thing about edges on the cycle pointing left or right. Hence, the number of edges of a Hamiltonian cycle on a square grid should be even. At the same time, the number of edges of any Hamiltonian cycle equals the number of vertices.

I just proved that you need only consider square grids with an even number of vertices on each side. For square grids with two vertices on each side, there is only one Hamiltonian cycle, namely the border of the square. The only grand tour puzzle for this grid won’t have highlighted edges at all. For a square grid with four vertices on each side there are only two different Hamiltonian cycles up to isomorpshisms:

If we count all the reflections and rotations, we will get six Hamiltonian cycles. The next picture shows all 11 grand tour puzzles on this grid. If we count rotations and reflections, we will get 66 different grand tour puzzles.

Below are the sequences associated with this puzzle. Except for one case, I do not know if these sequences are in the Online Encyclopedia for Integer Sequences. I don’t know because I only counted two terms of each sequence, and this information is not sufficient to identify the sequence.

• A003763 Number of Hamiltonian cycles on 2n by 2n square grid of points. The sequence starts 1, 6, 1072, ….
• Number of Hamiltonian cycles up to isomorphism on 2n by 2n square grid of points. The sequence starts 1, 2, ….
• Number of Grand Tour puzzles on 2n by 2n square grid of points. The sequence starts 1, 11, ….
• Number of Grand Tour puzzles up to isomorphism on 2n by 2n square grid of points. The sequence starts 1, 66, ….
• The smallest number of edges in a Grand Tour puzzle on 2n by 2n square grid of points. The sequence starts 0, 2, ….
• The largest number of edges in a Grand Tour puzzle on 2n by 2n square grid of points. The sequence starts 0, 4, ….

If you look at Glenn Iba’s 6 by 6 square grid puzzles, you can see that the smallest number of edges is not more than 6. And the largest number of edges is no less than 12.

You can also make similar sequences for a triangular grid.

I invite you to calculate these sequences and submit them to the OEIS, if they are not already there.

Suppose N mothers live in a city. Half of them have one child and half of them have two children. That means that an average mother has 1.5 children.

Suppose we pick the sexual orientation of every child by rolling dice. Let’s assume that a child has a 10% probability of being homosexual.

The number of mothers with one child who is homosexual is 0.05N. The number of mothers with two children both of them homosexual is 0.005N. The number of mothers with two children with only the first child homosexual is 0.045N, which is the same as the number of mothers of two children with only the second child homosexual. The total number of mothers who have two children with at least one of them homosexual is 0.095N.

Let’s calculate the average fertility of a mother with at least one homosexual child. It is (1*0.05N + 2*0.095N)/(0.05N + 0.095N) = 0.24/0.145 = 1.66. The resulting number — 1.66 — is much bigger than 1.5, the average number of children for a mother.

This means there is a correlation between homosexuality and the fertility of mothers. This suggests that there is a gay gene which at the same time is responsible for female fertility.

But the model is completely random — there can’t be any correlation.

Where is the mistake?

Obviously, you can substitute homosexuality with having blue eyes or math ability or whatever, but I invented this paradox while I was working on my “Fraternal Birth Order Threatens Research into the Genetics of Homosexuality” post. Besides, there is some research on correlation between homosexuality and fertility.

I look forward to your solution to this puzzle.

Here I repeat the Conway’s Wizards Puzzle from a previous posting:

Last night I sat behind two wizards on a bus, and overheard the following:

— A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age.”
— B: “How interesting! Perhaps if you told me your age and the number of your children, I could work out their individual ages?”
— A: “No.”
— B: “Aha! AT LAST I know how old you are!”

Now what was the number of the bus?

It is obvious that the first wizard has more than two children. If he had one child then his/her age would be the number of the bus and it would be the same as the father’s age. While it is unrealistic, in mathematics many strange things can happen. The important part is that if the wizard A had one child he couldn’t have said ‘No’. The same is true for two children: their age distribution is uniquely defined by the sum and the product of their ages.

Here is a generalization of this puzzle:

Last night I sat behind two wizards on a bus, and overheard the following:

— Wizard A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age. Also, the sum of the squares of their ages is the number of dinosaurs in my collection.”
— Wizard B: “How interesting! Perhaps if you told me your age, the number of your children, and the number of dinosaurs, I could work out your children’s individual ages. ”
— Wizard A: “No.”
— Wizard B: “Aha! AT LAST I know how old you are!”

Now what was the number of the bus?

As usual with generalizations, they are drifting far from real life. For this puzzle, you have to open up your mind. In Conway’s original puzzle you do not need to assume that the wizard’s age is in a particular range, but once you solve it, you see that his age makes sense. In this generalized puzzle, you should assume that wizards can live thousands of years, and keep their libido that whole time. Wizards might spend so much of their youth thinking, that they postpone starting their families for a long time. The wizards’ wives are also generalized. They can produce children in great quantities and deliver multiple children at the same time in numbers exceeding the current world record.

Another difference with the original puzzle is that you can’t solve this one without a computer.

You can continue to the next step of generalization and create another puzzle by adding the next symmetric polynomial on the ages of the children, for example, the sum of cubes. In this case, I do not know if the puzzle works: that is, if there is an “AHA” moment there. I invite you, mighty geeks, to try it. Please, send me the answer.

In case you are wondering why the wizard is collecting dinosaurs, I need to point out to you that John H. Conway is a superb puzzle inventor. His puzzle includes a notation suggestion: a for the wizard’s age, b for the bus, c for the number of children. Hence, the dinosaurs.

Here is my simplified version of Conway’s wizards puzzle.

Last night when I was coming home from my writing class with Sue Katz, I sat behind two wizards on the bus, and overheard the following:

— Wizard A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is the amount of dollars I have in my pocket.”

At this point I interrupted the wizard. “Excuse me, professor, I overheard your conversation and can’t resist asking you a question. Usually when a father says ‘my children’ everyone assumes that he has at least two children. Can I assume that?”

— Wizard A: “No. I stated my assumptions up front. A positive integral number of children means one or more.”

I started thinking. If I were to explain this to a non-mathematician who assumes that ‘my children’ means more than one child, I would need to change the wizard’s statement into the following:

“I have at least one child. The ages of my one-or-more children are all positive integers. The sum of the ages of my children or the age of my only child is the number of this bus. The product of the ages of my children or my only child’s age is the amount of dollars I have in my pocket.”

Hmm. I like that mathematicians use ‘my children’ to indicate any number of children. Makes puzzles faster to type.

Anyway, the wizards continued their discussion:

— Wizard B: “How interesting! Perhaps if you told me the number of your children, I could work out their individual ages”
— Wizard A: “No.”
— Wizard B: “Aha! AT LAST I know how many children you have!”

If I were John Conway, I would have asked you next, “What is the number of the bus?” As I am not John Conway, I’ll ask you, “Why do we presume that Wizard A hasn’t cheated on his wife?”

The answer is that all wizards are notorious for making precise statements. If he cheats a lot, he would have started the conversation with, “The number of children I know about is a positive integer.” Or maybe, more discreetly, “My wife and I have a positive integral number of children.”

If you have already figured out the number of the bus, the bonus question is, “Why did I change the ‘age of the first wizard’ in Conway’s original puzzle into the ‘amount of dollars’ in my puzzle?”

When I left the bus, I started wondering why on earth anyone would ever want to sum up the ages of their children. And I remembered that I once did it myself. I was trying to persuade my sister to apply for U.S. citizenship. My argument was that by moving here the life expectancy of her children would increase by 30 years. Indeed, she has two sons and the male life expectancy in Russia and the U.S. has an astonishing 15-year difference. I have to admit that my argument is not very clean, as we do not know the causes for this difference and, besides, the data is for life expectancy at birth and it changes while our kids age. My sister dismissed my argument, saying that the low male life expectancy in Russia is due to alcoholism and that her family is not in the high-risk group.

So, there could be a reason to sum up the ages of your children, but why would anyone ever want to multiply the ages of their children? In any case, if the first wizard continues to keep an amount of dollars equaling the product of the ages of his children in his pocket, his pocket will do better than mutual funds for the next several years.