Tanya Khovanova's Math Blog

I wrote a series of essays about AMC competitions:

• Metasolving AMC 8
• AMC, AIME, USAMO Contradiction
• Multiple Choice Proofs
• Should You Check Your Answers During Tests?
• To Guess or Not to Guess?
• Solving Problems with Choices
• How to Boost Your Guessing Accuracy During Tests
• Choices or No Choices
• Problem Design for Multiple Choice Questions

This essay is next in the series. Although it is not strictly about AMC, it should be useful during any test when you need to check your answers. There are several important rules which are helpful.

Rule 0. Checking is important. If wrong answers are punished, then correcting a mistake brings more points than solving a new problem. In addition, problems that were solved are often easier than problems yet to be solved, so finding a mistake might be faster than solving a new problem.

Rule 1. Your checking methods must be fast. The tests are generally timed. This means that in order to check your answers, you need to sacrifice your work on the next problem.

Rule 2. Customize how you check according to your strengths and weaknesses. For example, if you tend to jump to conclusions about what the question is going to be, and as a result answer your anticipated question instead of the one that is actually on the test, then when you are checking you should start reading the problem from the question. Or, if you usually make mistakes in geometry problems, you should allocate more time to geometry problems when you are checking. If you never make mistakes in arithmetic problems then you do not need to check those.

Rule 3. Mark problems that might need checking. If you do not have enough time to check all the problems, check only those you are not sure about.

Rule 4. Do not repeat your solution when you check. While solving the problem your brain often creates a pathway from start to finish. If on this pathway your brain decided to believe that two plus two is five, very often during checking, your brain will make the same mistake again. Because of that it is crucial to use other methods for checking than repeating your reasoning. In case you can’t find a way to check your answers using a different method and have to repeat your reasoning, you should repeat it in a different order.

This rule is so important, that I am providing some methods to change your brain pathway when you are checking your answers.

Plug in. Plugging in the answer you found is much faster than finding it. Use this method whenever possible. It is perfect for problems like this one below from 2004 AMC10-A:

What is the value of x if |x – 1| = |x – 2|?

Plug in an intermediate result. Sometimes you can’t plug in the answer, but you can plug in an intermediate result. In the following problem from 2004 AMC10-B you can plug in the number of nickels and dimes:

Patty has 20 coins consisting of nickels and dimes. If her nickels were dimes and her dimes were nickels, she would have 70 cents more. How much are her coins worth?

Calculate something else related to your answer. For example a negation. Here is a problem from 2004 AMC10-B:

How many two-digit positive integers have at least one 7 as a digit?

If you calculated the answer directly, to check it you may want to calculate the number of two-digit positive integers that do not contain 7.

Create an example. Sometimes you solve a problem by reasoning, but to check it you might create a particular example. Here is a problem from 2001 AMC10:

Let P(n) and S(n) denote the product and the sum, respectively, of the digits of the integer n. For example, P(23) = 6 and S(23) = 5. Suppose N is a two-digit number such that N = P(N) + S(N). What is the units digit of N?

If we denote the tens digit by a and the units digit by b, then N = 10a + b, P(N) = a*b, and S(N) = a + b. We get an equation a(b+1) = 10a, from which the answer is 9. To check the answer we do not need to repeat the reasoning. It is enough to check that 19 is the sum of the product of its digits plus the digits.

Here is another problem from 2001 AMC10:

Suppose that n is the product of three consecutive integers and that n is divisible by 7. Which of the following is not necessarily a divisor of n?

The list of choices is: 6, 14, 21, 28, 42. Your solution might go like this: the product of three consecutive numbers is divisible by 6. Hence, n is divisible by 42. So, the answer must be 28. To check you might consider a product of three consecutive numbers: 5*6*7=210 and see that it is not divisible by 4, hence it is not divisible by 28.

Rule 5. Embrace the partial check. It is very important to check your answers fast. Sometimes you can gain speed if you do not check the problem completely, but check it partially. For example, you can check that your answer is one of the two correct answers. There are many methods for partial checking.

Try an example. Sometimes an example doesn’t guarantee that your choice is correct, but it increases your confidence in your answer. Here is another problem from 2001 AMC10:

The sum of two numbers is S. Suppose 3 is added to each number and then each of the resulting numbers is doubled. What is the sum of the final two numbers?

The choices are: 2S + 3, 3S + 2, 3S + 6, 2S + 6, 2S + 12. You can reason that increasing each summand by 3, increases the sum by 6. After that doubling each summand increases the resulting sum twice, so the answer is 2S + 12. To check the answer you can use an example. Usually an example doesn’t guarantee the confirmation of your answer, but it might help you eliminate some of the wrong answers. For example, if you choose zero and zero as your initial two numbers, then S = 0, and your transformation brings the result to 12, which confirms your answer 2S + 12. In this particular case, a very easy specific example excluded all the wrong answers.

Divisibility. Sometimes it is faster to calculate the remainder of the answer by some number.

For example, look at the following problem from 2003 AMC10:

What is the units digit of 13²⁰⁰³?

The choices are 1, 3, 7, 8, 9. We can immediately say that the answer must be an odd number.

Approximation check. One important example of a partial check is an approximation check. By estimating an approximate answer you might exclude most of the wrong answers. Consider this problem from 2001 AMC12:

How many positive integers not exceeding 2001 are multiples of 3 or 4 but not 5?

The divisibilities by 3, 4 or 5 shouldn’t correlate with each other. Approximately one third of those number are multiples of 3 and one quarter are multiples of 4. Let’s say that one twelfth are multiples of both 3 and 4. Hence, we estimate the portion of numbers that are multiples of 3 or 4 as 1/3 + 1/4 – 1/12 = 1/2. We have about 1,000 such numbers. The number of numbers that are, in addition, not divisible by 5, are less than that. So out of the given choice of (A) 768, (B) 801, (C) 934, (D) 1067, (E) 1167, we can immediately confirm that the answer is among the first three.

The methods above can be useful even if you do not have multiple choices. But if you do…

Rule 6. Use given choices as extra information. In the previous examples you saw how to use a partial check to exclude some of the choices. Here is a specific example from 2006 AMC10-A of how to exclude choices:

What non-zero real value for x satisfies (7x)¹⁴ = (14x)⁷?

The choices are: 1/7, 2/7, 1, 7, 14. If you solved the problem directly, to check it you can reason why other choices do not work. In this particular case it can be done very fast. 1/7 doesn’t work because the left part of the equation becomes 1 when the right is clearly not. 1 and 7 do not work because the left part is odd and the right is even; 14 doesn’t work because the left is clearly bigger than the right.

Rule 7. Use meta considerations. If you get into the mind of the designers you can better anticipate when you should check more thoroughly. Consider this problem from 2006 AMC10-A:

A digital watch displays hours and minutes with AM and PM. What is the largest possible sum of the digits in the display?

The most common mistake would be to assume that 12:59 supplies the largest sum, which is 17. But look at the choices: 17, 19, 21, 22, 23. When the designers are asking to find the largest number with some property, they assume that some students will make a mistake and chose a smaller number over a larger one. That means the designers would include this potential mistake among the choices. So the answer is extremely unlikely to be the smallest number on the list of choices. Thus, if you think the answer is 17, understanding how these problems are constructed should alert you to thoroughly check your answer. Indeed, the correct answer is 23 which corresponds to 9:59. Not surprisingly, it is the largest on the list of choices.

AMC 10/12 is coming on February 8 and HMMT on February 12. Happy checking.

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 am coaching my AMSA students for math competitions. Recently, I gave them the following problem from the 1964 MAML:

The difference of the squares of two odd numbers is always divisible by:
A) 3, B) 5, C) 6, D) 7, E) 8?

The fastest way to solve this problem is to check an example. If we choose 1 and 3 as two odd numbers, we see that the difference of their squares is 8, so the answer must be E. Unfortunately this solution doesn’t provide any useful insight; it is just a trivial calculation.

If we remove the choices, the problem immediately becomes more interesting. We can again plug in numbers 1 and 3 to see that the answer must be a factor of 8. But to really solve the problem, we need to do some reasoning. Suppose 2k + 1 is an odd integer. Its square can be written in the form 4n(n+1) + 1, from which you can see that every odd square has remainder 1 when divided by 8. A solution like this is a more profitable investment of your time. You understand what is going on. You master a method for solving many problems of this type. As a bonus, if students remember the conclusion, they can solve the competition problem above instantaneously.

