Tanya Khovanova's Math Blog

I’ve translated two problems from the 2009 Moscow Math Olympiad. In both of them our characters are genetically engineered octopuses. The ones with an even number of arms always tell the truth; the ones with an odd number of arms always lie. In the first problem (for sixth graders) four octopuses had a chat:

• “I have 8 arms,” the green octopus bragged to the blue one. “You have only 6!”
• “It is I who has 8 arms,” countered the blue octopus. “You have only 7!”
• “The blue one really has 8 arms,” the red octopus said, confirming the blue one’s claim. He went on to boast, “I have 9 arms!”
• “None of you have 8 arms,” interjected the striped octopus. “Only I have 8 arms!”

Who has exactly 8 arms?

Not only do octopuses lie or tell the truth according to the parity of the number of their arms, it turns out that the underwater world is so discriminatory that only octopuses with six, seven or eight arms are allowed to serve Neptune. In the next problem (for seventh graders), four octopuses who worked as guards at Neptune’s palace were conversing:

• The blue one said, “All together we have 28 arms.”
• The green one said, “All together we have 27 arms.”
• The yellow one said, “All together we have 26 arms.”
• The red one said, “All together we have 25 arms.”

How many arms does each of them have?

My students enjoyed the octopuses, so I decided to invent some octopus problems of my own. In the first problem, the guards from the night shift at Neptune’s palace were bored, and they started to argue:

• The magenta one said, “All together we have 31 arms.”
• The cyan one said, “No, we do not.”
• The brown one said, “The beige one has six arms.”
• The beige one said, “You, brown, are lying.”

Who is lying and who is telling the truth?

In the next problem the last shift of guards at the palace has nothing better to do than count their arms:

• The pink one said, “Gray and I have 15 arms together.”
• The gray one said, “Lavender and I have 14 arms together.”
• The lavender one said, “Turquoise and I have 14 arms together.”
• The turquoise one said, “Pink and I have 15 arms together.”

What number of arms does each one have?

The first episode of Numb3rs: Season Six reminded me of the hangman’s paradox. Here is a one-day version of the hangman’s paradox:

Suppose you are in a prison and the guard says to you, “You will be hanged tomorrow at noon and it will be a surprise.” You presume that you can’t be surprised since they already told you, so there is a contradiction in what they’ve said. Therefore, you conclude that they can’t hang you and you relax. Next day at noon the guard comes for you, to take you to be hanged, and you are utterly surprised. Oops.

What I do not like about this paradox is that it assumes that you do not know about the paradox. I, on the other hand, imagine that you, my reader, are logical and intelligent. So the moment the guard tells you that you will be hanged tomorrow at noon and it will be a surprise, you realize that the situation depends on what you decide to believe in now. If you decide that you won’t be hanged tomorrow, then you will have a relatively relaxing day today and you will be caught by surprise tomorrow and die. If you decide that you will die tomorrow, then you will have a nerve-wracking day today, but the guard may release you, to save his honor, since you won’t be surprised.

The original hangman’s paradox in which the guard tells you that you will be hanged on a weekday the following week and that you will be caught by surprise, also assumes that you are not aware of the paradox. If you are aware of the paradox, you know that usually guards in this paradox come for you on Wednesday, so you can prepare yourself. Actually, to guarantee your survival, if not your feeling of moral superiority, you can daily persuade yourself to belief that you will be hanged at noon the next day. This way, you will never be caught by surprise. If you are a person who can control your own beliefs, you may be able to save your life.

The book An Introduction to Diophantine Equations by Titu Andreescu and Dorin Andrica is targeted at people preparing for USAMO and IMO. It contains a lot of problems on Diophantine equations from math Olympiads used in various math Olympiads all over the world.

The first chapter discusses several methods for solving Diophantine equations: decomposition, using inequalities, using parameters, modular arithmetic, induction, infinite descent, and other miscellaneous ideas. Each sub-chapter starts with a short description of the method, accompanied by several solutions to sample problems. At the end of each sub-chapter there are a plethora of exercise problems.

The second and the third chapters are more theoretical. The former discusses some classical equations and the latter looks at Pell’s equation. These two chapters also contain problems, but the bulk of the chapters is devoted to basic theory that is essential to an understanding of Diophantine equations.

For those who are training for the Olympiads, this is an important book to own, not only because there are few other books on the subject, but because it provides so many useful problems.

I’ve long complained that most training books for math competitions leave out any discussion of how we choose a method by just looking at a problem. Andreescu and Andrica didn’t fill that gap with this book.

Perhaps in their next book they will point out clues that indicate that a particular problem might be solved by the parametric method. And explain which types of problems are best solved with induction. Let them challenge students to find those clues in a problem that help us to judge which method might be most promising, instead of randomly trying one method after another. Let me give you a sample problem from the book, which originated at the Balkan Mathematical Olympiad:

Prove that the equation x⁵ – y² = 4 has no solutions in integers.

The solution is to take the equation modulo 11, and see that it is impossible.

Is there a reason to start with the modular arithmetic method and not with other methods? If we use modular arithmetic, do we recognize why it’s best to start with 11? I’m convinced that this problem has sufficient clues to suggest starting with checking this equation modulo 11.

I wonder if you, my readers, agree with me. If so, can you explain which hints in the problem lead to taking the equation modulo 11? I believe it should be a part of competition training to learn to identify clues that suggest that one direction might be preferable to the others.

I love Harvard-MIT Math Tournaments. I like the mini-events, especially when I learn a new game. I also like the guts round, where I enjoy the adrenaline rush of watching the progress in real time. I also like the fact that I know many of the kids from different teams: my current students, my former students, the members of my club, my Sergei’s friends.

The problems for the competitions are designed by undergraduate students at MIT and Harvard. Kudos to them. Still, I was somewhat disappointed with the November 2009 problems. Most problems are variations of standard problems with different parameters. It is not easy to design a problem, but I was hoping for something fresh.

My favorite problem from the HMNT 2009 tournament was in the theme round:

There are five guys named Alan, Bob, Casey, Dan, and Eric. Each one either always tells the truth or always lies. You overhear the following discussion between them:

• Alan: “All of us are truth-tellers.”
• Bob: “No, only Alan and I are truth-tellers.”
• Casey: “You are both liars.”
• Dan: “If Casey is a truth-teller, then Eric is too.”
• Eric: “An odd number of us are liars.”

Who are the liars?

My second favorite problem was in the guts round:

Six men and their wives are sitting at a round table with 12 seats. These men and women are very jealous — no man will allow his wife to sit next to any man except for himself, and no woman will allow her husband to sit next to any woman except for herself. In how many distinct ways can these 12 people be seated such that these conditions are satisfied? (Rotations of a valid seating are considered distinct.)

This was the funniest problem:

You are trapped in ancient Japan, and a giant enemy crab is approaching! You must defeat it by cutting off its two claws and six legs and attacking its weak point for massive damage. You cannot cut off any of its claws until you cut off at least three of its legs, and you cannot attack its weak point until you have cut off all of its claws and legs. In how many ways can you defeat the giant enemy crab? (Note that the legs are distinguishable, as are the claws.)

It is difficult to arrange so many problems for four rounds without mistakes. The error in the following problem is not a typo and it bothers me that no one caught it:

Pick a random digit in the decimal expansion of 1/99999. What is the probability that it is 0?

Hey, there is no uniform distribution on an infinite set of integers: picking a random digit is not defined.

Last month I gave my students a problem from Raymond Smullyan’s book The Riddle of Scheherazade:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. How many of them can each say that it is the same color as another one of Hassan’s horses?

Half of my students failed to notice the trick and gave the wrong answer. Recently I gave them the continuation of the problem from the same book:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. Assuming now that Hassan’s horses can talk, how many of them can each say that it is the same color as another one of Hassan’s horses?

