Tanya Khovanova's Math Blog

I had a distant relative Alla, who was brought up by a single mother, who died in a car crash when the girl was in her early teens. Alla was becoming a sweet and pleasant teenager; she was taken in by her aunt after the accident. Very soon the aunt started complaining that Alla was turning into a cheater and a thief. The aunt found a therapist for Alla, who explained that Alla was stealing for a reason. Because the world had unfairly stolen her mother, Alla felt entitled to compensation in the form of jewelry, money, and other luxuries.

I was reminded of Alla’s story when I was reading The (Honest) Truth About Dishonesty: How We Lie to Everyone—Especially Ourselves by Dan Ariely. Ariely discusses a wide range of reasons why honest people cheat. But to me he neglects to look at the most prominent reason. Often honest people cheat when they feel justified and entitled to do so.

One of Ariely’s experiments went like this. One group was asked to write a text avoiding letters x and z. The other group was asked to write a text avoiding letters a and n. The second task is way more difficult and requires more energy. After the tasks were completed the participants were given a test in which they had a chance to cheat. For this experiment, the participants were compensated financially according to the number of questions they solved. Not surprisingly, the second group cheated more. The book concludes that when people are tired, their guard goes down and they cheat more. I do not argue with this conclusion, but I think another reason also contributes to cheating. Have you ever tried to write a text without using the letters a and n? I did:

I should try it here. But this is so difficult. I give up.

My son, Alexey, was way better than me:

First, God brought forth the sky with the world. The world existed without form. Gloom covered the deep. The Spirit of God hovered over the fluids. Quoth God: let there be light. Thus light existed.

Fun as it is, this is cruel and unusual punishment. The request is more difficult than most people expect at an experiment. It could be that participants cheated not only because their capacity for honesty was depleted, but because they felt entitled to more money because the challenge was so difficult.

In another experiment, the participants received a high-fashion brand of sunglasses before the test. Some of them were told that the sunglasses were a cheap imitation of the luxury brand (when they really were not). This group cheated more than the group who thought that they got a real thing. The book concludes that wearing fake sunglasses makes people feel that they themselves are fake and so they care less about their honor. Unfortunately, the book doesn’t explain in detail what was actually promised. It looks like the participants were promised high-fashion sunglasses. In this case, the fake group would have felt deceived and might have felt more justified to cheat.

Dear Dan Ariely: May I suggest the following experiment. Invite people and promise them some money for a 15-minute task. Pay them the promised minimum and give them a test through which they can earn more. Construct it so that they can earn a lot more if they cheat. Then make the non-control group wait for half an hour. If I were in this group, I would have felt that I am owed for the total of 45 minutes—three times more than what I was promised. I do not know if I would cheat or just leave, but I wouldn’t be surprised that in this group people would cheat more than in the control group.

If like me, you fancy Raymond Smullyan and his books, then you’ve heard about knights and knaves. Knights always tell the truth and knaves always lie. In addition to knights and knaves, there are normal people who sometimes tell the truth and sometimes lie. Here is a puzzle.

Puzzle. How, in one sentence, can a normal person prove that they are normal?

We can draw a parallel between people and coins. We can say that knights correspond to real coins, and knaves to fake coins that are lighter than real ones. Inspired by normal people, my coauthor Konstantin Knop invented chameleon coins. Chameleon coins can change their weight and behave like real or fake coins. I just wrote a post about chameleon coins.

Normal people are too unpredictable: they can consistently pretend to be knights or knaves. So logicians invented a simpler type of person, one who switches from telling the truth in one sentence to a lie in the next and then back to the truth. Such people are called alternators. Here is another puzzle:

Puzzle. You meet a person who is one of the three types: a knight, a knave, or an alternator. In two questions, find out which type they are.

Continuing a parallel between people and coins we can define alternator coins: the coins that switch their weight each time they are on the scale from weighing as much as real ones to weighing as much as fake ones. For the purposes of this essay, we assume that the fake coins are lighter than real ones. Unlike the chameleon coin, which might never reveal itself by always pretending to be real, the alternators can always be found. How do you find a single alternator among many real coins? There is a simple strategy: repeat every weighing twice. This strategy allows us to find an alternator among 9 coins in four weighings. Can we do better?

