Who Is Left?

Centaurs, manticores, and minotaurs roam their planet. Their society is very democratic: any two animals can become sex partners. When two different species mate, their orgasm is so potent that they merge into one creature of the third species. For example, once one centaur and one manticore make love, they are reborn as one minotaur. At the beginning of the year 2016 there were 2016 centaurs, 2017 manticores, and 2018 minotaurs. They mated non-stop and at the end of the year only one creature was left on the planet. Which one?

This is one of those puzzles that I love-hate. I hate it because it is easy to answer this puzzle by inventing a specific mating pattern that ends with one animal. It is possible to get the correct answer without seeing the beauty. I love it because there is beauty in the explanation of why, if the mating ends with one animal, it has to be a specific animal.

The solution is charming, but being a mathematician this problem makes me wonder if ii is always possible to end with one animal. So I add another puzzle.

Describe the sets of parameters for which it is impossible to end up with one creature.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

A Faulty Scale

Today I have two new coin puzzles that were inspired by my son, Alexey Radul:

You have N > 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is lighter than the real ones. You also have a balance scale which might or might not be faulty. A faulty scale differs from a normal one in reversing the sense of unbalanced weighings—it shows a lighter pan as heavier and vice versa (but still shows equal-weight pans as weighing the same). What is the smallest number of weighings you need in order to figure out whether the scale is faulty?

If you think about it, this problem is isomorphic to a known problem I wrote about before:

You have N ≥ 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is either lighter than the real ones or heavier than the real ones. You also have a normal balance scale. What is the smallest number of weighings you need in order to figure out whether the fake coin is lighter or heavier?

To make things more interesting let’s mix the problems up.

You have N > 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is lighter than the real ones. You also have M > 1 identical-looking balance scales. All but one of them are normal and one is faulty. The faulty scale differs from a normal one in reversing the sense of unbalanced weighings—it shows a lighter pan as heavier and vice versa (but still shows equal-weight pans as weighing the same). What is the smallest number of total weighings needed to figure out which scale is faulty?

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

How Many Triangles?

The following problem was at a 2016 entrance test for the MIT PRIMES STEP program.

I drew several triangles on a piece of paper. First I showed the paper to Lev and asked him how many triangles there were. Lev said 5 and he was right. Then I showed the paper to Sasha and asked him how many triangles there were. Sasha said 3 and he was right. How many triangles are there on the paper? Explain.

The intended answer was 8: there were 5 triangles on one side of the paper and 3 on the other.

Most of the students didn’t think that the paper might be two-sided, but they came up with other inventive ideas. Below are some of their pictures, and I leave it to you to explain why they work. All the students who submitted these pictures got a full credit for this problem on the test.

Example 7Example 5Example 4Example 3Example 1Example 2Example 6
Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Should You Apply to PRIMES?

If you are a high-school student who wants to conduct research in mathematics, you should check out the MIT PRIMES program. If you enjoy solving the problems in our entrance test, that’s the first indication that you might want to apply. But to determine if the program is right for you, and you are right for the program, please read the following questions and answers which have been prepared for you by Tanya Khovanova, the PRIMES Head Mentor. (This only addresses applications to PRIMES Math, and only to the research track)

Question: I do not like math competitions. Should I apply?
Answer: Math competitions are completely separate from research in mathematics. If you enjoy thinking about mathematics for long periods of time and are fascinated by our test questions, you should apply.

Question: I am good at math, but I really want to be a doctor. Should I apply?
Answer: No. PRIMES requires a huge time commitment, so math should really be your most significant interest.

Question: I want to get into Harvard, and PRIMES looks good on a resume. Should I apply?
Answer: PRIMES does look good on a resume. But if you are more passionate about, say, climate change than math, what would Harvard’s admission committee see? Our experience in the program is that if math isn’t your top interest, your math student may not be sufficiently impressive to be accepted at Harvard as a math researcher. At the same time, you will not be accepted as the top climate change student as you didn’t invest your time in that. Math research is a hard way to earn points for college. See also, the essay, Thoughts on research by Simon Rubinstein-Salzedo.

Question: My parents want me to apply. Should I apply?
Answer: Your parents will not be accepted to the program. Do not apply if you do not really, really want to.

Question: Your website suggests that I should spend ten hours a week on the PRIMES project. I can only spend five. But I am a genius and faster than other people.
Answer: We already assume that you are a genius and faster than anyone else you know. Five hours a week are not enough for a successful project.

