Archive for the ‘Math Competitions’ Category.

Where is My Team Now?

I was at the 1976 International Mathematics Olympiad as part of the USSR team. There were eight people on the team and I decided to find out what they have achieved in the last 40 years. Here is the picture of our team. From left to right: Sergey Finashin, Yuri Burov, Nikita Netsvetaev, Boris Solomyak, Alexander Goncharov, Tanya Khovanova, Sergei Mironov, our chaperone Z.I. Moiseeva, our team leader A.P. Savin, no clue who this is (probably a translator), Piotr Grinevich.

USSR 1976 IMO Team

The list below is ordered by the number of points received at the Olympiad.

Tanya Khovanova, 39 points: a lecturer at MIT. I am interested in a wide range of topics, mostly recreational mathematics and have written 60 papers.

Sergey Finashin, 37 points: a full professor at Middle East Technical University in Turkey, who is interested in topology. He wrote 40+ papers.

Alexander Goncharov, 37 points: a full professor at Yale University. He is the highest achiever on the team. He won the EMS Prize in 1992 and was an Invited Speaker at the 1994 International Congress of Mathematicians. He is interested in geometry, representation theory, and mathematical physics. He published 75 papers in refereed journals.

Nikita Netsvetaev, 34 points: a full professor at Saint-Petersburg University in Russia. He is interested in topology and algebraic geometry and wrote 20 papers.

Boris Solomyak, 31 points: a full professor at Bar-Ilan University. He is interested in fractal geometry and dynamical systems and wrote 90 papers.

Piotr Grinevich, 26 points: a leading scientific researcher at the Landau Institute for Theoretical Physics. He also teaches at Moscow State University. He is interested in integrable systems and wrote 80 papers.

Sergei Mironov, 24 points. Sergey became very ill while he was an undergrad. He stopped doing mathematics.

Yuri Burov, 22 points. Yuri wrote two papers, but quit mathematics after graduate school. He died several years ago from multiple sclerosis.

Six out of eight people on our team became mathematicians. Or more precisely five an a half. I consider myself a mathematician and am grateful for my position at MIT, where I run innovative programs for young mathematicians. But in the research world, a lecturer is a nobody. This makes me sad. I had to take breaks from research in order to raise my two children. And then I had to work in the private sector in order to support them. I was the best on my team and now I am the only one who is not a full professor. If you are looking for an example of how gender affects a career in academia, this is it.

Share:Facebooktwitterredditpinterestlinkedinmail

The First Moscow Olympiad

The first Moscow Math Olympiad was conducted in 1935. Today, eighty years later, I decided to check it out. Most of the problems look standard, but some of the stereometry problems look too complicated. I found four problems that I really like: all of them are geometry problems.

Problem 1. The lengths of the sides of a triangle form an arithmetic progression. Prove that the radius of the inscribed circle is one third of one of the heights of the triangle.

Problem 2. A median, bisector, and height all originate from the same vertex of a triangle. You are given the three points that are the intersection points of the aforementioned median, bisector, and height with the circumscribed circle. Construct the triangle.

Problem 3. Find the set of points P on the surface of a cube such that the main diagonal subtends the smallest possible angle if viewed from P. Prove that the main diagonal subtends larger angles if viewed from other points on the surface. [Clarification: the two corners the main diagonal passes through don’t count.]

Problem 4. Given three parallel straight lines, construct a square such that three of its vertices belong to these lines.

Each of these problems has a powerful idea that solves it. You can try and solve these problems, but if you want help, the ideas are presented below as hints in a scrambled order.

  • Hint. Rotate by 90 degrees.
  • Hint. Consider a circumscribed sphere.
  • Hint. The line connecting the intersection point of the bisector with the circle and the circle’s center is parallel to the height.
  • Hint. Use Heron’s formula.
Share:Facebooktwitterredditpinterestlinkedinmail

Who Wants to Be a Bad Mathematician?

