Tanya Khovanova's Math Blog

Tired of the same old sudoku? Here’s an opportunity to try many variations of it. Thomas Snyder and Wei-Hwa Huang wrote a book called Mutant Sudoku. The authors are both Sudoku champions. I like the book because the authors are trying to bring everyone up to their level, rather than dumbing down their puzzles. So the book is not at all boring as are most Sudoku books.

The book contains about 180 fun puzzles. Look at the variety:

• Tight Fit Sudoku
• Extra Space Sudoku
• Tile Sudoku
• 3-D Sudoku
• Outside Sudoku
• Shape Sudoku
• Target Sum Sudoku
• Thermo-Sudoku
• Consecutive Sudoku
• Surplus Sudoku
• Deficit Sudoku
• Chimeric Sudoku

Wei-Hwa Huang kindly sent me this sample Thermo Sudoku puzzle from the book to use on my blog. The grey areas represent thermometers. Every particular thermometer has to have numbers in increasing order (not necessarily consecutive) starting from the bulb.

The second book by the same authors Sudoku Masterpieces: Elegant Challenges for Sudoku Lovers, is itself a masterpiece. With about 100 puzzles, there are fewer than in the first book, but there are more types of puzzles. As a consequence, you’ll have less practice for each particular type, but more variety. In addition, as you can see from the cover, the second book is elegantly designed.

I bought both books and immediately started scribbling in the first one. My bad handwriting would seem so out of place in the beautiful second book that I have not even started working in it yet. Maybe I will give it as a gift to someone with better penmanship.

Two days ago I threw at my readers the following problem:

A plane takes off and goes east at a rate of 350 mph. At the same time, a second plane takes off from the same place and goes west at a rate of 400 mph. When will they be 2000 miles apart?

The purpose of throwing this problem was to discuss the nature of the implicit assumptions that we are asked to make when solving math problems, and the implicit assumptions we teach our children to make when we teach them to solve math problems. This is especially important for problems like this, that are phrased in terms of a situation in the real world. The real world is too complex to model all of; the great power of mathematics is that sufficiently idealized situations are predictable. But which idealizations are appropriate? How does one choose? How does one teach youngsters what to choose?

Before I get to the actual discussion, however, I want to re-throw this problem at my readers, in an effort to highlight what originally jumped out at me as being wrong with it.

Neglecting the effects of altitude, differential wind, acceleration, relativity, measurement error, finite size and non-superimposability of the planes, and the Earth’s deviations from perfect sphericity,

1. Find how much time it takes them to become 2000 miles apart, assuming that the planes are starting from Boston and the distance is measured as
   1. a straight line in 3-space.
   2. the shortest surface distance.
2. How far from the closest pole may the starting point be located, so that the answer to the problem is “never”? Solve separately for
   1. the 3D distance.
   2. the shortest surface distance.
3. What portion of the Earth’s surface do the “never”-locations of the previous question occupy?
   1. under the 3D distance?
   2. under the shortest surface distance?

Hint: The easiest question is 2b.

I stumbled upon the following problem in Mathematics Teacher v.73 (September 1980):

A plane takes off and goes east at a rate of 350 mph. At the same time, a second plane takes off from the same place and goes west at a rate of 400 mph. When will they be 2000 miles apart?

Ooh, boy!

Question for my readers: explain my reaction.

A year ago I posted a chessboard puzzle. Recently I stumbled on a September 2008 issue of “Math Horizons” where it was presented as a magic trick.

When the magician leaves the room, the trickees lay out eight coins in a row deciding which side is turned up according to their whim. They also think of a number between 1 and 8 inclusive. The magician’s assistant then flips exactly one of the coins, before inviting the magician back in. The magician looks at the coins and guesses the number that the trickees thought of.

The magician’s strategy can be derived from the solution to the chessboard puzzle. The assistant numbers the coins from zero to seven from left to right. Then s/he flips the coin so that the parity addition (XORing) of all the numbers corresponding to heads is the number that the magician needs to guess. For this trick to work, the number of coins needs to be a power of 2.

Andrey Zelevinsky posted (in Russian) a cool variation of this trick with two decks of cards.

The magician has two identical card decks and he is out of the room for now. A random person from the audience thinks of a card. Next, the audience chooses several cards from the first deck. Then the assistant adds one card from the second deck to the set of chosen cards, lays them on a table, and then invites the magician back. The magician looks at the cards on the table and guesses the card that was thought of.

Unlike in the coin trick above, the number of cards in the deck doesn’t need to be a power of 2. This flexibility is due to the fact that the magician has two decks of cards, as opposed to one set of coins. Having the second deck is equivalent to the assistant in the coin trick being allowed to flip one or ZERO coins.

Nikolay Konstantinov, the creator and the organizer of the Tournament of the Towns, discussed some of his favorite tournament problems in a recent Russian interview. He mentioned two beautiful geometry problems by Sergey Markelov that I particularly loved. The first one is from the 2003 tournament.

An ant is sitting on the corner of a brick. A brick means a solid rectangular parallelepiped. The ant has a math degree and knows the shortest way to crawl to any point on the surface of the brick. Is it true that the farthest point from the ant is the opposite corner?

The other one is from 1995.

There are six pine trees on the shore of a circular lake. A treasure is submerged on the bottom of the lake. The directions to the treasure say that you need to divide the pine trees into two groups of three. Each group forms a triangle, and the treasure is at the midpoint between the two triangles’ orthocenters. Unfortunately, the directions do not explain how exactly to divide the trees into the groups. How many times do you need to dive in order to guarantee finding the treasure?

I gave my students a problem from the 2002 AMC 10-A:

Tina randomly selects two distinct numbers from the set {1, 2, 3, 4, 5}, and Sergio randomly selects a number from the set {1, 2, …, 10}. The probability that Sergio’s number is larger than the sum of the two numbers chosen by Tina is: (A) 2/5, (B) 9/20, (C) 1/2, (D) 11/20, (E) 24/25.

Here is a solution that some of my students suggested:

On average Tina gets 6. The probability that Sergio gets more than 6 is 2/5.

This is a flawed solution with the right answer. Time and again I meet a problem at a competition where incorrect reasoning produces the right answer and is much faster, putting students who understand the problem at a disadvantage. This is a design flaw. The designers of multiple-choice problems should anticipate mistaken solutions such as the one above. A good designer would create a problem such that a mistaken solution leads to a wrong answer — one which has been included in the list of choices. Thus, a wrong solution would be punished rather than rewarded.

Readers: here are three challenges. First, to ponder what is the right solution. Second, to change parameters slightly so that the solution above doesn’t work. And lastly, the most interesting challenge is to explain why the solution above yielded the correct result.

I’ve heard many fun problems in which blindfolded parachutists are dropped somewhere and they need to meet up once they’re on the ground. They can’t shout or purposefully leave traces behind. They will recognize each other as soon as they bump into each other. Their goal is to get to the same assembly point. They can design their strategy in advance.

Here is the first problem in a series that gets increasingly difficult:

Two parachutists are dropped at different locations on a straight line at the same time. Both have an excellent sense of direction and a good geographical memory, so both know where they are at any moment with respect to their starting point on the line. What’s their strategy?

The strategy is that the first person stands still and the second one goes forward and back repeatedly, increasing the distance of each leg until they collide.

In the next variation, both are required to execute the same program, that is, if one stands still, then both stand still. To compensate for this increased difficulty, they are allowed to leave their parachutes anywhere. And both of them will recognize the other’s parachute if they bump into it.

In the third variation, the set-up is similar to the previous problem, but they are not allowed to change the direction of their movement. To their advantage, they know which way East is.

I recently heard a 2-D version from my son Sergei in which the parachutists are ghosts. That means that when they bump into each other they go through each other without even recognizing the fact that they met:

Several blindfolded men are sleeping at different locations on a plane. Each wakes up, not necessarily at the same time. At the moment of waking up, each of them receives the locations of all the others in relation to himself at that moment. They are not allowed to interact, nor will they receive any further information as time passes. They need to get together in one place. How can they do that, if they are allowed to decide on their strategy in advance?