This is why when I am teaching I often remove multiple choices from problems. To solve them, rough estimates and plugging numbers are not enough. To solve the problems the students really need to understand them. Frankly, some of the problems remain boring even if we remove the multiple choices, like this one from the 2009 AMC 10.

One can holds 12 ounces of soda. What is the minimum number of cans needed to provide a gallon (128 ounces) of soda?

It’s a shame that many math competitions do not reward deep analysis and big-picture understanding. They emphasize speed and accuracy. In such cases, plugging in numbers and rough estimates are useful skills, as I pointed out in my essay Solving Problems with Choices.

In addition, smart guessing can boost the score, but I already wrote about that, too, in How to Boost Your Guessing Accuracy During Tests and To Guess or Not to Guess?, as well as Metasolving AMC 8.

As the AMC 10 fast approaches, I am bracing myself for the necessity to include multiple choices once again, thereby training my students in mindless arithmetic.

I am starting yet another part-time job as the Head Mentor at PRIMES, a new MIT research program for high schoolers. I am very excited about this program, for it will be valuable not only to kids who want to become researchers, but also to kids who just want to see what research is like. Kids who want to learn to think in a new way will also find it highly useful.

PRIMES is in many ways similar to RSI, which it augments and complements. There are also a lot of differences. Keep in mind that I am only comparing PRIMES to the math part of RSI, with which I was working as a coordinator for two years. I do not know how RSI handles other sciences.

Different time scale. RSI lasts six weeks; PRIMES will take about a year. I already wrote about some peoples’ skepticism towards RSI in my piece called “Fast Food Research?.” PRIMES creates a more natural pace for research.

Choices. Because of the time schedule at RSI, students get their project as soon as they start. Students who realize by the end of the second week that they do not like their project are at a disadvantage: if they do not change their project, they’re stuck with something that does not inspire them or is too difficult, and if they do change their project, they won’t have enough time to do a great job. At PRIMES students will have time to talk to the mentors before starting their project, so that they can participate in choosing their project. Depending on how it goes later, they’ll have time to try several different directions. I believe that the best research comes from the heart: students who have the time and opportunity to shape their choices will be more invested in their project.

Application process. At RSI, The Center for Excellence in Education reviews the applications. Even though they usually do a superb job at sending us great students, I believe it would be an advantage if mentors were able to influence the review process, for they might find even better matches to their projects. At PRIMES, the mentors will have this opportunity to review the applications.

Geography. RSI accepts students from all over the US and from some other countries. PRIMES can only accept local students — those who live close enough to visit MIT once a week for four months. Because of this restriction, PRIMES is recruiting from a smaller pool of students than RSI. But for local students it means that it will be easier to get accepted to PRIMES than to RSI.

Coaching. At RSI, students get a lot of coaching. I think that every student is in close contact with four adults. Two of them are from the math department — mentor and coordinator (that’s me!) — and two tutors from CEE. PRIMES will have less coaching. A student will have a mentor and me, the head mentor. In addition, mentors might arrange for students to talk to the professors who originated their projects.

Immersion. RSI students are physically present. They are housed at MIT with the expectation that they completely devote their time to their research. Students at PRIMES will be integrating their research into the rest of their lives and their commitments. That will require good organizational skills and a lot of self-discipline. RSI students have discipline imposed on them by their situation — which may be an advantage to them.

Olympiads. While they are at RSI, students can’t go to IMO or other summer activities. This is why many strong Olympiad students choose not to go to RSI, or they turn down an RSI acceptance if in the meantime they have gotten on to an Olympic team. At PRIMES you can do both. It is possible to go to an Olympiad, in addition to writing a paper.

Grade. RSI students have to be juniors. There are no grade limitations for PRIMES. Thus, it is possible to go to PRIMES in one’s senior year. In this case, it may be too late to use PRIMES on college applications, but it is perfectly fine for the sake of research itself. Or it might be possible to go to PRIMES as a sophomore, and then apply for RSI the next year. This will strengthen the student’s application for RSI.

