Archive for the ‘Math Competitions’ Category.

Two Dice

My friend Alex Ryba uses interesting math questions in the CUNY Math Challenge. For the 2016 challenge they had the following problem.

Problem. Eve owns two six-sided dice. They are not necessarily fair dice and not necessarily weighted in the same manner. Eve promises to give Alice and Bob each a fabulous prize if they each roll the same sum with her dice. Eve wishes to design her two dice to minimize the likelihood that she has to buy two fabulous prizes. Can she weight them so that the probability for Alice and Bob to get prizes is less than 1/10?

The best outcome for Eve would be if she can weight the dice so that the sum is uniform. In this case the probability that Alice and Bob get the prizes is 1/11. Unfortunately for Eve, such a distribution of weight for the dice is impossible. There are many ways to prove it.

I found a beautiful argument by Hagen von Eitzen on the stack exchange: Let ai (correspondingly bi) be the probabilities that die A (correspondingly B) shows i + 1. It would be very useful later that that i ranges over {0,1,2,3,4,5} for both dice. Let f(z) = ∑ aizi and g(z) = ∑ bizi. Then the desired result is that f(z)g(z) = ∑j=010 zj/11. The roots of the right side are the non-real roots of unity. Therefore both f and g have no real roots. So, they must both have even degree. This implies a5=b5=0 and the coefficient of z10 in their product is also 0, contradiction.

Alex himself has a straightforward argument. The probabilities of 2 and 12 have to be equal to 1/11, therefore, a0b0 = a5b5 = 1/11. Then the probability of a total 7 is at least a0b5 + a0b5. The geometric mean of a0b5 and a0b5 is 1/11 (from above), so their arithmetic mean is at least 1/11 and their sum is at least 2/11. Therefore, the uniform distribution for sums is impossible.

So 1/11 is impossible, but how close to it can you get?

Share:Facebooktwitterredditpinterestlinkedinmail

My 1975 IMO Team

My IMO Team, 1975

I just got this picture from my friend Victor Gutenmacher, which I never saw before. My 1975 IMO team is posing at our training grounds before the Olympiad trip to Bulgaria.

Left to right: Boris Yusin, Yuri Ionin, Zoya Moiseyeva (front), Gregory Galperin (back), me, Ilya Yunus, Valentin Skvortsov, Aleksandr Kornyushkin, Sergei Finashin, Sergei Fomin (front), Alexander Reznikov (back), Yuri Shmelev (front), Yuri Neretin (back), Victor Gutenmacher.

Our coaches are in the shot as well. Surprisingly, or not surprisingly, all of them moved to the USA. Yuri Ionin, now retired, was a professor at Central Michigan University. Gregory Galperin is a professor at Eastern Illinois University. Sergei Fomin is a professor at the University of Michigan. Victor Gutenmacher worked for BBN Technologies and Siemens PLM Software, and is now retired.

There are two more adults in the picture: Valentin Anatolievich Skvortsov, our leader and Zoya Ivanovna Moiseyeva, our deputy leader. Skvortsov was working at the math department of Moscow State University at that time. The University was angry that he didn’t block some students with Jewish heritage from the team thus allowing them to be accepted to Moscow State University without exams. I wrote a story of how Zoya persuaded Alexander Reznikov not to go to Moscow University to help Valentin. It ruined Alexander’s live, and didn’t even help Valentin. 1975 was Valentin’s last trip as the leader.

Share:Facebooktwitterredditpinterestlinkedinmail

Solutions to Geometry Puzzles from the 35-th Lomonosov Tournament

I recently posted two geometry problems. Now is the time for solutions:

Problem 1. Is it possible to put positive numbers at the vertices of a triangle so that the sum of two numbers at the ends of each side is equal to the length of the side?

One might guess that the following numbers work: (a+b-c)/2, (b+c-a)/2 and (c+a-b)/2, where a, b, and c are the side lengths. But there exists a geometric solution: Construct the incircle. The tangent points divide each side into two segment, so that the lengths of the segments ending at the same vertex are the same. Assigning this length to the vertex solves the problem. Surprisingly, or not surprisingly, this solution gives the same answer as above.

Problem 2. Prove that it is possible to assign a number to every edge of a tetrahedron so that the sum of the three numbers on the edges of every face is equal to the area of the face.

The problem is under-constrained: there are six sides and four faces. There should be many solutions. But the solution for the first problem suggests a similar idea for the second problem: Construct the inscribed sphere. Connect a tangent point on each face to the three vertices on the same face. This way each face is divided into three triangles. Moreover, the lengths of the segments connecting the tangent points to a vertex are the same. Therefore, two triangles sharing the same edge are congruent and thus have the same area. Assigning this area to each edge solves the problem.

There are many solutions to the second problem. I wonder if for each solution we can find a point on each face, so that the segments connecting these points to vertices divide the faces into three triangles in such a way that triangles sharing an edge are congruent. What would be a geometric meaning of these four points?Share:Facebooktwitterredditpinterestlinkedinmail

2015 Coin Problem Solution

