Tanya Khovanova's Math Blog

I love The Secretary Problem. I first heard about it a long time ago with a different narrative. Then it was a problem about the marriage of a princess:

The king announces that it is time for his only daughter to marry. Shortly thereafter 100 suitors line up in a random order behind the castle walls. Each suitor is invited to the throne room in the presence of the princess and the king. At this point, the princess has to either reject the suitor and send him away, or accept the suitor and marry him. If she doesn’t accept anyone from the first 99, she must marry the last one. The princess is very greedy and wants to marry the richest suitor. The moment she sees a suitor, she can estimate his wealth by his clothes and his gifts. What strategy should she use to maximize the probability of marrying the richest person?

The strategy contains two ideas. The first idea is trivial: if the princess looks at a suitor and he is not better than those she saw before, there is no reason to marry him. The second idea is to skip several suitors at the beginning, no matter how rich they might seem. This allows the princess to get a feel for what kinds of suitors are interested in her. Given that we know the strategy, the interesting part now is to find the stopping point: how many suitors exactly does she have to skip? The answer is ⌊N/e⌋. (You might think that this formula is approximate. Surprisingly, it works for almost all small values. I checked the small values and found a discrepancy only for 11 and 30 suitors.)

The problem is called The Secretary Problem, because in one of the set-ups the employer tries to hire a secretary.

In many situations in real life it is a good idea to sample your options. Whether I’m shopping for an apartment or looking for a job, I always remember this problem, which reminds me not to grab the first deal that comes my way.

Mathematically, I try to find variations of the problem that are closer to real life than the classical version. Here’s one of the ideas I had: you can always delay hiring a secretary until you have interviewed several candidates. You can’t wait too long, as that good secretary you interviewed two weeks ago might have already found a job. And of course the king has a small window of time in which he can run out of the castle and persuade a suitor to come back before he saddles up his horse and rides away.

To make the problem mathematical we should fix the window size as an integer w. When you are interviewing the k-th suitor, you are allowed to go w − 1 suitors back. In other words, the latest you can pick the current suitor is after interviewing w − 1 more people. I call this problem: The Secretary Problem with a Sliding Window.

It is easy to extrapolate the standard strategy to the sliding window problem. There is no reason to pick a suitor who is not the best the princess have seen so far. In addition, if she sees the best person, it is better to wait for the last moment to pick him in case someone better appears. So the strategy should be to skip several people at the beginning and then to pick the best suitor at the last moment he is available.

The difficult part after that is to actually calculate the probabilities and find the stopping point. So I suggested this project to RSI 2015. The project was assigned to Abijith Krishnan under the direction of Dr. Shan-Yuan Ho. Abijith is a brilliant and hard-working student. Not only did he (with the help from his mentor) write a formula for the stopping point and winning probabilities during the short length of RSI, he also resolved the case when the goal is to pick one candidate out of the best two.

If you are interested to see what other RSI students did this year, the abstracts are posted here.

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.