Question: I looked at the past PRIMES projects and nothing excites me as much as my current interest in Pascal’s triangle. I doubt I should apply.
Answer: When you start working on a project, you will learn a lot about it. You will understand why, for example, Cherednik algebras are cool. The excitement comes with knowledge and invested time. Not yet being excited about Cherednik algebras is not a good reason not to apply. Besides a lot of exciting mathematics is done between several different fields.

Question: I really want to do nothing else than study Pascal’s triangle.
Answer: We try to match our projects to students’ interests as much as we can. But we almost never can fulfill a specific request as above. You might get a project related to Young diagrams, which are connected to quantum Pascal’s triangle. If this connection doesn’t excite you, you shouldn’t apply.

Question: I think I will be better positioned for research if I spend five more years studying.
Answer: There is nothing wrong with this approach. For many years the standard was to start research in graduate school. Our program is innovative. At PRIMES we are trying a different model. It may sound scary, but you will learn everything you need to know in order to do your project. If the project is in representation theory, for example, you will only learn what you need—not the whole theory. Our hope is that eventually you will take a course in representation theory and expand your grasp of it and see the bigger picture behind your project. We have a reading track for people like you who reside in Boston area.

Question: I love math, but I am not sure that I want to be a mathematician. Should I apply?
Answer: Many people start loving math early in life and then discover that there are many other things that require a similar kind of brain: computer science, cryptography, finance, and so on. We do not require from our students a commitment to become mathematicians. If you want to try research in math, you should apply. If students decide that they do not want to do research in math after finishing our program, we do not consider that a negative result. One way or another, the experience of PRIMES will help you understand better what you want to do with your life.

Question: I want to get to the International Math Olympiad. I am afraid that the time the research project takes prevents me from preparing for competitions. Should I apply?
Answer: People who are good at Olympiads often have fantastic brain power that helps in research. On the other hand, research requires a different mind set and the transition might be painful. It is possible, but not trivial to succeed in both. It is up to you to decide how you want to spend your time.

Question: I like number theory, but I do not see past PRIMES projects in number theory.
Answer: Doable number theory projects are hard to come by and we have fewer number theory projects than students who want to do number theory. There are many high-school programs that teach number theory including PROMYS and Ross programs. Our applicants like number theory because they were exposed to it. During PRIMES you will be exposed to something else and might like it as much.

Question: I found a local professor to work with on a research project. Should I apply to PRIMES?
Answer: PRIMES requires that you devote 10 hours a week to research for a year. It is unrealistic to do two research projects in parallel. Choose one. Working with someone in person may be better than by Skype at PRIMES. Also, usually our mentors are not professors, but rather graduate students. On the other hand, they are MIT grad students and projects are often suggested by professors. Our program is well structured. We guarantee weekly meetings in the Spring, we give extra help with your paper, and we have a conference. It is up to you to decide.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Alexander Shapovalov Crosses a River

Alexander Shapovalov is a prolific puzzle writer. He has a special webpage of his river-crossing puzzles (in Russian). Here is one of these puzzles.

Three swindlers have two suitcases each. They approach a river they wish to cross. There is one boat that can carry three objects, where a person or a suitcase counts as one object. No swindler can trust his suitcase to his swindler friends when he is away, but each swindler doesn’t mind his suitcases left alone at the river shore. Can they cross the river?

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

3-Pile Nim as an Automaton

In my paper with Joshua Xiong, Nim Fractals, we produced a bijection between P-positions in the three-pile Nim and a three-branch Ulam-Warburton automaton. We also defined a parent-child relationship on games that is induced by this bijection. Namely, two consecutive P-positions in a longest optimal game of Nim are the ones that correspond to a parent-child pair in the automaton. A cell in the Ulam-Warburton automaton has exactly one parent. That means, if (a,b,c) is a Nim P-position, then exactly one of (a − 1,b − 1,c), (a − 1,b,c − 1), and (a,b − 1,c − 1) must be a P-position and a parent of (a,b,c). (See our paper for more details.)

Now I want to explicitly write out the rules of an automaton which will generate the Nim P-positions in 3D.

