Tanya Khovanova's Math Blog

In my paper with Joshua Xiong on Nim Fractals we explained how to build an evolution graph corresponding to an impartial combinatorial game. The vertices of the graph are P-positions. And two vertices are connected if the two corresponding positions are consecutive P-positions in a longest possible optimal game.

What types of graphs do we get? An evolution graph should have at least one sink: these are our terminal P-positions. Also there are no directed loops: the game is finite. In addition, the distance from a vertex to sinks is uniquely defined: the number of directed edges that is needed to move from this vertex to a sink. This number is equal to half of the number of moves in the longest game, starting from the corresponding P-position.

A natural question arises: Can we build a game from a graph? The graph needs to satisfy the properties above. But other than that, can we? We can consider the graph itself as a game. Players can start at a vertex or an edge. From an edge, they can only move to a vertex where this edge ends. From a vertex they can move to any out-edge. The corresponding evolution graph is the graph itself. Vertices correspond to P-positions and edges to N-positions.

There is an equivalent game with a more uniform description. We put a vertex in the middle of every edge in the evolution graph. The new graph becomes bipartite. Players can start at any vertex. A move is allowed from a vertex following an out-edge to the vertex, where this edge ends. Vertices that are in the same part as terminal positions are P-positions. Other vertices are N-positions.

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.

Professor Bock came to his office at the Math Department of Deys University and discovered that someone had broken in. Luckily he had a lunch scheduled with his friend Detective Radstein. Bock complained to the detective about the break-in and the detective agreed to investigate.

Nothing was stolen from the office. It looked like somebody had just slept on Professor Bock’s couch. The couch was bought recently and it was positioned so that it was impossible to see it through the tiny window of the office door, which had been locked. Interestingly, Professor Bock’s office was the only one with a couch. The detective concluded that the person who broke in knew about the couch and thus was from the Math Department. In addition, the couch was very narrow and couldn’t possibly sleep more than one person.

Investigating crimes at the Math Department of Deys University was very easy. This was due to a fact discovered by Detective Radstein on a previous case: every member of the department was one of three types:

• A dodger who always tells the truth and answers the question directly, with one exception. If such a person is guilty and asked to confirm that, then s/he remains truthful, but dodges the question.
• A liar who’s every statement is a lie. A liar might dodge or not dodge the question.
• A pathological truth-teller who always answers the question directly and truthfully.

Thus solving a crime at the department is very easy. Detective Radstein just needs to ask every person two questions, “How much is 2+2?” and “Are you guilty?” Only a guilty dodger would answer “4” and dodge. Only a guilty truth-teller would answer “4” and “yes”. Only a guilty liar would answer something other than “4” and “no”.

Detective Radstein decided to enjoy himself by making this investigation more challenging. He asked everyone only one question “Are you guilty of breaking-in?” These are the first three replies:

—Albert: I did it.
—Bill: Albert didn’t do it.
—Connie: Albert did it.

It was amusing how many people knew where Albert slept, but these answers were enough for Detective Radstein to figure out the culprit. After this issue was resolved he asked Professor Bock, “While I am here, what other problems do you have at the department?”

“Well,” said the professor, “In fact, I would be grateful if you could help us resolve two more issues. This semester our expenditure for tea increased three times. It is clear someone is stealing tea. It’s also clear that this could only be someone who started working at the department this semester. There are two people who fit this description: David and Eve. So Detective Radstein asked each of them, “Are you stealing the tea?” He got the following answers:

—David: Eve steals the tea.
—Eve: Only one person steals the tea.

Having solved the Math Department’s tea problem Detective Radstein then asked Professor Bock, “What else?” “Well,” said Professor Bock, “one more thing. We have a lot of blackboards around the department. Every day a famous three-letter Russian curse word appears on the blackboards. The handwriting is always the same, so it is one person. Luckily the word starts with XY, so most people assume that this is some math formula. Anyway, I want to look into the eyes of the person who does this. I left the department late yesterday; only Fedor, Grisha and Harry were here. The blackboards were clean. This morning when I opened up the Math Department, the vulgar swearword had been written on the blackboards. I don’t suspect someone of sneaking into the department at night to scribble on our blackboards. I am certain it is one of the three people I mentioned.”