Round 1 of Who Wants to Be a Mathematician had the following math problem:

Bob and Jane have three children. Given that one child is their daughter Mary, what is the probability that Bob and Jane have at least two daughters?

In all such problems we usually make some simplifying assumptions. In this case we assume that gender is binary, the probability of a child being a boy is 1/2, and that identical twins do not exist.

In addition to that, every probability problem needs to specify the distribution of events over which the probability is calculated. This problem doesn’t specify. This is a mistake and a source of confusion. In most problems like this, the assumption is that something is chosen at random. In this type of problem there are two possibilities: a family is chosen at random or a child is chosen at random. And as usual, different choices produce different answers.

The puzzle above is not well-defined, even though this is from a contest run by the American Mathematical Society!

Here are two well-defined versions corresponding to two choices in randomization:

Bob and Jane is a couple picked randomly from couples with three children and at least one daughter. What is the probability that Bob and Jane have at least two daughters?

Mary is a girl picked randomly from a pool of children from families with three children. What is the probability that Mary’s family has at least two daughters?

Now, if you don’t mind, I’m going to throw in my own two cents, that is to say, my own two puzzles.

Harvard researchers study the influence of identical twins on other siblings. For this study they invited random couples with three children, where two of the children are identical twins.

  1. Bob and Jane is a couple picked randomly from couples in the study with at least one daughter. What is the probability that Bob and Jane have at least two daughters?
  2. Mary is a girl picked randomly from a pool of children participating in the study. What is the probability that Mary’s family has at least two daughters?
Share:Facebooktwitterredditpinterestlinkedinmail

From Tanks to Coins

I already wrote about my favorite problem from the 2015 All-Russian Math Olympiad that involved tanks. My second favorite problem is about coins. I do love almost every coin problem.

A coin collector has 100 coins that look identical. He knows that 30 of the coins are genuine and 70 fake. He also knows that all the genuine coins weigh the same and all the fake coins have different weights, and every fake coin is heavier than a genuine coin. He doesn’t know the exact weights though. He has a balance scale without weights that he can use to compare the weights of two groups with the same number of coins. What is the smallest number of weighings the collector needs to guarantee finding at least one genuine coin?

Share:Facebooktwitterredditpinterestlinkedinmail

Meta-Solving Multiple Choice

I explained to my AMSA students the idea of meta-solving multiple choice. Sometimes by looking at the choices without knowing what the problem is, it is possible to guess the correct answer. Suppose your choices are 2k, 2, 2/k, 10k, −2k. What is the most probable answer? There are several ideas to consider.

  • A problem designer considers different potential mistakes and tries to include the answers corresponding to most common mistakes. That means the answers corresponding to the mistakes are variations of the right answer. Thus, the right answer is a common theme in all the answers.
  • A problem designer tries not to allow the students to bypass the solution. So if only one of the choices is negative and the answer is negative, the students do not need to calculate the exact answer, they just need to see that it’s negative. That means the right answer cannot be the odd one out.

Both these considerations suggest a rule of thumb: the answers that are odd ones out are probably wrong. In the given example (2k, 2, 2/k, 10k, —2k), the second choice is an odd one out because it’s the only one that does not contain k. The third choice is an odd one out because it’s the only one in which we divide by k. The fourth choice is an odd one out because it’s the only one with 10 instead of 2. The last one is an odd one out because of the minus sign. Thus the most probable answer is 2k.

So I explained these ideas to my students and gave them a quiz, in which I took the 2003 AMC 10A test, but only gave them the choices without the problems. I was hoping they would do better than randomly guessing.

Luckily for me, I have six classes in a row doing the same thing, so I can make adjustments as I go along. Looking at the results of the first two groups of students, I discovered that they were worse than random. What was going on?

I took a closer look, and what do you know? Nobody marked the first or the last choice. The answers are in an increasing order, so the first is the smallest and the last is the largest. So these two numbers are odd ones out, in a way.

It is a good idea to consider 189 as an odd one out in the list 1, 2, 4, 5, 189. In many other cases, the fact that the number is either the smallest or largest is insufficient reason to consider it as the odd one out. For example, there is no reason to consider 1 to be an odd one out in the list 1, 2, 3, 4, 5. And the designers of AMC are good: a lot of problems have an arithmetic progression as a list of choices, where none of the numbers are obviously odd ones out.

To correct the situation of worse than random results, I discussed it with my students in my next classes. Problem designers cannot have a tradition in which the first answer is never the correct answer. If such a tradition existed, and people knew about it, that knowledge would help them guess. So the first answer should be correct approximately five times, which is a fifth of the total number of questions (25).

And we came up with a strategy. Use the odd one out method except for arithmetic progressions. Then add the choices to balance out the total number of the first answers, the second answers, etc.

That method worked. In my next four classes my students were better than random.

Share:Facebooktwitterredditpinterestlinkedinmail

Tanks at the 2015 All-Russian Math Olympiad

Yesterday I went online to check out the problems at the 2015 All-Russian Math Olympiad. I was stunned to discover a problem about tanks and fighter jets. I have never seen such a militarized problem before. The problem setup tells me something about the mood of people in Russia. It tells me that the mood has changed—alarmingly for the worse.

On the other hand, mathematically it was my favorite problem. So here it is.

The field is a 41 by 41 square made of square cells. A tank is camouflaged and hidden in one of the cells. A pilot flying a fighter jet above knows that the tank is there and wants to destroy it. If there is a tank in a cell, it will be hit by the shot directed at this cell. The pilot also knows that two hits are needed to destroy the tank. The tank will move to a neighboring cell immediately upon being hit, without breaking its camouflage. Other than that, the tank won’t move. What is the smallest number of shots required to guarantee that the tank is destroyed?

Share:Facebooktwitterredditpinterestlinkedinmail

2015 Moscow Math Olympiad

My favorite problem at the 2015 Moscow Olympiad was about an emperor and his wizards.

8-10th grade. Designed by I.V. Mitrofanov. The emperor invited 2015 of his wizards to a carnival. Some of the wizards are good and others are evil. The good wizards always tell the truth, whereas the evil ones are free to say anything they want. The wizards know who is who, but the emperor does not.

During the carnival, the emperor asks every wizard a yes-or-no question. Then he expels one of the wizards from his kingdom. The expelled wizard leaves through a magic door, which allows the emperor to realize what kind of wizard s/he was. After that the emperor starts the next round of questions and expels another wizard. He continues the rounds until he decides to stop.

Prove that it is possible to expel all the evil wizards, while expelling not more than one good wizard.

Two other problems at the Olympiad were noteworthy—because no competitor solved them:

11th grade. Designed by O.N. Kosuhin. Prove that it is impossible to put the integers from 1 to 64 (using each integer once) into an 8 by 8 table so that any 2 by 2 square considered as a matrix has a determinant that is equal to 1 or −1.

9th grade. Designed by A.Y. Kanel-Belov. Do there exist two polynomials with integer coefficients such that each of them has a coefficient with absolute value exceeding 2015, but no coefficient of their product has absolute value exceeding 1?

Share:Facebooktwitterredditpinterestlinkedinmail

A New Question about Old Coins

I want to come back to a middle-school Olympiad problem I posted a while ago.

Streamline School Olympiad 2000 (8th grade). You have six bags of coins that look the same. Each bag has an infinite number of coins and all the coins in the same bag weigh the same amount. Each different bag contains coins of a different weight, ranging from 1 to 6 grams exactly. There is a label (1, 2, 3, 4, 5, 6) attached to each bag that is supposed to correspond to the weight of the coins in that bag. You have only a balance scale. What is the least number of times you need to weigh the coins in order to confirm that the labels are correct?

