Tanya Khovanova's Math Blog

I just invented a two-player game. To start, you have an empty n by n board. When it’s your turn you must write an integer between 1 and n into an empty cell on the board. Your integer has to differ from the integers that are already present in the same row or column. If you finish filling up the board, you will get a Latin square and the game will be a tie. The person who doesn’t have a move loses. What is the best strategy?

Let’s see what happens if n is 2. The first player puts any number in one of the four corners of the 2 by 2 board. The second player wins by placing a different number in the opposite corner.

I played this game with my son Sergei Bernstein on a 3 by 3 board. We discovered that the first player can always win. Since this game is so much fun, I’ll leave it to the reader to play it and to find the winning strategy for the first player.

Can you analyze bigger boards? Remember that this game has many symmetries. You can permute rows and columns. Also, you can permute numbers.

While we were playing Sergei invented two theorems.

Sergei’s theorem 1. If n is odd the first player can guarantee a tie.

Proof. In the first move the first player writes (n+1)/2 in the center cell. If the second player puts number x in any cell the first player puts number n+1−x into the cell that is rotationally symmetric to the second player’s cell with respect to the center. With this strategy the first player will always have a legal move.

Sergei’s theorem 2. If n is even the second player can guarantee a tie.

Proof. If the first player puts number x in any cell the second player puts number n+1−x into the cell that is vertically symmetric to the first player’s cell with respect to the vertical line of symmetry of the board. With this strategy the second player will always have a legal move.

As you play the game, let me know if you develop any theorems of your own.

Suppose you meet a friend who you know for sure has two children, and he says: “I have a son born on Tuesday.” What is the probability that the second child of this man is also a son?

People argue about this problem a lot. Although I’ve discussed similar problems in the past, this particular problem has several interesting twists. See if you can identify them.

First, let us agree on some basic assumptions:

1. Sons and daughters are equally probable. This is not exactly true, but it is a reasonable approximation.
2. For our purposes, twins do not exist. Not only is the proportion of twins in the population small, but because they are born on the same day, twins might complicate the calculation.
3. All days of the week are equally probable birthdays. While this can’t actually be true — for example, assisted labors are unlikely to be scheduled for weekends — it is a reasonable approximation.

Now let us consider the first scenario. A father of two children is picked at random. He is instructed to choose a child by flipping a coin. Then he has to provide information about the chosen child in the following format: “I have a son/daughter born on Mon/Tues/Wed/Thurs/Fri/Sat/Sun.” If his statement is, “I have a son born on Tuesday,” what is the probability that the second child is also a son?

The probability that a father of two daughters will make such a statement is zero. The probability that a father of differently-gendered children will produce such a statement is 1/14. Indeed, with a probability of 1/2 the son is chosen over the daughter and with a probability of 1/7 Tuesday is the birthday.

The probability that a father of two sons will make this statement is 1/7. Among the fathers with two children, there are twice as many who have a son and a daughter than fathers who have two sons. Plugging these numbers into the formula for calculating the conditional probability will give us a probability of 1/2 for the second child to also be a son.

Now let us consider the second scenario. A father of two children is picked at random. If he has two daughters he is sent home and another one picked at random until a father is found who has at least one son. If he has one son, he is instructed to provide information on his son’s day of birth. If he has two sons, he has to choose one at random. His statement will be, “I have a son born on Mon/Tues/Wed/Thurs/Fri/Sat/Sun.” If his statement is, “I have a son born on Tuesday,” what is the probability that the second child is also a son?

The probability that a father of differently-gendered children will produce such a statement is 1/7. If he has two sons, the probability will likewise be 1/7. Among the fathers with two children, twice as many have a son and a daughter as have two sons. Plugging these numbers into the formula for calculating the conditional probability gives us a probability of 1/3 for the second child to also be a son.