Once again Detective Radstein asked the suspects whether they did it.

—Fedor: Grisha did it.
—Grisha: Fedor did it.
—Harry: I do not speak Russian.

And again Detective Radstein solved the case. He was surprised that everyone in the department knew what everyone else was doing. Only his friend Professor Bock seemed clueless.

If you were the detective, would you be able to help Professor Bock?

My mom used to tell me “You are born to teach.” My mom was a very shy person with no desire to be a teacher. Somehow she ended up teaching chemistry all her life. She also told me that teaching was our family business. All my ancestors were teachers or priests. Given that I lived in the Soviet Union, priesthood was not an option. (Given that I’m a woman, priesthood was not an option anywhere else.)

After my postdocs, I ended up quitting academia and working for industry. As a result, I didn’t teach much. Until 2008 my only teaching experience was a course in Discrete Mathematics that I taught at Bar-Ilan University as part of my postdoc. Somehow Bar-Ilan University wanted five people to teach this same course in parallel and wanted me to teach it in Russian to attract fresh Russian immigrants. By the end of my course, I had way more people coming to my class than at the beginning, many of whom had transferred from the other parallel courses.

I had another clue that I was doing a good job. During one of my classes, the door was left open. A guy was walking down the hall, but when he heard me, he stopped. He stood there listening intently until the end of my class.

At the end of 2007 I resigned my industry job to go back to mathematics. I needed some financial support to do so, so my friends tried to arrange a math coach position for me at AMSA (Advanced Math and Sciences Academy Charter School). I had my interview in April, 2008, for a position for the following academic year. My interviewers were skeptical: they had had a series of PhDs who had proven incapable of teaching. I told them that deep down in my heart I knew that I would be a great teacher. And I made them an offer: I will start working in April and work until the end of the school year in June. Hiring me for two months was not a great risk, but gave them a basis on which to decide whether to give me a contract for the following year. I’ve been working at AMSA ever since.

My class is optional and there are no grades, but most of my students stick with me for all five years. (I teach grades 8 to 12.) My students show that they like me in many ways. I’m especially thrilled when they tell me that I am the best teacher they ever had.

Informally they call my class Tanya Time.

One evening Detective Radstein visited Professor Bock. He was hanging out in the kitchen and overheard a conversation between Professor Bock and his wife. It appeared that Mrs. Bock had discovered that all the cutlets she had prepared for the next day were missing. She asked her husband:

—Did you eat the cutlets?
—I ate soup, the professor replied.
—Oh well, the children were probably very hungry.

Detective Radstein smiled to himself. Many mathematicians have trouble making false statements. Some of them adjust to social situations by learning how to lie while formally telling the truth. Radstein calls them dodgers. Fortunately, dodgers only dodge a question when they are threatened. It was obvious that Professor Bock was such a dodger. He implied that he didn’t eat the cutlets, because he had soup for lunch. The detective was ready to bet $10,000 that, in truth, the soup was just an appetizer to Professor Bock’s meal of cutlets.

Detective Radstein talked to his friend Professor Bock about this obsession mathematicians have to make true statements. Professor Bock agreed that many mathematicians are like that. In fact, all the faculty members in his department are either dodgers or pathological truth-tellers. Ironically, all other staff members at Professor Bock’s math department are liars.

A pathological truth-teller is another term that Detective Radstein uses to describe people who tell the truth no matter what. They never dodge. They answer a question exactly, often disregarding the context and purpose of the question. For example, when someone enters an elevator and asks a pathological truth-teller, “Is this elevator going up or down?” the answer s/he gets is “Yes.”

One day Professor Bock asked Detective Radstein for help, following a series of laptop thefts at his department. It was clear that the thefts were committed by someone working at the department and that the criminal acted alone.

Detective Radstein decided that the easiest starting point would be to ask everyone the same question: Did you steal the laptops? If a pathological truth-teller is the perpetrator, s/he would admit to the crime. A dodger would evade the question, but only if they are guilty. A liar is flexible: s/he might either answer the question with a lie or dodge with a lie. These are the first three answers the detective got from members of the department:

—Alice: No, I didn’t steal the laptops.
—Bob: Alice stole the laptops.
—Clara: Alice didn’t steal the laptops.

Who stole the laptops?

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?

My post with Kvantik’s 2012 problems for middle school was a success. So I scanned the 2013 issues and found 7 more problems that I liked. Here are two cute problems I’ve seen before:

Problem 1. In the equation 30 − 33 = 3 move one digit to make it correct.

Problem 2. A patient got two pills for his headache and two pills for his cough. He was supposed to use one of each type of pill today and do the same tomorrow. The pills all looked the same. By mistake, the patient mixed up the pills. How should he use them so that he follows the prescription exactly?

Now logic and information-theoretical problems:

Problem 3. One strange boy always tells the truth on Wednesdays and Fridays and always lies on Tuesday. On other days of the week he can lie or tell the truth. He was asked his name seven days in a row. The first six answers in order are Eugene, Boris, Vasiliy, Vasiliy, Pete, Boris. What was his answer on the seventh day?

Problem 4. Ten people are suspected of a crime. It is known that two of them are guilty and eight are innocent. Suspects are shown to a psychic in groups of three. If there is a guilty person in the group the psychic points him out. If there are two guilty people in the group, the psychic points to one of them. If all of them are innocent, the psychic points at one of the three.

1. How would you find at least one guilty person in four séances?
2. How would you find both criminals in six séances?

Problem 5. There are four balloons: red, blue, green and black. Some of the balloons might be magical. There is also a detector box that can say how many balloons out of the ones put inside are magical. How can you find all the magical balloons using the detector box not more than three times?

I conclude with two miscellaneous problems.

Problem 6. Three runners started their loops at the same time at the same place on the same track. After some time they ended at their starting point together. The fastest runner passed the slowest runner 23 times. Assuming each runner has a constant speed, how many times was one runner passed by another runner in total?

Problem 7. Given a point inside a circular disk, cut the disk into two parts so that you can put them back together into a new disk such that the given point is the center.

I recently posted a set of problems from a Russian magazine for middle school children. Now it’s time for solutions.

Problem 1. There are 6 glasses on the table in a row. The first three are empty, and the last three are filled with water. How can you make it so that the empty and full glasses alternate, if you are allowed to touch only one of the glasses? (You can’t push one glass with another.)
Solution. Pour the water from the fifth glass to the second glass.

Problem 2. If it is raining at midnight, with what probability will there be sunshine in 144 hours?
Solution. In 144 hours it be midnight. Assuming we are not close to the earth’s poles, there will be no sunshine.

Problem 3. How can you fill a cylindrical pan exactly half-full of water?
Solution. Fill it with water, then tilt so that the water slowly runs out until you are about to see the rim of the floor of the pan.

Problem 4. The Jackal always lies; the Lion always tells the truth. The Parrot repeats the previous answer—unless he is the first to answer, in which case he babbles randomly. The Giraffe replies truthfully, but to the previous question directed to him: his first answer he chooses randomly.
The Wise Hedgehog in the fog stumbled upon the Jackal, the Lion, the Parrot, and the Giraffe, although the fog prevented him from seeing them clearly. He decided to figure out the order in which they were standing. After he asked everyone in order, “Are you the Jackal?” he was only able to figure out where the Giraffe was. After that he asked everyone, “Are you the Giraffe?” in the same order, and figured out where the Jackal was. But he still didn’t have the full picture. He started the next round of questions, asking everyone, “Are you the Parrot?” After the first one answered “Yes”, the Hedgehog understood the order. What is the order?
Solution. On the question “Are you the Jackal?” the Jackal and the Lion have to answer no. The Giraffe has to say “yes.” The Parrot could not have said “yes,” because in this case the Hedgehog, knowing where Giraffe is, could have figured out where the Parrot is. That means, in the first round there was only one “yes.” We also can conclude that the Parrot is not after the Giraffe. On the question “Are you the Giraffe?” the Lion would have said “no,” and the Jackal would have said “yes.” The argument here is similar to the previous discussion: the Parrot couldn’t have said “yes.” We also know that the Parrot is not after the Jackal. So the Parrot is either the first or is after the Lion. After the Hedgehog’s last question, we know that the Lion can’t be the first. That means the Parrot is the first. Which means the previous animal said “yes,” implying that the Jackal is the last. So there are two possibilities: The Parrot, the Lion, the Giraffe, the Jackal, or the Parrot, the Giraffe, the Lion, the Jackal. But in the second arrangement, the Hedgehog would have differentiated the Lion from the Parrot before the last question, as the Parrot couldn’t have been after the Giraffe. The answer is: the Parrot, the Lion, the Giraffe, the Jackal.