The answer is unpretentious: one weighing is enough. We can take one 5-gram coin, two 4-gram coins, three 3-gram coins, four 2-gram coins and five 1-gram coins for the total of 35 grams. This number is not divisible by 6, so we can add one more 1-gram coin and weigh all of them against six 6-gram coins. I leave it to the reader to show that this solution works and to extrapolate the solution for any number of bags.

My new challenge is to find a weighing for the above problem using the smallest number of coins. What is the number of coins in such a weighing for a given number of bags?

I manually calculated this number for a small number of bags, but I would like to get a confirmation from my readers. Starting from 6 bags, I don’t know the answer. Can you help me?

Share:Facebooktwitterredditpinterestlinkedinmail

Intel ISEF Mathematics Awards 2014

The Intel International Science and Engineering Fair announced 2014 Grand Awards. I worked with three out of the top five mathematical award winners. Now I can brag that I’ve got my finger in more than half of the world’s best high-school math research.

To be clear: I wasn’t actually mentoring these projects, but I supervised two of the projects and I trained the third student for several years. So I’m proud to list the award-winning papers:

How interesting that each of these three students is from a different part of my present career. It certainly feels that I am in all the right places.

Share:Facebooktwitterredditpinterestlinkedinmail

Kolmogorov Student Olympiad in Probability

There are too many Olympiads. Now there is even a special undergraduate Olympiad in probability, called Kolmogorov Student Olympiad in Probability. It is run by the Department of Probability Theory of Moscow State University. I just discovered this tiny Olympiad, though it has been around for 13 years.

A small portion of the problems are accessible for high school students. These are the problems that I liked. I edited them slightly for clarity.

Second Olympiad. Eight boys and seven girls went to movies and sat in the same row of 15 seats. Assuming that all the 15! permutations of their seating arrangements are equally probable, compute the expected number of pairs of neighbors of different genders. (For example, the seating BBBBBBBGBGGGGGG has three pairs.)

Third Olympiad. One hundred passengers bought assigned tickets for a 100-passenger railroad car. The first 99 passengers to enter the car get seated randomly so that all the 100! possible permutations of their seating arrangements are equally probable. However, the last passenger decides to take his reserved seat. So he arrives at his seat and if it is taken he asks the passenger in his seat to move elsewhere. That passenger does the same thing: she arrives at her own seat and if it is taken, she asks the person to move, and so on. Find the expected number of moved passengers.

Third Olympiad. There are two 6-sided dice with numbers 1 through 6 on their faces. Is it possible to “load” the dice so that when the two dice are thrown the sum of the numbers on the dice are distributed uniformly on the set {2,…,12}? By loading the dice we mean assigning probabilities to each side of the dice. You do not have to “load” both dice the same way.

Sixth Olympiad. There are M green and N red apples in a basket. We take apples out randomly one by one until all the apples left in the basket are red. What is the probability that at the moment we stop the basket is empty?

Seventh Olympiad. Prove that there exists a square matrix A of order 11 such that all its elements are equal to 1 or −1, and det A > 4000.

Twelfth Olympiad. In a segment [0,1] n points are chosen randomly. For every point one of the two directions (left or right) is chosen randomly and independently. At the same moment in time all n points start moving in the chosen direction with speed 1. The collisions of all points are elastic. That means, after two points bump into each other, they start moving in the opposite directions with the same speed of 1. When a point reaches an end of the segment it sticks to it and stops moving. Find the expected time when the last point sticks to the end of the segment.

Thirteenth Olympiad. Students who are trying to solve a problem are seated on one side of an infinite table. The probability that a student can solve the problem independently is 1/2. In addition, each student will be able to peek into the work of his or her right and left neighbor with a probability of 1/4 for each. All these events are independent. Assume that if student X gets a solution by solving or copying, then the students who had been able to peek into the work of student X will also get the solution. Find the probability that student Vasya gets the solution.

Share:Facebooktwitterredditpinterestlinkedinmail