I used the alternator coins as a research project for my PRIMES STEP program where we do math research with students in seventh and eighth grade. The students started the alternator project and immediately discovered the strategy above. The next step is to describe a better strategy. For example, what is the maximum number of coins containing one alternator such that the alternator can always be found in four weighings?

But first we count possible outcomes. Suppose there is a strategy that finds an alternator. In this strategy we can’t have two unbalanced weighings in a row. To prove that, let us suppose there was an unbalanced weighing. Then the alternator switches its weight to a real coin and whether or not the alternator is on the scale, the next weighing must balance. The beauty of it is that given a strategy each outcome has to point to a particular coin as an alternator. That means the number of outcomes bounds the total number of coins that can be processed.

Counting the number of possible outcomes that do not have two unbalances in row is a matter of solving a recurrence, which I leave to the readers to find. The result is Jacobshtal numbers: the most beautiful sequence you might never have heard of. For example, the total number of possible outcomes of four weighings is 11. Since each outcome of a strategy needs to point to a coin, the total number of coins that can be processed in four weighings is not more than 11. But 11 is better than 9 in our previous strategy. Can we process 11 coins in four weighings? Yes, we can. I will describe the first part of the strategy.

So we have 11 coins, one of which is an alternator. In the first weighing we compare 5 coins against 5 coins. If the weighing unbalances, the alternator is on a lighter pan. Our problem is reduced to finding the alternator among five coins when we know that it is in the real state. If the weighing balances, then we know that if the alternator is among the coins on the scale it must now be in the light state. For the second weighting, we pick two sets of three coins out of this ten coins and compare them against each other. Notice that 3 is a Jacobsthal number, and 5, the number of coins outside the scale, is also a Jacobsthal number. If the second weighing balances, the alternator must be among 5 coins outside the scale. All but one of these coins are in the light state, and I leave it to the readers to finish the strategy. If the weighing unbalances, we need to find the alternator among 3 coins that are in the real state now. This can be done in two weighings, and again the readers are to the rescue.

It appears that Jacobsthal numbers provide the exact lower bound of the number of coins that can be processed. This is what my middle-schoolers discovered and proved. We wrote a paper on the subject. The strategy in the paper is adaptive. That means it changes depending on the results of the previous weighings. Can we find an oblivious strategy? I will tell you in later posts.

Suppose we have 3ⁿ identical-looking coins. One of the coins is fake and lighter than the other coins which all are real. We also have a random scale. That is a scale that at each weighing behaves randomly. Find the fake coin in the smallest number of weighings. Oops! That won’t work! It is impossible to find the fake coin. The scale can consistently misbehave in such a way as to blame a specific real coin for being fake.

Let’s try something else. Suppose we have two scales: one normal and one random. Find the fake coin.

What am I thinking? The normal scale can point to one coin and the random scale can point to another coin and we are in a “she said, he said” situation which we can’t resolve.

Now, in my final try, I’ll make it right. We actually have three scales, one of which is random. So here we go, with thanks to my son Sergei for giving me this puzzle:

Puzzle. We have 3ⁿ identical-looking coins. One of the coins is fake and lighter than the other coins, which all are real. We also have three scales: two normal and one random. Find the fake coin in the smallest total number of weighings.

Let’s start with this strategy: repeat every weighing on all three scales and have a majority vote. At least two of the scales will agree, thus pointing to the true result. This way we can use a divide-into-three-equal-groups strategy for one scale to find the fake coin. It will require 3n weighings.

Can we do better? Of course, we can. We can repeat every weighing on two scales. If they agree we do not need the third scale. If they do not agree, one of the scales is random and lying, and we can repeat the weighing on the third scale to “out” the random scale. After we identify one normal scale, the process goes faster. In the worst case we will need 2n + 1 weighings.

Can we do even better? Yes, we can. I will leave it to the readers to find a beautiful solution that is asymptotically better than the previous one.

Update on Dec 24, 2016. The total number of coins should be 3²ⁿ, not 3ⁿ. We are looking at the worst case scenario, when the random scale is adversarial.