This time the majority of my students didn’t notice the trick. This motivated me to continue playing jokes with them. Unfortunately though, Raymond Smullyan had only two problems about Hassan’s horses, so I have to invent the next one myself. Here is what I plan to give my students next time:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. Assuming now that Hassan’s horses can talk and always tell the truth, how many of them will say that it is the same color as another one of Hassan’s horses?

Feel free to continue the series.

My recent blog puzzle where my readers had to choose the odd one out became extremely popular and was republished in many blogs around the world. Some commentators decided that my posting was a joke and an example where the odd one out didn’t exist. I have to disappoint them: as a protest against find-the-odd-one-out questions and to illustrate that sometimes there is no good choice for the odd one out I would have chosen a different picture:

Can you find the odd one out?

Inspired by Michael Huber, who in his new book Mythematics combines math problems with Greek myths, I invented my first logic puzzle. Unlike Huber, I never had any ambition to help Hercules, but I always wanted to assist Frodo.

The day was passing towards sunset when the Company finally caught a long-awaited gleam of water, from which sparkled flickers of sunlight. As they quietly drew nearer, they laid their eyes on the next obstacle — a river that they had to transverse. The Company was footsore and tired and the hobbits were starving. But they couldn’t rest yet. They needed to collect materials with which to construct their raft before it became too dark. By nightfall they managed to build a tiny raft, and eagerly started their supper.

They couldn’t wait until dawn to build more rafts, for they needed to cross the river now. So while they rested, Aragorn smoked his pipe and began to contrive a plan.

Aragorn was in charge and there were eight of them. The four hobbits — Frodo, Sam, Merry and Pippin — were not very useful in battle. However, the four strong fighters — Aragorn, Gimli, Legolas and Boromir, who were sworn to protect the ring-bearer Frodo — were the best in the land.

The small raft they had built would not hold a lot of weight. Aragorn and Boromir were the heaviest. Gimli was short, but together with his armor he weighed as much as either Aragorn or Boromir. Each one of these three heaviest warriors was close to the raft’s maximum capacity, so they had to each be alone on the raft while crossing the river. Among the strong fighters, only Legolas was able to cross the river with a hobbit. The raft could also accommodate two hobbits.

Weight was not Aragorn’s only consideration: the current was dangerously fast. All the strong men could row, but among the hobbits, only Sam was strong enough to row against such a swift current.

Aragorn also worried about the orcs, who were roaming on both sides of the river. He didn’t want to leave any hobbit(s) alone on a riverside, without the safeguard of a strong fighter. Because he was the ring-bearer, Frodo needed extra protection. Aragorn wanted Frodo to be accompanied by at least two strong men. But lately Boromir had become restless when he was around the ring and Aragorn couldn’t count on him to look after Frodo. That is, while on the riverside, Frodo’s protection had to come from two out of the three remaining strong men: Aragorn, Legolas and Gimli.

Can you help Aragorn design a plan to cross the river?

In my days of competing in math, I met guys who could solve any geometry problem by using coordinates: first they would assign variables to represent coordinates of different points, then they would write and solve a set of equations. It seemed so boring. Besides, this approach doesn’t provide us with any new insight into geometry.

I find geometric solutions to geometry problems much more interesting than algebraic solutions. The geometric solutions that use geometric transformations are often the shortest and the most beautiful.

I.M. Yaglom wrote a great trilogy called The Geometric Transformations. The first book of this trilogy discusses translations, rotations and reflections. The second one — looks at similarity transformations, and the third one talks about affine and projective transformations. A lot of beautiful problems with their solutions are scattered throughout these books. They include all my favorite problems related to transformations.

I think geometry is the weakest link for the USA math team. So we have to borrow the best geometry books from other countries. This trilogy was translated from Russian and Russians are known for their strong tradition of excellence in teaching geometry.

Below you can find sample problems from Geometric Transformations 1, Geometric Transformations 2 and Geometric Transformations 3 — not necessarily in this order.

I.M. Yaglom wrote a great trilogy called The Geometric Transformations. The first book of this trilogy discusses translations, rotations and reflections. The second one — looks at similarity transformations, and the third one talks about affine and projective transformations. A lot of beautiful problems with their solutions are scattered throughout these books. They include all my favorite problems related to transformations.

I think geometry is the weakest link for the USA math team. So we have to borrow the best geometry books from other countries. This trilogy was translated from Russian and Russians are known for their strong tradition of excellence in teaching geometry.

Below you can find sample problems from Geometric Transformations 1, Geometric Transformations 2 and Geometric Transformations 3 — not necessarily in this order.

Problem 1. Let A be a point outside a circle S. Using only a straightedge, draw the tangents from A to S.

Problem 2. At what point should a bridge be built across a river separating two towns A and B (see figure) in order that the path connecting the towns be as short as possible? The banks of the river are assumed to be parallel straight lines, and the bridge is assumed to be perpendicular to the river.

Problem 3. Suppose you have two lines drawn on a piece of paper. The intersection point A of the two lines is unreachable: it is outside the paper. Using a ruler and a compass, draw a line through a given point M such that, were the paper bigger, point A would belong to the continuation of the line.

I am strongly opposed to questions of the type “which is the odd one out” during IQ tests. On the other hand, I do not mind them in different settings, especially when they are fun. Inspired by Martin Gardner, I spent a lot of time drawing this picture, and now I have to share it with the world. So, which is the odd one out?

I love the MIT Mystery Hunt. I like the adrenalin rush when solving problems under pressure. Plus, I like the togetherness of doing problems with other people. During the hunt I usually do not have time to look at all the puzzles: some of them are solved by my teammates while I’m sleeping and others are solved before I get to see them.

I’ve never tried to go back and check out the puzzles I missed nor the puzzles from the previous hunts, probably because without the goal of winning and without my team, I might find them boring. Often the solving process involves tedious Internet browsing to identify the images of different people or objects. I would only be motivated if the puzzle were related to something I am very interested in, such as Ballroom dancing. But I’m not thrilled at the thought of browsing through all the problems in order to find one that is relevant to the Tango.

In short, I need an index to the puzzles. For example, it would be nice to direct the lovers of square dancing to the Do Sa Do puzzle, or fans of Star Trek to the Alien Species puzzle. I hope that nobody blames me for hinting that those aliens are from Star Trek. I’m convinced that Trekkies who only want to solve Star Trek-related puzzles would immediately recognize them anyway. I do believe that I am not revealing too much by saying that the Facebook puzzle will appeal to the aficionados of the television show “24”.

It would be extremely useful to humanity to at least mark the MIT Mystery Hunt puzzles that are self-consistent, and do not require activities. For example, some of the puzzles involve interaction with headquarters, so you can’t solve them after the hunt. Some of the puzzles might expire, as for example the puzzle with pictures of different announcements in the infinite corridor.

Unfortunately, such an index doesn’t exist, and I do not have the time or expertise to create one myself. But I can fill this void at least partially by presenting a guide to math puzzles from the previous four hunts. I can’t promise that my guide is complete, as navigating the MIT Mystery Hunt website is very tiresome.

Before going into the math puzzles, I would like to list Sergei’s favorite type of puzzle: Duck Konundrums. The first Duck Konundrum puzzle appeared in 2000. It was created by Dan Katz, which is why his initials are in the title. One really needs to follow the instructions for this puzzle. This is very unusual as traditionally hunt puzzles do not have instructions at all. Do not be relieved: the instructions are really very complicated. The next Duck Konundrum puzzle appeared in 2002 and was considered to be even more amusing. People loved it, and this type of puzzle became a tradition in subsequent hunts. Here is my list of Duck Konundrums:

• 2000 — 5.6: The Duck Konundrum.
• 2002 — D2: The Mighty Duck Konundrum.
• 2004 — D3: The Fellowship Of The Duck.
• 2006 — The Cock Conundrum — A combination of the Duck Konundrum and a cute boys’ puzzle.
• 2007 — D4: Ducks Playing Poker.
• 2008 — Mystery Rallye — A Duck Konundrum style puzzle without ducks.
• 2009 — The Amazing Juggling Troupe Of Duckkon Undrum V.