RSI is well-established and has proven itself. PRIMES is new and hopefully will offer young mathematicians additional opportunities to try research.

I think that the American system of education creates a lot of pressure for teachers to drill their students for standardized tests and multiple choice questions. This blocks creative thinking. Every program like PRIMES is very good for unleashing students’ creativity and contributing to the development of the future thinkers of American society.

From the 1966 Moscow Math Olympiad:

Prove that you can choose six weights from a set of weights weighing 1, 2, …, 26 grams such that any two subsets of the six have different total weights. Prove that you can’t choose seven weights with this property.

Let us define the sequence a(n) to be the largest size of a subset of the set of weights weighing 1, 2, …, n grams such that any subset of it is uniquely determined by its total weight. I hope that you agree with me that a(1) = 1, a(2) = 2, a(3) = 2, a(4) = 3, and a(5) = 3. The next few terms are more difficult to calculate, but if I am not mistaken, a(6) = 3 and a(7) = 4. Can you compute more terms of this sequence?

Let’s see what can be said about upper and lower bounds for a(n). If we take weights that are different powers of two, we are guaranteed that any subset is uniquely determined by the total weight. Thus a(n) ≥ log₂n. On the other hand, the total weight of a subset has to be a number between 1 and the total weight of all the coins, n(n+1)/2. That means that our set can have no more than n(n+1)/2 subsets. Thus a(n) ≤ log₂(n(n+1)/2).

Returning back to the original problem we see that 5 ≤ a(26) ≤ 8. So to solve the original problem you need to find a more interesting set than powers of two and a more interesting counting argument.

The International Math Olympiad started in Eastern Europe in 1959. Romania was the first host country. The Olympiad grew and only in 1976 did it move outside the Eastern bloc. The competition was held in Austria.

I was on the Soviet team in 1975 and 1976, so I was able to compare competitions held in Eastern vs. Western countries. Of course, the Austrian Olympiad was much better supported financially, but today I want to write about the differences in how our team was prepped.

Before our travel to Austria the Soviet team members were gathered in a room with strangers in suits for a chat. I assumed that we were talking to the KGB. They gave us a series of instructions. For example, they told us not to leave the campus during the competition, to always walk in groups, and to avoid talking to kids from countries that are enemies of the USSR. They warned us that they would be watching, and I was scared to death.

Now that I am older and wiser, I understand that their goal was to frighten us. Our team traveled with adult supervisors, who were trusted by the KGB. But for several days during the grading period of the competition, our supervisors were not allowed to see us. So the KGB wanted us to be too afraid to be very adventurous when we were left on our own.

In addition, the KGB had a Jewish problem. In general, Jews were not allowed to go abroad. I had many Jewish friends who qualified for the pre-IMO math camp where the team was chosen, but who were not able to get on the IMO because of delays with their travel documents. Some local bureaucrats were eager to impress the KGB and therefore held up visas for Jewish students, preventing them from being on the team. But the team selection process itself wasn’t yet corrupt in 1976. So every year despite the efforts of the system, some young Jewish mathematicians would end up on the team.

Before 1976, the Olympiad was in the Eastern bloc, so the KGB wasn’t quite so concerned about having Jewish members on the team. But Austria was not only a Western country, it was also the transition point for Jewish refugees from the Soviet Union. The speed with which the IMO moved their competition to a Western country was much faster than the Soviet bureaucratic machine could build a mechanism for completely preventing Jews from joining the team.

One very strong candidate, Yura Pass, didn’t get his documents, but two other Jewish boys made it on to the team that was going to Austria. They were joking that they would be the only Soviet Jews who would go to Austria and actually come back. They did come back, only to go forward later: both are now math professors working in the US.

Because we had Jewish members on our team, it gave the KGB a special extra reason to scare us. But the biggest pressure was to win. We were told that 1976 was the most important year for the Soviet team to be the best. We were told that capitalist countries spread rumors that the judges in Eastern bloc countries favored the Soviet team and that the relative success of the Soviet team throughout the years had not been fully deserved. Now that the competition was in Austria, the suits told us, the enemies of the USSR were hoping for the downfall of the Soviet team. Our task was to prove once and for all that the Soviet students were the best at math, and that the rumors were unfounded. We had to win the team competition not only to prove ourselves, but also to clear the name of the Soviet team for all the previous years.