Let me restrict the evolution of the automaton to the non-negative octant. That is, we consider points (a,b,c) in 3D, where each coordinate is a non-negative integer. We define the neighbors of the point (a,b,c) to be the points that differ from (a,b,c) in two coordinates exactly by 1. So each point strictly inside the octant has 12 neighbors. (There are three ways to choose two coordinates, and after that four ways to choose plus or minus 1 in each of them.

There is a geometric interpretation to this notion of neighborhood. Let us correspond a unit cube to a point with integer coordinates. The center of the cube is located at the given point and the sides are parallel to the axes. Then two points are neighbors if and only if the corresponding cubes share one edge. Now it becomes more visual that a cube has 12 neighbors, as it has 12 edges.

Here is the rule of the automaton. Points never die. We start with the patriarch, (0,0,0), one point being alive. The non-alive point is born inside the non-negative octant if it has exactly 1 alive neighbor that is closer to the patriarch. In other words the point (a,b,c) is born if and only if exactly one out of three points (a − 1,b − 1,c), (a − 1,b,c − 1), and (a,b − 1,c − 1) is alive. It follows that the points that are born at the n-th step has a coordinate sum 2n.

Consider for example the starting growth. At the first step the points (0,1,1), (1,0,1) and (1,1,0) are born. At the next step the points (0,2,2) and (2,0,2) and (2,2,0) are born. while the (1,1,2) will never be born as starting from the second step it has at least two live neighbors: (0,1,1) and (1,0,1) that are closer to the patriarch.

Theorem. In the resulting automaton, the points that are born at step n are exactly the P-positions of Nim with the total of 2n tokens.

Proof. Only the points with an even total can be born. Now we proceed by induction on the total number of tokens. The base case is obvious. Suppose we proved that at step n exactly P-positions with 2n tokens are born. Consider a P-position of Nim: (a,b,c) such that a + b + c = 2n + 2. Remember, that bitwise XOR of a, b, and c is zero. Consider the 2-adic values of a, b, and c (aka the smallest powers of 2 dividing a, b, and c). There should be exactly two out of these three integers that have the smallest 2-adic value. Suppose these are a and b. Then (a − 1,b − 1,c) is a P-position, while (a − 1,b,c − 1) and (a,b − 1,a − 1) are not. That means by the inductive hypothesis (a,b,c) has exactly one alive neighbor. So the position (a,b,c) is born at time n + 1.

Now we need to proof that nothing else is born. For the sake of contradiction suppose that (a,b,c) is the earliest N-position to be born. That means it has a live neighbor that is a P-position closer to the patriarch. WLOG we can assume that this neighbor is (a − 1,b − 1,c).

If a − 1 and b − 1 are both even, then (a,b,c) is a P-position, which is a contradiction. Suppose a − 1 and b − 1 are both odd. Then their binary representations can’t have the same number of ones at the end. Otherwise, (a,b,c) is a P-position. That is a and b have different 2-adic values. Suppose a has a smaller 2-adic value, Then, for (a − 1,b − 1,c) to be a P-position a and c has to have the same 2-adic value. That means (a,b − 1,c − 1) is a P-position too. Now suppose a − 1 and b − 1 are of different parities. Without loss of generality suppose a − 1 is odd and b − 1 is even, then c is odd. Then (a − 1,b,c − 1) is a P-position too. Thus we can always find a second neighbor with the same number of tokens. That is, both neighbors are alive at the same time; and the N-position (a,b,c) is never born. □

One might wonder what happens if we relax the automaton rule by removing the constraint on the distance to the patriarch. Suppose a new point is born if it has exactly one neighbor alive. This will be a different automaton. Let us look at the starting growth, up to a permutation of coordinates. At step one, positions (0,1,1) are born. At the next step positions (0,2,2) are born. At the next step positions (0,1,3), (1,2,3) and (0,3,3) are born. We see that (0,1,3) is not a P-positions. What will happen later? Will this N-position mess up the future positions that are born? Actually, this automaton will still contain all the P-positions of Nim.

Theorem. In the new automaton, the points that are born at step n and have total of 2n tokens are exactly the P-positions of Nim with the total of 2n tokens.

Proof. Only the points with an even total can be born. Now we proceed by induction on the total number of tokens. The base case is obvious. The birth of the points that have total of 2n tokens and are born at step n depend only on the points with the total of 2n − 2 tokens that are born at step n − 1. By the inductive hypothesis, those are the P-positions with 2n − 2 tokens. So the points have total of 2n tokens and are born at step n match exactly the first automaton described above. To reiterate, N-positions with 2n tokens are born after P-positions with 2n tokens, so they do not influence the birth of P-positions with 2n + 2 tokens. □

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Longest Optimal Game of Nim

In the game of Nim you have several piles with tokens. Players take turns taking several tokens from one pile. The person who takes the last token wins.

The strategy of this game is well-known. You win if after your move the bitwise XOR of all the tokens in all the piles is 0. Such positions that you want to finish your move with are called P-positions.

I play this game with my students where the initial position has four piles with 1, 3, 5, and 7 tokens each. I invite my students to start the game, and I always win as this is a P-position. Very soon my students start complaining that I go second and want to switch with me. What should I do? My idea is to make the game last long (to have many turns before ending) to increase the chances of my students making a mistake. So what is the longest game of Nim given that it starts in a P-position?

Clearly you can’t play slower then taking one token at a time. The beauty of Nim is that such an optimal game starting from a P-position is always possible. I made this claim in several papers of mine, but I can’t find where this is proven. One of my papers (with Joshua Xiong) contains an indirect proof by building a bijection to the Ulam-Warburton automaton. But this claim is simple enough, so I want to present a direct proof here. Actually, I will prove a stronger statement.

Theorem. In an optimal game of Nim that starts at a P-position the first player can take one token at each turn so that the second player is forced to take one token too.

Proof. Consider a P-position in a game of Nim. Then find a pile with the lowest 2-adic value. That is the pile such that the power of two in its factorization is the smallest. Suppose this power is k. Notice that there should be at least two piles with this 2-adic value.

The first player should take a token from one of those piles. Then the bitwise heap-sum after the move is 2k+1−1. Then the Nim strategy requires the second player to take tokens from a pile such that its value decreases after bitwise XORing with 2k+1−1. All piles with the 2-adic value more than k will increase after xoring with 2k+1−1. That means the second player has to take tokens from another pile with 2-adic value k. Moreover, the second player is forced to take exactly one token to match the heap-sum. □

In the position (1,3,5,7) all numbers are odd, so I can take one token from any pile for my first move, then the correct move is to take one token from any other pile. My students do not know that; and I usually win even as the first player. Plus, there are four different ways I can start as the first player. This way my students do not get to try several different options with the same move I make. After I win several times as the first player, I convince my students that I win anyway and persuade them to go back to me being the second player. After that I relax and never lose. I am evil.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Replace Question Marks

Replace question marks with letters in the following sequence:

Y, Y, ?, ?, Y, ?, Y, ?, R, R, R, R.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

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:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Your Deal is Better than my Deal

Do you know how to cut a cake? I mean, mathematically. There is a whole area of mathematics that studies cake cutting.

Mathematicians usually assume that each person has their own idea of what is the best part of the cake. Suppose three sisters are celebrating the New Year by having a cake. Anna likes only icing, Bella likes only chocolate chips, and Carol likes only pieces of walnuts mixed into the cake. Mathematicians want to cut cakes fairly. But what is fair? Fair is fair, right? Wrong. There are several different notions of fair cake division.

There is a proportionate division. In such a division every sister gets at least one-third of her value of the cake. This seems fair. Let’s see an example. Anna gets one third of the icing, Bella gets one third of the chocolate chips, and Carol gets everything else. This is a fair proportionate division. Each of the sisters believes that she got at least one-third of the cake, in their own value. But it doesn’t seem quite fair.

There is a stronger notion of fairness. It is called envy-free. In this division each sister gets at least one-third of the cake and, in addition, none of the three sisters would improve their value by swapping pieces. That means, if Anna wants only icing, not only does she get at least one-third of the icing, but also no one else gets more icing than Anna. The previous example of the proportionate division is not envy-free. Carol got two-thirds of the icing, so Anna would want to switch with her.

Let’s try a different division. Anna gets one third of the icing, Bella gets the chocolate chips and another third of the icing, and Carol gets all the walnuts and another third of the icing. Formally, this is envy-free cake cutting. But poor Anna. What do you think Anna feels when she sees the smiles of contentment on the faces of her sisters? Whoever invented the name doesn’t understand envy. Anna got one-third of the cake by her value, but the other sisters got the whole cake!

Luckily mathematicians understand this conundrum. So they invented another name for a cake division. They call a division equitable if everyone values all the pieces the same. So the division above is envy-free but not equitable. Let’s try again. Let’s give each sister one-third of all the components of the cake. This division is very good mathematically: it is proportionate, envy free, and equitable. By the way, envy-free division is always proportionate. This division seems fair. But is it a good division?

There is another term here: Pareto-efficient division means that it is impossible to make one person feel better, without making another person feel worse. All divisions above are not Pareto-efficient. Moving some icing from Carol to Anna, doesn’t decrease the value for Carol, but increases the value for Anna.

There is an even better way to divide the cake. We can give the icing to Anna, the walnuts to Bella, and the chocolate chips to Carol. This division is envy-free, equitable, and Pareto-efficient. It is perfect. Mathematicians even have a word for it. They call it a perfect division.

Mathematically this division is perfect. Unfortunately, sisters are not. I know an Anna who would still envy Bella.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail