Archive for November 2009

## Beliefs that Might Save Your Life

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.

## Why Modulo 11?

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 x5 – y2 = 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.

## HMNT 2009

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.

## Hassan’s Horses

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.

## No Odd One Out

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?