Now let us consider the third scenario. A father of two children is picked at random. If he doesn’t have a son who is born on Tuesday, he is sent home and another is picked at random until one who has a son that was born on Tuesday is found. He is instructed to tell you, “I have a son born on Tuesday.” What is the probability that the second child is also a son?

The probability that a father of two daughters will have a son born on Tuesday is zero. The probability that a father of differently-gendered children will have a son who is born on Tuesday is 1/7. The probability that a father of two sons will have a son born on Tuesday is 13/49. Among the fathers with two children, twice as many have a son and a daughter than two sons. Plugging these numbers into the formula for calculating the conditional probability will give us a probability of 13/27 for the second child to also be a son.

Now let’s go back to the original problem. Suppose you meet your friend who you know has two children and he tells you, “I have a son born on Tuesday.” What is the probability that the second child is also a son?

What puzzles me is that I’ve never run into a similar problem about daughters or mothers. I’ve discussed this math problem about these probabilities with many people many times. But I keep stumbling upon men who passionately defend their wrong solution. When I dig into why their solution is wrong, it appears that they implicitly assume that if a man has a daughter and a son, he won’t bother talking about his daughter’s birthday at all.

I’ve seen this so often that I wonder if this is a mathematical mistake or a reflection of their bias.

How to solve the original problem? The problem is under-defined. The solution depends on the reason the father only mentions one child, or the Tuesday.

The funny part of this story is that I, Tanya Khovanova, have two children. And the following statement is true: “I have a son born on Tuesday.” What is the probability that my second child is a son?

How many different months’ lengths are possible?

For “simplicity” let’s stick to the Gregorian calendar.

Lennart Green is an amazing magician who performs card tricks. He is so good that the judges at the competition of the International Federation of Magic Societies didn’t believe his tricks. They assumed that he used the help of stooges, and unfairly disqualified him. At the next competition he used a judge to assist him and won first place in the cards category.

I saw his performance twice. Both times he brought a woman to the stage, but each time it was a different woman. It was clear that he talked to each woman before the performance, presumably asking her permission. Furthermore, during his performances, both of the women looked slightly bored, implying that it might be not their first time. My first impression was that the women were a part of the act. I was fooled just as the judges had been fooled.

What can I say? Lennart Green isn’t skilled at picking up the right women. Watch his performance at TED, and remember that he proved that the assistants were clueless.

I got this problem from my friend, a middle-school math teacher, Tatyana Finkelstein.

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

I would like to add an extra twist to the problem above. It is conceivable that there might be several different strategies for finding the direction in which the weight of the fake coin deviates from the real coins. In this case it is better to choose a strategy that can redeem as many coins as possible — that is, to identify the maximum number of coins as real.

The number of coins you identify as real depends on the outcomes of your weighings. Then what is the precise definition of the best strategy?

Let us call a strategy k-redeem if after the weighings you are guaranteed to demonstrate that k coins are real, but you are not guaranteed to demonstrate that k+1 coins are real. Your task is to analyze two-weighing strategies and choose the most profitable one — the strategy that guarantees to redeem the largest possible number of coins, that is, a k-redeem strategy for the largest k.

Sara was born in Boston on February 29, 2008 at 11:00 am. Her parents were quite upset that their calendar-challenged daughter would only be able to celebrate her birthday once in four years. Luckily, science can help Sara’s parents. How? Sara can celebrate her birthday every year at the moment when the Earth passes the same point on its orbit around the Sun as when Sara was born.

Assuming that Sara lives her entire life in Boston and that the daylight savings time is not moved earlier into February, your task is to calculate the schedule of Sara’s birthday celebrations for 100 years starting from her birth. To simplify your homework, you can approximate one year as 365 days and 6 hours.

Joseph DeVincentis heard my prayers and created an index for MIT mystery hunt puzzles. He created it not because I requested it, but rather because he was on the writing team this year and they needed it. Anyway, finally there is an index.

I have to warn you, though, that this index was created for people who have already solved the puzzles, so the index contains hints for many of the problems and, on rare occasions, solutions.