A while ago I posted my second favorite problem from the 2015 All-Russian Math Olympiad:

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?

Now it’s solution time. First we show that we can do this in 70 weighings. The strategy is to compare one coin against one coin. If the scale balances, we are lucky and can stop, because that means we have found two real coins. If the scale is unbalanced, the heavier coin is definitely fake and we can remove it from consideration. In the worst case, we will do 70 unbalanced weighings that allow us to remove all the fake coins, and we will find all the real coins.

The more difficult part is to show that 69 weighings do not guarantee finding the real coin. We do it by contradiction. Suppose the weights are such that the real coin weighs 1 gram and the i-th fake coin weighs 100i grams. That means whatever coins we put on the scale, the heaviest pan is the pan that has the fake coin with the largest index among the fake coins on the scale.

Suppose there is a strategy to find a real coin in 69 weighings. Given this strategy, we produce an example designed for this strategy, so that the weighings are consistent, but the collector cannot find a real coin.

For the first weighing we assign the heaviest weight, 10070 to one of the coins on the scale and claim that the pan with this coin is heavier. We continue recursively. If a weighing has the coins with assigned weights, we pick the heaviest coin on the pans and claim that the corresponding pan is heavier. If there are no coins with assigned weights on pans, we pick any coin on the pans, assigned the largest available weight to it and claim that the corresponding pan is heavier.

After 69 weighings, not more than 69 coins have assigned weights, while all the weighings are consistent. The rest of the coins can have any of the leftover weights. For example, any of the rest of the coins can weigh 100 grams. That means that there is no coin that is guaranteed to be real.Share:Facebooktwitterredditpinterestlinkedinmail

2014 Math Festival in Moscow

I stumbled upon a couple of problems that I like while scanning the Russian website of Math Festival in Moscow 2014. The problems are for 7 graders.

Problem. Inside a 5-by-8 rectangle, Bart draws closed paths that follow diagonals of 1-by-2 rectangles. Find the longest possible path.

This problem is really very difficult. The competition organizers offered an extra point for every diagonal on top of 16. The official solution has 24 diagonals, but no proof that it’s the longest. I’m not sure anyone knows if it is the longest.

Here is another problem:

Problem. Alice and Bob are playing a game. They start with two numbers: 2014 and 2015. In one move a player can do one of two things:

  1. subtract one of the numbers by one of the non-zero digits in any of the two numbers or,
  2. divide one number by two if the number is even.

The winner is the person who is the first to get a one-digit number. Assuming that Alice starts, who wins?

Share:Facebooktwitterredditpinterestlinkedinmail

My Favorite Problems from the Moscow Math Olympiad 2016

I picked four problems that I liked from the Moscow Math Olympiad 2016:

Problem 1. Ten people are sitting around a round table. Some of them are knights who always tell the truth, and some of them are knaves who always lie. Two people said, “Both neighbors of mine are knaves.” The other eight people said, “Both neighbors of mine are knights.” How many knights might be sitting around the round table?

Problem 2. Today at least three members of the English club came to the club. Following the tradition, each member brought their favorite juice in the amount they plan to drink tonight. By the rules of the club, at any moment any three members of the club can sit at a table and drink from their juice bottles on the condition that they drink the same amount of juice. Prove that all the members can finish their juice bottles tonight if and only if no one brings more than the third of the total juice brought to the club.

Problem 3. Three piles of nuts together contain an even number of nuts. One move consists of moving half of the nuts from a pile with an even number of nuts to one of the other two piles. Prove that no matter what the initial position of nuts, it is possible to collect exactly half of all the nuts in one pile.

Problem 4. N people crossed the river starting from the left bank and using one boat. Each time two people rowed a boat to the right bank and one person returned the boat back to the left bank. Before the crossing each person knew one joke that was different from all the other persons’ jokes. While there were two people in the boat, each told the other person all the jokes they knew at the time. For any integer k find the smallest N such that it is possible that after the crossing each person knows at least k more jokes in addition to the one they knew at the start.

Spoiler for Problem 2. I want to mention a beautiful solution to problem 2. Let’s divide a circle into n arcs proportionate to the amount of juice members have. Let us inscribe an equilateral triangle into the circle. In a general position the vertices of the triangle point to three distinct people. These are the people who should start drinking juices with the same speed. We rotate the triangle to match the drinking speed, and as soon as the triangle switches the arcs, we switch drinking people correspondingly. After 120 degree rotation all the juices will be finished.Share:Facebooktwitterredditpinterestlinkedinmail

Geometry Puzzles from the 35-th Lomonosov Tournament

Problem 1. It is true that it is possible to put positive numbers at the vertices of a triangle so that the sum of two numbers at the ends of each side is equal to the length of the side?

This looks like a simple linear algebra question with three variables and three equations. But it has a pretty geometrical solution. What is it?

Problem 2. Prove that it is possible to assign a number to every edge of a tetrahedron so that the sum of the three numbers on the edges of every face is equal to the area of the face.

Again we have six sides and four faces. There should be many solutions. Can you find a geometric one?Share:Facebooktwitterredditpinterestlinkedinmail

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