They do not know where North is. So they can’t go to the person at the most Northern point. Also they do not know how locations correspond to people, so they can’t all go to where, say, Peter is. Let us consider the case of two men. Suppose they decide to go to the middle of the segment of two locations they receive when they awake. But they get different locations because they wake up at different times. Suppose the first person wakes up and goes to the middle. The fact that he walks while the other is sleeping, means that he changes the middle. So when the second person wakes up, his calculated middle is different from the one calculated by the first person. Consequently, they will never manage to meet. Hence, the solution should be different.

Actually Sergei gave me a more difficult problem:

Not only do they need to meet, but they need to stay together for a predefined finite time period.

Here is as bonus problem.

If there are three parachutists, it is possible to end up in a meeting place and stay there indefinitely. For four people it is often possible too.

In my old essay I presented the following coin problem.

We have N coins that look identical, but we know that exactly one of them is fake. The genuine coins all weigh 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.

Here is my solution to this problem. Let us start with small values of N. For one coin you can’t do anything. For two coins there isn’t much you can do either. I will leave it to the readers to solve this for three coins, while I move on to four coins.

Let us compare two coins against the other two. The weighing has to unbalance. Then put aside the two coins from the right pan and compare one coin from the left pan with the other coin from the left pan. If they balance, then the right pan in the first weighing contained the fake coin. If they are unbalanced then the left pan in the first weighing contained the fake coin. Knowing where the fake coin was in the first weighing gives us the answer.

It is often very useful to go through the easy cases. For this problem we can scale the solution for three and four coins to get a solution for any number of coins that is divisible by three and four by just grouping coins accordingly. Thus we have solutions for 3k and 4k coins.

For any number of coins we can try to merge the solutions above. Divide all coins into three piles of size a, a and b, where a ≤ b ≤ 2a. In the first weighing compare the first two piles. If they balance, then the fake coin must be among the b remaining coins. Now pick any b coins from both pans in the first weighing and compare them to the remaining b coins. If the first weighing is unbalanced, then the remaining coins have to be real. For the second weighing we can pick a coins from the remaining pile and compare them to one of the pans in the first weighing.

The solution I just described doesn’t cover the case of N = 5. I leave it to my readers to explain why and to solve the problem for N = 5.

Among ten given coins, some may be real and some may be fake. All real coins weigh the same. All fake coins weigh the same, but have a different weight than real coins. Can you prove or disprove that all ten coins weigh the same in three weighings on a balance scale?

When I first received this puzzle from Ken Fan I thought that he mistyped the number of coins. The solution for eight coins was so easy and natural that I thought that it should be eight — not ten. It appears that I was not the only one who thought so. I heard about a published paper with the conjecture that the best you can do is to prove uniformity for 2ⁿ coins in n weighings.

I will leave it to the readers to find a solution for eight coins, as well as for any number of coins less than eight. I’ll use my time here to explain the solution for ten coins that my son Sergei Bernstein suggested.

First, in every weighing we need to put the same number of coins in both pans. If the pans are unbalanced, the coins are not uniform; that is, some of them are real and some of them are fake. For this discussion, I will assume that all the weighings are balanced. Let’s number all coins from one to ten.

Consider two sets. The first set contains only the first coin and the second set contains the second and the third coins. Suppose the number of fake coins in the first set is a and a could be zero or one. The number of fake coins in the second set is b where b is zero, one or two. In the first weighing compare the first three coins against coins numbered 4, 5, and 6. As they balance the set of coins 4, 5, and 6 has to have exactly a + b fake coins.

In the second weighing compare the remaining four coins 7, 8, 9, and 10 against coins 1, 4, 5, and 6. As the scale balances we have to conclude that the number of fake coins among the coins 7, 8, 9, and 10 is 2a + b.