Now I will do the math index for this year, and I promise that I will avoid big hints.

• Fun with Numbers — I got a very warm feeling from this puzzle. Some questions were right from my Number Gossip page and I knew some answers by heart.
• Planar Complex — A puzzle with complex numbers.
• Seeking Syren Scotchy — An advanced non-rectangular Nurikabe variation with colors and knight’s moves.
• Side by Side by Side — A massive logic puzzle.
• Counter Culture — So as not to reveal much info, I will just say that some math is involved in solving this puzzle.
• Expeditions — A logic puzzle that requires extra knowledge.
• Lighten Up — A Light-Up variation.
• Directions — I shouldn’t say.
• Message From Above — A math puzzle at the second stage.
• The Prodigious Riddle of Juno — A logic puzzle with a lot of if-then clauses.
• Bulls and Cows — Not surprisingly, a variation on Bulls and Cows
• Building a Mystery — Create a polyhedron.
• Trance State — Logic gates.
• Sequencer — Mirrors.
• 20,000 Leagues Under the Sea — A Battleship puzzle at the second stage.

I am so used to wise-men puzzles about hats, that I was pleasantly surprised when Leonid Makar-Limanov gave me a wise-men puzzle that didn’t include them.

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

If you are stuck, there are many approaches to try. You can attempt to solve the puzzle for a board of size 1 by 2, or for a board of size 1 by 3. Some might find it easier to solve a version in which you are allowed to have a multiple number of rocks on a cell, and the first wise man is permitted to add a rock to a cell that already contains rocks.

I promised to discuss how to improve the accuracy of your guessing at AMC 10/12, or other tests for that matter. There are two types of guessing. First, meta-guessing is when you do not look at the problem, but rather guess from just looking at the choices. Second, in the one I refer to as an educated-guess you do look at the problem. Instead of completely solving it, you try to deduce some information from the problem that will help you eliminate some of the choices. In this essay, I discuss both methods.

But first let me emphasize that solving problems is a more important skill than meta-guessing from a list of choices. Solving problems not only teaches you to think mathematically, but also increases your brain power. Spending time improving your meta-guessing skills can help you at multiple-choice tests and may give you insight into how test designers think, but this will not increase your math knowledge in the long run.

On the other hand, educated-guessing is a very useful skill to obtain. Not only can it improve your score during a test, the same methods can be applied to speed up the process of re-checking your answers before handing in the test. This skill will also come in handy when you start your research. Some problems in research are so difficult that even minor progress in estimating or describing your answer is beneficial.

Before discussing particular methods, let me remind you that AMC 10/12 is a multiple-choice competition with five choices for each question. The correct answer brings you 6 points. A wrong answer brings you 0 points, and not answering brings you 1.5 points. So if you randomly guess one of the five choices, your expected average score is 1.2 points, which is 0.3 less than your score for an unanswered question. Thus guessing is unprofitable on average.

However, if you can eliminate one choice, your expected average score becomes 1.5 points. In this case guessing doesn’t bring you points on average, but it does create some randomness in your results. For strategic reasons, you might prefer guessing, as I discussed in my earlier piece.

If you can eliminate two wrong choices, then guessing becomes profitable. A random guess out of three possibilities brings you 2 points, a better result than 1.5 points for an unanswered question. Even more, if you can eliminate three choices, then guessing will increase your score by 3 points on average.

Now that we’ve covered the benefits of excluding choices before guessing, I would like to discuss how to exclude choices by just looking at them. Let us take one of the problems from the 2002 AMC10B. Here are the choices: (-2,1), (-1,2), (1,-2), (2,-1), (4,4). The pair (4,4) is a clear outlier. I suggest that an outlier can’t be a correct choice. If (4,4) were the correct answer, then it would have been enough, instead of solving the problem, to use some intermediate arguments to choose it. For example, if you can argue that both numbers in the answer must be at least 2, or must be positive or be even, then you can get the correct answer without solving the problem. Any problem for which you can easily pick the correct answer without solving it is an unacceptably poor problem design. Thus, (4,4) can’t be the correct answer, and should be eliminated during guessing.