We did have a very strong team. The USSR came out first with 250 points, followed by the UK with 214 points and the USA with 188 points. Out of nine gold medals, we took four.

We could have gotten one more gold medal if Yura Pass had been allowed on the team. Yura was crushed by the machine’s treatment of Jews and soon afterwards quit mathematics.

My coauthor Konstantin Knop publishes cute math problems in his blog (in Russian). Recently he posted a coin weighing problem that was given at the 2010 Euler math Olympiad in Russia to eighth graders. The author of the problem is Alexander Shapovalov.

Among 100 coins exactly 4 are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin. How would we find at least one genuine coin using two weighings on a balance scale?

It is conceivable that your two weighings may find more than one genuine coin. The more difficult question that Konstantin and his commentators discuss is the maximum number of genuine coins you can guarantee to identify in two weighings. Konstantin and the others propose 14 as the answer, but do not have a proof yet.

I wonder if one of you can find a bigger number than Konstantin or alternatively a proof that indeed 14 is the largest possible.

You might ask, considering the title of this piece, why I think that coins are scary. No, I am not afraid of coins. It scares me that this problem was given to eighth graders in Russia, because I cannot imagine that it would be given to kids that age in the USA.

By the way, ten eighth grade students in Russia solved this problem during the competition.

A week ago I chatted with my son Sergei about memorable math problems. He mentioned problem 5 from USAMO 2007. The problem can be reduced to the following:

Prove that (x⁷ + 1)/(x + 1) is composite for x = 7⁷ⁿ, where n is a non-negative integer.

Perhaps Sergei remembered this problem because as far as he knew, he was the only one in that competition to solve it. That made me curious as to how he solved it. His solution is available as solution 2 at the Art of Problem Solving website. His solution seemed mysterious and impossible to invent on the spot. I became even more curious to understand the thought process underlying his solution.

Here is his recollection:

We need to factor x⁶ − x⁵ + x⁴ − x³ + x² − x + 1. If such factoring existed it would have been known. Therefore, we need to somehow use the fact that x = 7⁷ⁿ. What is the simplest way to factor? We should try to represent the polynomial in question as the difference of squares. Luckily, x is an odd power of 7. We can make it a square if we multiply or divide it by 7 or another odd power of 7. So with a supply of squares on one side, we need to find a match for one of them to build the difference.

Let us simplify the problem and see what happens for (y³ + 1)/(y + 1) for y = 3³ⁿ, when n = 1. In other words we want to represent 703 as a difference of squares. This can be done: 703 = 28² − 9². Now let us see how we can express 28² and 9² through y which in this case is equal to 27. The first term is (y + 1)², and the second is 3y.

Now let’s go back to 7 and x, and check whether (x + 1)⁶ − (x⁶ − x⁵ + x⁴ − x³ + x² − x + 1) is 7x. Oops, no. The difference is 7x⁵ + 14x⁴ + 21x³ + 14x² +7x. On the plus side, it is divisible by 7x which we know is a square. The leftover factor is x⁴ + 2x³ + 3x² +2x + 1, which is a square of x² +x + 1.

The problem is solved, but the mystery remains. The problem can’t be generalized to numbers other than 3 and 7.

I decided to take a closer look at the Putnam Competition. I analyzed the results of the three top contenders for the best Putnam teams: Harvard, MIT, Princeton. I looked at the annual number of Putnam Fellows from each of these three schools starting from 1994.

As you may notice MIT couldn’t even generate a Putnam Fellow until 2000, but starting from 2003 MIT consistently had more Putnam Fellows than Harvard or Princeton.

Richard Stanley, the coach of the MIT team, kindly sent me the statistics for the most recent competition, held in 2009.

Furthermore, MIT had 40% in the top 5, 33% in the top 15, 32% in the top 25, and 35% in the top 81. For comparison, in the top 81, MIT had 28 winners — more than the next three schools together: Caltech 11, Harvard 9, Princeton 7.

No comment.