We all have played with problems in which we had real coins and fake (counterfeit) coins. For this post I assume that the fake coins are always lighter than the real coins. My coauthor Konstantin Knop invented a new type of a coin: a chameleon coin. This coin can mimic a fake or a real coin. It can also choose independently which coin to mimic for each weighing on a balance scale.

You cannot find the chameleon coin in a mix with real coins if it does not want to be found, because it can consistently behave as a real coin. Let’s add classic fake coins to the mix, the ones that are lighter. Still the task of identifying the chameleons using a balance scale cannot be achieved: the chameleons can pretend to be fake coins. We can’t identify the fake coins either, as the chameleons can mess things us up by consistently pretending to be fake.

What we can do is to find a small number of coins some of which are guaranteed to be fake. Consider the simplest setup, when we have one fake coin and one chameleon in our mix of N coins. That is we have N − 2 real coins. Our task now is to find TWO coins, one of which has to be fake. As usual we want to do it in the smallest number of weighings that guarantees that we’ll find the two coins. Let me give you a fun problem to solve:

Puzzle. The total number of coins is four. And as above we have one chameleon and one classic fake. In two weighings find two coins so that one of them is guaranteed to be fake.

If you want to learn more, we just wrote a paper titled Chameleon Coins.

* * *

—Honey, we are like two parallel lines.
—Why do you say that?
—The intersection of our life paths was a mistake.

* * *

—Q: Why did the obtuse angle go to the beach?
—A: Because it was over 90 degrees.

* * *

Ancient Roman in a clothing store: How come XL is larger than L?

* * *

—Which is the odd one out: one, three, six, seven?
—Well, three of them are odd ones.

* * *

When I am with you, I solve integrals in my head, so that blood can come back to my brain.

* * *

There are two kinds of people in this world: Those that can extrapolate from incomplete data.

* * *

Seven has the word even in it, which is odd.

I have always wanted to be an honest person and have followed my honor code. Soviet Russia had two honor codes. One code was for dealing with people and the other for dealing with businesses and the government. I remind you that in Soviet Russia, all businesses were owned by the government. The money paid for work didn’t have any relation to the work done. The government paid standard salaries and the businesses did whatever. Generally, that meant that they were doing nothing. Meanwhile, the government got its income from selling oil.

All people were being screwed by the government, so they had no motivation to play fair. Just as American workers do, Soviet Russians might use the work copier to make personal copies. The difference was that we didn’t feel guilty at ripping off the government. We wouldn’t just make a few necessary copies; we would make copies for our friends, our family, for strangers—as many copies as possible.

I moved to the United States in 1990. Several of my friends took time to explain to me the difference between Soviet Russia and the US. One of the friends, let’s call her Sarah, was working as staff at Harvard University. She told me the story of a recent visit by a famous Russian professor. After he left, the department received a bill. It appears that the professor, in a short visit, used several months-worth of the department’s budget allocation for copying and phone calls. I was impressed, in a good way, by the professor who I assume spent a good deal of his time making a lot of copies of papers unavailable in Russia, presumably not only for himself but also for students and colleagues. On the other hand, it was clearly wrong.

My new friend Sarah told me that in the US money does not come from nowhere, and I should include Harvard University in my honor code for people. Actually, not only Harvard, but also any place of work and the government too. Sarah also told me that since that budget problem, she was asked to talk to every incoming Russian visitor and explain to them how capitalism works. Most Russian visitors were ready to accept the rules. I too was delighted with that. It is much easier to follow one honor code than two.

I was also very happy for my son, Alexey. He was eight when we moved to Boston. Before our move I had a dilemma. Should I tell him that Lenin and Stalin were bad guys and killed millions of people? If I gave him a truthful explanation, I would also have to teach him to lie. Otherwise, if he mentioned this at school or on the street, we would be at risk of going to prison. If I didn’t teach him the truth, he might become brainwashed and grow up believing in communism, which would be very, very bad.

I was so lucky that I moved to the US: I didn’t have to teach my son to lie.

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.

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?

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.

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.