Let us look at a 2002 AMC10A problem with the following choices: 4/9, 2/3, 5/6, 3/2, 9/4. Test designers want to create choices that are plausible. They try to anticipate possible mistakes. In this set of choices, we can deduce that one of the mistakes that they anticipate is that students will confuse a number with its inverse. In this case 5/6 can’t be the correct answer. Otherwise, 6/5 would have been included as a choice. In another similar example from the 2000 AMC10 with choices -2, -1/2, 1/3, 1/2, 2, the designers probably hope that students will confuse numbers with their inverses and negations. Hence, we can exclude 1/3.

Sometimes the outlier might hint at the correct answer. Suppose you have the following list of choices: 2, 1/2π, π, 2π, 4π. The number 2 is an outlier here. Probably, the problem designers were contemplating that students might forget to multiply by π. In this case the likely correct answer would be 2π, because only from this answer can you get 2 by forgetting to multiply by π.

As an exercise, try to eliminate the wrong choices from the following set from a problem given at 2000 AMC10: 1/(2m+1), m, 1-m, 1/4m, 1/8m².

AMC designers know all of these guessing tricks, so they attempt to confuse the competitors from time to time by going against common sense. For example, in a 2002 AMC10A problem the choices were: -5, -10/3, -7/3, 5/3, 5. I would argue that -7/3 is a clear outlier because all the others are divisible by 5. Furthermore, there is no point in including so many answers with 3 in the denominator unless there is a 3 in the denominator of the correct answer. So I would suggest that one of -10/3 and 5/3 must be the answer. My choice would be 5/3, as there is a choice of 5 which I would assume is there for students who forgot to divide by 3. As I said the designers are smart and the actual answer is -10/3. They would have tricked me on this problem.

One of the best ways to design a multiple choice question is to have an arithmetic progression as a list of choices. There is no good way to eliminate some choices from 112, 113, 114, 115, 116. Unfortunately for people who want to get an advantage by guessing, many of the problems at AMC have an arithmetic progression as their choices.

Now that we’ve seen the methods of meta-guessing, let’s look at how to make an educated guess. Let us look at problem 1 in 2003 AMC10A.

What is the difference between the sum of the first 2003 even counting numbers and the sum of the first 2003 odd counting numbers?

Without calculations we know that the answer must be odd. Thus, we can immediately exclude three out of five choices from the given choices of 0, 1, 2, 2003, 4006. Parity consideration is a powerful tool in eliminating wrong answers. Almost always you can decide the parity of the answer much faster than you can calculate the answer. Similar to using parity, you can use divisibility by other numbers to have a fast elimination. Here is a problem from 2000 AMC10:

Mrs. Walter gave an exam in a mathematics class of five students. She entered the scores in random order into a spreadsheet, which recalculated the class average after each score was entered. Mrs. Walter noticed that after each score was entered, the average was always an integer. The scores (listed in ascending order) were 71, 76, 80, 82, and 91. What was the last score Mrs. Walter entered?

The first four numbers entered must be divisible by 4. The total of the given numbers is divisible by 4. Hence, the last number must also be divisible by 4. This reasoning eliminates three out of five choices.

Another powerful method is a rough estimate. Let us look at the next problem in 2003 AMC10A.

Members of the Rockham Soccer League buy socks and T-shirts. Socks cost $4 per pair and each T-shirt costs $5 more than a pair of socks. Each member needs one pair of socks and a shirt for home games and another pair of socks and a shirt for away games. If the total cost is $2366, how many members are in the League?

If we notice that the cost per person is more than $25, we can conclude that there are less than a hundred members in the League. Given the choices of 77, 91, 143, 182, and 286, we immediately can eliminate three of them.

Another method is to use any partial knowledge that you may have. Consider this problem from 2003 AMC10A:

Pat is to select six cookies from a tray containing only chocolate chip, oatmeal, and peanut butter cookies. There are at least six of each of these three kinds of cookies on the tray. How many different assortments of six cookies can be selected?

You might remember that there is a formula for this. Even if you do not remember the exact formula, you might still have a vague memory that the answer must be a binomial coefficient that somehow uses the number of cookies and the number of flavors. Looking at the choices — 22, 25, 27, 28, 29 — you can see that the only choice that appears in the first 10 rows of the Pascal’s triangle is 28. So you should go with 28.

It is easy to talk about easy problems; let us see what we can do about difficult ones. Consider the last problem on 2003 AMC10A:

Let n be a 5-digit number, and let q and r be the quotient and the remainder, respectively, when n is divided by 100. For how many values of n is q+r divisible by 11?

The choices are 8180, 8181, 8182, 9000, 9090. They can be naturally split into two groups: three choices below 9000 and the rest. By my rules of removing outliers the group of numbers below 9000 seems the more promising group. But I would like to discuss how to approximate the answer. There is no reason to believe that there is much correlation between remainders by 100 and divisibility by 11. There is a total of 90,000 5-digit numbers; among those numbers, approximately 90,000/11 = 8182 is divisible by 11, so we should go with the group of answers close to 8182.

Another way of thinking about this problem is the following. There are 900 different quotients by 100 to which we add numbers between 0 and 99. Thus for every quotient our sums are a set of 100 consecutive numbers. Out of 100 consecutive numbers usually 9, and rarely 10, are divisible by 11. Hence, the answer has to be less than 9000.

Sometimes methods you use for guessing can bring you the answer. Here is a problem from 2001 AMC12:

What is the product of all odd positive integers less than 10000? (A) 10000!/5000!², (B) 10000!/2⁵⁰⁰⁰, (C) 9999!/2⁵⁰⁰⁰, (D) 10000!/(2⁵⁰⁰⁰5000!), (E) 5000!/2⁵⁰⁰⁰.

For a rough estimate, I would take a prime number and see in what power it belongs to the answer. It’s simplest to consider a prime number p that is slightly below 5000. Then p should appear as a factor in the product of all odd positive integers below 10000 exactly once. Now let us look at the choices. Number p appears in 5000! once and in 10000! twice (as p and 2p). Hence, it appears in (A) zero times, and twice each in (B) and (C). We also can rule out (E) as the product of odd numbers below 10000 must be divisible by primes between 5000 and 10000, but 5000! doesn’t contain such primes. Thus the answer must be (D).

The method I just described won’t produce the formula. But the ideas in this method allow you to eliminate all the choices except the right one. Moreover, this method provides you with a sanity check after you derive the formula. It also helps to build your mathematical intuition.

I hope that you will find my essays about AMC useful. And good luck on February 9!

I teach students to solve math problems by appreciating the big picture, or by noticing the problem’s inner symmetries, or through a deep understanding of the problem. In the long run, one thing leads to another: such training structures their minds so that they are better at understanding mathematics and, as a consequence, they perform well at math competitions.

That is why, when AMC is still far away, I do not give my students a lot of AMC problems; rather, I pick problems that contain useful ideas. When I do give AMC problems, I remove the multiple choices, so they understand the problems completely, instead of looking for shortcuts. For example, this problem from AHSME 1999 is a useful problem with or without choices.

What is the largest number of acute angles that a hexagon can have?

As AMC approaches, we start discussing how to solve problems given multiple choices. Training students for AMC is noticeably different from teaching mathematics. For example, some problems are very specific to AMC. They might not even exist without choices. Consider this problem from the 2001 AMC12:

A polynomial of degree four with leading coefficient 1 and integer coefficients has two zeros, both of which are integers. Which of the following can also be a zero of the polynomial?

Here we really need the choices in order to pick one complex number, such that its real part is an integer or a half integer and, in addition, the product of the number with its conjugate produces an integer.