For the last weighing we compare coins 1, 7, 8, 9, and 10 against 2, 3, 4, 5, and 6. The balance brings us to the equation 3a + b = a + 2b, which means that 2a = b. This in turn means that either a = b = 0 and all the coins are real, or that a = 1, and b = 2 and all the coins are fake.

Now that you’ve solved the problem for eight and less coins and that I’ve just described a solution for ten coins, can we solve this problem for nine coins? Here is my solution for nine coins. This solution includes ideas of how to use a solution you already know to build a solution for a smaller number of coins.

Take the solution for ten coins and find two coins that are never on the same pan. For example coins 2 and 10. Now everywhere where we need 10, use 2. If we need both of them on different pans, then do not use them at all. The solution becomes:

The first weighing is the same as before with the same conclusion. The set containing the coin 1 has a fake coins, the set containing the coins 2 and 3 has b fake coins and the set containing coins 4, 5, and 6 has to have exactly a + b fake coins.

In the second weighing compare the four coins 7, 8, 9, and 2 against 1, 4, 5, and 6. As the scale balances we have to conclude that the number of fake coins among 7, 8, 9, and 2 is 2a + b.

For the last weighing we compare coins 1, 7, 8, and 9 against 3, 4, 5, and 6. If we virtually add the coin number 2 to both pans, the balance brings us to the equation 3a + b = a + 2b, which means that 2a = b. Which in turn means, similar to above, that either all the coins are real or all of them are fake.

It is known (see Kozlov and Vu, Coins and Cones) that you can solve the same problem for 30 coins in four weighings. I’ve never seen an elementary solution. Can you provide one?

I heard this problem many years ago when I was working for Math Alive.

Three men are fighting in a truel. Andrew is the worst shot; he misses 2/3 of the time. Bob is better; he misses 1/3 of the time. Connor is the best shot; he always hits. Each of the three men have an infinite number of bullets. Each shot is either a kill or a miss. They have to shoot at each other in order until two of them are dead. To make it more fair they decide to start with Andrew, followed by Bob, and then Connor. We assume that they choose their strategies to maximize their probability of survival. At whom should Andrew aim for his first shot?

This is a beautiful probability puzzle, and I will not spoil it for you by writing a solution. Recently, I watched an episode of Numb3rs: The Fifth Season (“Frienemies”) which featured a version of this puzzle. Here is how Dr. Marshall Penfield, a frienemy of the protagonist Charlie Eppes, describes it:

Imagine a duel between three people. I’m the worst shot; I hit the target once every three trials. One of my opponents [Charlie] is better; hits it twice every three shots. The third guy [Colby] is a dead shot; he never misses. Each gets one shot. As the worst I go first, then Charlie, then Colby. Who do I aim for for my one shot?

This is a completely different problem; it’s no longer about the last man standing. Colby doesn’t need to shoot since the other two truelists have already expended their only shots. If Charlie believes that Colby prefers nonviolence, all else being equal, then Charlie doesn’t need to shoot. Finally, the same is true of Marshall. There is no point in shooting at all.

To make things more mathematically interesting, let’s assume that the truelists are bloodthirsty. That is, if shooting doesn’t decrease their survival rate, they will shoot. How do we solve this problem?

If he survives, Colby will kill someone. If Charlie is alive during his turn, he has to shoot Colby because Colby might kill him. What should Marshall do? If Marshall kills Colby, then Charlie misses Marshall (hence Marshall survives) with probability 1/3. If Marshall kills Charlie, then Marshall is guaranteed to be killed by Colby, so Marshall survives with probability 0. If he doesn’t kill anyone, things look much better: with probability 2/3, Colby is killed by Charlie and Marshall survives. Even if Colby is alive, he does not necessarily shoot Marshall, so Marshall survives with probability at least 2/3. Overall, Marshall’s chances of staying alive are much better if he misses. He should shoot in the air!

The sad part of the story is that Charlie Eppes completely missed. That is, he completely missed the solution. In the episode he suggested that Marshall should shoot Charlie. If Marshall shoots Charlie, he will be guaranteed to die.

It is disappointing that a show about math can’t get its math right.