Archive for the ‘Math Competitions’ Category.

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

Math Kangaroo’s Logic Puzzle

My AMSA students loved the following puzzle from the 2003 Math Kangaroo contest for grades 7-8:

The children A, B, C and D made the following assertions.

  • A: B, C and D are girls.
  • B: A, C and D are boys.
  • C: A and B are lying.
  • D: A, B and C are telling the truth.

How many of the children were telling the truth?
A) 0   B) 1   C) 2   D) 3   E) Impossible to determine

Share:Facebooktwitterredditpinterestlinkedinmail

Discussing a Problem from the Moscow Olympiad

I recently posted the following problem from the Moscow Olympiad:

There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.

  • Prove that all the people have exactly the same number of acquaintances at this meeting.
  • Show that n can be greater than 4.

Here is the proof for the first bullet. Choose a person X. Take a pair of X‘s acquaintances. These two acquaintances have to share two acquaintances between themselves one of whom is X. In other words, we have described a function from all pairs of X‘s acquaintances to people who are not X. On the other hand, for every person who is not X, s/he and X share a pair of acquaintances. Hence, there is a bijection between people other than X and all pairs of X‘s acquaintances. If the number of X‘s acquaintances is a, and the total number of people is t, then we have shown that (a choose 2) = t−1. As this is true for any X, we see that everyone has the same number of acquaintances. Moreover, this situation can happen only if t−1 is a triangular number.

But wait. There is more work that needs to be done. The smallest triangular number is 1. That means that t might be 2. If there are two people at the meeting, then the condition holds: they have 0 common acquaintances. The next triangular number is 3. So we need to see what would happen if there are four people. In this case, if everyone knows each other, it works. This is why the second bullet asks us to find an example of the situation with more than four people, because four people is too easy.

Let’s look at larger triangular numbers. The situation described in the problem might also happen when there are:

  • 7 people total and everyone has 4 acquaintances,
  • 11 people total and everyone has 5 acquaintances,
  • 16 people total and everyone has 6 acquaintances,
  • and so on: a(a−1)/2 + 1 people total and everyone has a acquaintances.

The official Olympiad solution suggests the following example for 16 people total. Suppose we put 16 people in a square formation so that everyone knows people in the same row and column. I leave it to the reader to check that every two people share exactly two acquaintances.

Let me prove that there is no solution for a total of seven people. If there were a solution, then each person would have to know four people. My first claim is that the acquaintance graph can’t contain a four-clique. Suppose there is a four-clique. Then each person in the clique has to have another acquaintance outside of the clique to make it up to four. In addition, this extra acquaintance can’t be shared with anyone in the clique, because the clique contains all the acquaintances that they share. This means we need to have at least four more people.

Next, suppose two people a and b know each other and share an acquaintance c. Any two people in this group of three has to have another shared acquaintance, who is not shared with the third person. That is, there should be another person who is the acquaintance of a and b, a different person who is an acquaintance of a and c, and a third person who is acquainted with b and c. These three extra people are all the acquaintances of a, b, and c. Which means the last person who is not acquainted with a, b, or c, has less than for four acquaintances.

Let’s look at a more difficult problem that I offered at the same posting:

There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.

  • Prove that all the people have exactly the same number of acquaintances at this meeting.
  • Is it possible that n can be greater than 2k?

As in the previous solution, we see that a, the number of acquaintances of a person and t, the total number of people, satisfy the following equation: (a choose k) = (t−1 choose k−1).

For example, if k = 3, the equation becomes (a choose 3) = (t−1 choose 2). This is a question of finding numbers that are both tetrahedral and triangular. They are known and their sequence, A027568, is finite: 0, 1, 10, 120, 1540, 7140. The corresponding number of acquaintances is 3, 5, 10, 22, 36 and the total number of people is 3, 6, 17, 57, 121. The first trivial example involves 3 people who do not know each other. The next example is also simple: it has 6 people and everyone knows everyone else.

What about non-trivial examples? If there are 17 people in the group, then each person has to know 10 people. Does the acquaintance graph exist so that every group of three people share 3 acquaintances?

We see that the problem consists of two different parts. First, we have to solve the equation that equates two binomial coefficients. And second, we need to build the acquaintance graph. Both questions are difficult. We see that for k = 2 we have an infinite number of solutions to the equation with binomial coefficients. For k = 3, that number is finite. What happens with other k? If there are 2k people and they all know each other, then this works. But are there other non-trivial solutions? I am grateful to Henry Cohn for directing me to the works of Singmaster who studied non-trivial repetitions of numbers in Pascal’s triangle. In particular, Singmaster showed that the equation (n+1 choose k+1) = (n choose k+2) has infinitely many solutions given by n = F2i+2F2i+3−1 and k = F2iF2i+2−1.

This sequence generates the following non-trivial examples (15 choose 5) = (14 choose 6), (104 choose 39) = (103 choose 40), and so on. That means it might be possible that there is a group of 16 people so that every 6 people share 6 acquaintances. In this situation every person must know everyone else except for one other person. That leads us to the structure of the acquaintance graph: it is a complement to the perfect matching graph. I leave it to my readers to check that the corresponding acquaintance graph doesn’t exist. Are there examples of two binomial coefficients that equal each other and that lead to an acquaintance graph that can be built?

Now that I’ve tackled the solution to this Olympiad problem, I see that I generated more questions than I answered.

Share:Facebooktwitterredditpinterestlinkedinmail