Sometimes the choices distract from solving the problem. For example, in the following problem from the 2005 AMC12, having choices might tempt students to try to eliminate them one by one:

The sum of four two-digit numbers is 221. None of the eight digits is 0 and no two of them are same. Which of the following is not included among the eight digits?

Without the choices, students might start considering divisibility by 9 right away.

On some occasions, the choices given for the problems at AMC make the problem more interesting. Here is an example from the 2000 AMC10:

Two different prime numbers between 4 and 18 are chosen. When their sum is subtracted from their product, which of the following numbers could be obtained?

The choices are 21, 60, 119, 180 and 231. We can immediately see that the answer must be odd. Because the span of the three remaining choices is so wide, we suspect that we can eliminate the smallest and the largest. Trying for 5 and 7 — the two smallest primes in the range — we can eliminate 21. Similarly, checking the two largest primes in the range, we can eliminate 231. This leaves us with the answer: 119. If the choices were different, we might have lost the interplay between the solution and the list of choices. Then, solving the problem would have been slower and more boring. There are ten pairs of prime numbers to check. And we would need on average to check five of them until we stumbled on the correct choice.

In other cases having multiple choices makes the problem more boring and less educational. Here is another problem from the same competition.

Two non-zero real numbers, a and b, satisfy ab = a – b. Find a possible value of a/b + b/a – ab.

Solving this problem without choices can teach students some clever tricks that people use when playing with expressions. Indeed, when we collect a/b + b/a into one fraction (a² + b²)/ab, we might remember that a² + b² is very close to (a – b)², and see from here that a/b + b/a – 2 is (a – b)²/ab, which, given the initial condition, equals ab. Thus, we can get the answer: 2.

On the other hand, if you look at the multiple choices first: -2, -1/2, 1/3, 1/2, 2, you might correctly assume that the answer is a number. Thus, the fastest way to solve it is to find an example. If a = 1, then b must be 1/2, and the answer must be 2. This solution doesn’t teach us anything new or interesting.

My next example from the 2002 AMC10 is similar to the previous one. The difference is that the solution with multiple choices is even more boring, while the solution without these choices is more interesting and beautiful.

Let a, b, and c be real numbers such that a – 7b + 8c = 4 and 8a + 4b – c = 7. Then a² – b² + c² is: 0, 1, 4, 7, or 8.

Given the choices, we see that the answer is a number. Hence we need to find any solution for the system or equations: a – 7b + 8c = 4 and 8a + 4b – c = 7. For example, if we let c = 0, we have two linear equations and two variables a and b that can be solved by a straightforward computation. Then we plug the solution into a² – b² + c².

Without knowing that the result is a number, we need to look at the symmetries of our two initial equations. We might discover a new rule:

If we have two expressions ax + by and bx – ay, where a and b are switched between variables and there is a change in sign, it is a good idea to square each of them and sum them up, because the result is very simple: (a² + b²)(x² + y²).

Hence, in our initial problem we need to move the term with b in our two linear equations to the right; then square them and sum up the results. This way we may get a very simple expression. And indeed, this trick leads to a solution and this solution provides insight into working with algebraic expressions.

This is the perfect problem to linger over, assuming you’re not in the middle of a timed competition. It might make you wonder for which parameters this problem works. You might discover a new theorem that allows you to create a very similar problem from any number that can be represented as a sum of two non-trivial squares in two different ways.

To prepare my students for AMC I need to teach them tricks that are not useful at USAMO, or in mathematics in general for that matter. Many tricks distract from new ideas or from understanding the problem. All they give us is speed.

This bothers me, but to pacify myself, I keep in mind that most of my students will not become mathematicians and it might be useful in their lives to be able to make split-second decisions among a small number of choices.

However, it seems like Americans have the opposite problem: we make quick decisions without thinking. I’m concerned that training for multiple choice tests and AMC competitions aggravates this problem.