Problem 5. There are 12 cards with the statements “There is exactly one false statement to the left of me,” “There are exactly two false statements to the left of me,” …, “There are 12 false statements to the left of me.” Pete put the cards in a row from left to right in some order. What is the largest number of statements that might be true?
Solution. Suppose there are more than six statements that are true. That means one of the cards with a number more than six is true, meaning that there are at least 7 false statements. This is a contradiction. Suppose there are 6 true cards. They have to be cards with numbers one through six. In addition, no pair of adjacent cards can both be true. Arranging the cards in the order 7, 1, 8, 2, 9, 3, 10, 4, 11, 5, 12, 6 works. Notice that we can permute the cards with numbers more than 6 and it will still work.

Problem 6. Olga Smirnov has exactly one brother, Mikhail, and one sister, Sveta. How many children are there in the Smirnov family?
Solution. I shouldn’t have posted this problem. In Russian it is clear that Olga is a girl and the answer is 3 children. In English this problem might be confusing.

Problem 7. Every next digit of number N is strictly greater than the previous one. What is the sum of the digits of 9N?
Solution. Remember that 9N = 10N − N. That means the i-th digit of 9N is the (i+1)-th digit of N minus the the i-th digit of 9N. The next to last digit of 9N is the last digit of N minus the next to last digit of N minus 1 (because of the carry). The last digit of 9N is 10 minus the last digit of N. Summing this up, the answer is 9.

Problem 8. Nine gnomes stood in the cells of a three-by-three square. The gnomes who were in neighboring cells greeted each other. Then they re-arranged themselves in the square, and greeted each other again. They did this one more time. Prove that there is at least one pair of gnomes who didn’t get a chance to greet each other.
Solution. Color the square in checkerboard colors. There are 8 different ways to assign colors to gnomes for the three rounds. That means there are two gnomes who stood on the same colors all three times. They couldn’t have greeted each other.

John Conway told me a story about the book Winning Ways for Your Mathematical Plays that he wrote jointly with Elwyn Berlekamp and Richard Guy. The book includes the birthdays of each of the book’s three authors. The book has short author bios, each of which mentions that author’s birthday. But in addition, each birthday is hidden inside the book.

Elwyn Berlekamp was born on September 6, 1940, and this date is pictured on a tombstone on page 318 of Volume 2. That chapter is about suiciding moves.

John Conway was born on December 26, 1937. The Doomsday algorithm to calculate the day of the week for a given date is discussed on page 903 of Volume 4. Boxing Day in 1937 is chosen as an example. Boxing Day is a British holiday that originated when wealthy people gave gift boxes to servants the day after Christmas. John Conway was born on Boxing Day. Hidden behind this calculation that it was a Sunday, is the fact that it was Conway’s day of birth.

Richard Guy was born on September 30, 1916. He often uses his initials RKG for Richard Kenneth Guy. Maybe because of that he got the nickname Archangel. If you look into the index pages of Volumes 3 and 4, you will find an entry for Archangel that refers to pages 9, 30, 1916. Not only are there no mentions of “Archangel ” on pages 9 and 30, the book only has 1004 pages.

The trio of Berlecamp, Conway, and Guy will be the topic of an upcoming MOVES (Mathematics Of Various Entertaining Subjects) conference at the Museum of Mathematics.

The last time I visited John Horton Conway, he showed me a book, Genius At Play: The Curious Mind of John Horton Conway by Siobhan Roberts. It had nothing to do with him wanting to brag about the book. Nothing, nothing at all.

He just wanted to show me a picture from the book. While he was browsing this book about himself, I took a photo of him (featured on the left). The picture he was looking for was on page 314. I am reproducing it here (Photo by Michael A. Stecker, courtesy of Stephen D. Miller).

When we finally found the picture, he asked me how many tennis balls were in it. I smelled a trick question right away and didn’t bite. I shrugged. It appears that one of the balls at the far corner at the base of the pyramid had rolled away. So there was one less ball than I would have calculated. So, how many balls are there?