Many Mystery Hunt puzzles appeal to mathematicians. I have to warn you though. Puzzles often are divided into two stages. In the first stage, you need to solve a puzzle, like solving sudoku, a crossword or finding all the wedding dates of the people in the pictures. The second stage requires you to produce a word or a phrase that is the answer to the puzzle. The second stage might be as simple as listing the people in chronological order of their wedding dates and then taking the first letters of their last names. This second stage could also be quite difficult. Depending on your tastes one stage of the puzzle might be much more rewarding than the other. If you love solving sudokus, you might find it more fun to just stop with that solution, instead of continuing on to the second stage.

2006

• Got Your Number — Some recognizable numbers at the second stage (my favorite for the year).
• 783658 — Sudoku at the second stage.
• Hey, Look, A Grid! — A bunch of numbers in a grid.
• Feel Your Way — A very frustrating minesweeper.
• Gross Solitaire — A tedious logic puzzle.
• All for One and One for All — The “26L. in the A.” type of puzzle with first-order logic notation.
• Fun with Formulae — Decipher recognizable formulae.
• Numeracy — A list of very big numbers.

2007

• Clash of the Titans — A mixture of skyscraper type puzzles with logic.
• A Midterm Progress Report to the Enron Board of Directors, July 2000 — Many logic puzzles involving numbers.
• Captain Red Herring’s Buried Pirate Booty — A variation of battleship puzzles.
• The Joy of Accountancy — A kakuro variation.
• Splits and Mergers — A combination of mazes.
• Nur einzelne Zahlen erlaubt! — A sudoku-related puzzle.
• Transmogrifiers — Figure out unknown functions.
• Puzzle Editing — A real treat! You need to solve several Japanese puzzles: Fillomino, Nurikabe, Masyu, Light Up, Heyawake, Hitori and Edel.
• Man, I Hate These %#!&@ Sudokus! — You need the extra pdf file to solve these interrelated sudoku puzzles.
• I Only Get a Measly $200? — A logic puzzle related to the Monopoly games requires an extra pdf file.

2008

• Knots and Crosswords — As it says: crosswords with some knots.
• Cursed — A kakuro variation.
• The Cult of Helios — First you have to figure out what this puzzle is about.
• Bad Beat Jackpot — Some poker math.
• Twisty Little Passages — Map the maze.
• Chimera — An interesting mixture.
• Trouble in Triplicate — Related to the game of Set.
• War Game — A logic puzzle.
• All Geared Up — You need to be good with arithmetic to count all rotations.
• Functions — This is my favorite of the year, especially good for sequence fans.

2009

• Cloaked Battleships — A variation on battleship puzzles.
• Growth Involves Reconstructing Legos — A variation on skyscraper puzzles.
• Mos Eisley Spaceport — A graph-fitting puzzle.
• Malthusian Catastrophes — Requires a lot of calculations.
• Plan 4 From Outer Space — You need to solve a lot of equations.
• The Sexaholics of Truthteller Planet — A logic puzzle, my favorite for the year.
• Cross Something-Or-Others — Eight beautiful variations of kakuro. To get to the answer you need to use three more pages: first, second and third. This one was my second favorite of the year.
• Our Crew Is Replaceable. Your Package Isn’t. — Six river crossing puzzles.
• His Alien Barbarian Girl and Her Robot Dog — The puzzle is a colorful version of battleship puzzles. To get to the answer you need to combine this puzzle with its matching doctor puzzle.
• His Troubled Teen — A nice logic puzzle. To get to the answer you need to complement this with the matching doctor puzzle.
• His Investigative Journalist — Jigsaw sudokus, but you have to work to get to them. To get the answer you need to solve the matching doctor puzzle.

It would also be nice to have some ratings for puzzles. I am not sure how to persuade the webmasters of the MIT Mystery Hunt page to do the index and the rating. Feel free to send them an encouraging email.