Tanya Khovanova's Math Blog

My former IMO coach, Gregory Galperin, converted a famous joke into a logic puzzle, adding a variation.

Puzzle. Ten logicians walked into a cafe. Each knew whether they wanted tea or coffee, but no one knew each other’s preferences. When they sat at a table, the waiter asked loudly, “Will everyone be having coffee?” Then the waiter went around the table, writing down each person’s answer.
There were three possible answers: “I don’t know”, “Yes”, and “No”. All answers were truthful and spoken loudly so that all group members heard them.

1. Suppose the first nine people said, “I don’t know”, and the tenth person said, “Yes”. How many of them wanted coffee?
2. Suppose the sixth and the seventh answers were not the same. How many people said, “I don’t know”, how many said, “No”, and how many said, “Yes”. Find the smallest number of people who for sure would have ordered coffee and the smallest number who for sure would have wanted tea?

Here are some problems that I liked from the YuMSh (Youths Math School in St. Petersburg) Olympiad.

Problem for 6th grade. Twenty people from an island of knights and knaves have a party. Knights always tell the truth, and knaves always lie. Each party-goer got a card with a different number from 1 to 20. When they were asked about their numbers, each answered with a number from 1 to 20. The sum of all the answers is 156. What is the minimum possible number of liars that have to be at the party?

Problem for 7th grade. Alice and Bob bought a deck of playing cards (52 cards total) and took turns gluing the cards on the wall one at a time. Alice was first. The game is lost if, after a move, the wall has 4 cards of the same suit or 4 cards of consecutive values (for example, 8-9-10-jack). Can Alice or Bob guarantee themselves a win, regardless of their opponent’s moves?

Problem for 7th grade. Buddhist monks gather in an infinite cave where a finite number of prime numbers are written on the wall. The numbers might not be distinct. Every second, one of the monks performs one of the following operations.

1. Adds to one of the numbers one of its digits.
2. Shuffles the digits of one of the numbers.

Every time they do it, they erase the old number and write the new one. The rule is that the new number has to be greater than the old one. If a composite number gets written on the wall of this cave, then the world collapses into nothingness. Can the monks save the world for eternity?

Problem for 8th grade. The incenter of a triangle is equidistant from the midpoints of the sides of the triangle. Prove that the triangle is equilateral.

Problem for 9th grade. Bob was given 30 distinct natural numbers. He wrote down all the 435 pairwise sums. It appears that among those sums, 230 are divisible by 3. How many of the original 30 numbers are divisible by 3?

I recently posted a cute puzzle about poisoned wine. Today, I would like to discuss this puzzle’s variation with N total glasses, of which two are poisoned.

Puzzle. N glasses of wine are placed in a circle on a round table. S sages are invited to take the following challenge. In the presence of the first sage, N − 2 glasses are filled with good wine and the other two with poisoned wine, indistinguishable from the good wine. After drinking the poisoned wine, the person will die a terrible tormented death. Each sage has to drink one full glass. The first sage is not allowed to give any hints to the other sages, but they can see which glass he chooses before making their own selection. The sages can agree on their strategy beforehand. For which S can you find a strategy to keep them all alive?

What does this have to do with rulers, and what are those? I am grateful to Konstantin Knop for showing me a solution with rulers. But first, let’s define them.

A sparse ruler is a ruler in which some distance marks may be missing. For example, suppose we have a ruler of length 6, with only one mark at a distance 1 from the left. We can still measure distances 1, 5, and 6. Such a ruler is often described as {0,1,6} to emphasize its marks, endpoints, and size.

A complete sparse ruler is a sparse ruler that allows one to measure any integer distance up to its full length. For example, the ruler {0,1,6} is not complete. It can’t measure distances 2, 3, and 4. Thus, if we add the marks at 2, 3, and 4, such a ruler becomes complete.

A complete sparse ruler is called minimal if it uses as few marks as possible. In our previous example, the ruler {0,1,2,3,4,6} is not minimal. The distance between marks 1 and 4 is 3, so if we remove mark 3, we can still measure any distance. We can remove mark 2 too. The ruler {0,1,4,6} with marks 1 and 4 is minimal.

Oops. I forgot that we have a round table. This means we need to look at cyclic rulers: the idea is the same, but the numbers wrap around. For example, consider the cyclic ruler {0,1,4,6} of length 6, where 0 and 6 is the same point. This ruler has three marks at 0, 1, and 4.

Going back to the puzzle, suppose N = 6, aka there are six glasses around the table. The sages need to agree on a complete cyclic ruler, for example, the one described above. As this ruler contains any possible difference between the marks, the first sage can mentally place the ruler on the table so that the marks cover poisoned glasses. He signals the position of the ruler by drinking his glass. The sages can agree that the glass drunk by the first sage corresponds to position −1 on the ruler, and the other sages avoid the first, second, and fifth glass clockwise from the chosen glass.

In this case, three glasses are not covered by the ruler’s marks. This means three sages can be saved.

To summarize, the sages need a complete ruler, as such a ruler can always cover two glasses at any distance from each other with its marks. The number of sages that can be saved by such a ruler is N minus the number of marks. To save more sages, we want to find a minimal ruler.

There are actually more cool rulers. A ruler is called maximal if it is the longest complete ruler with a given number of marks. For example, the non-cyclic ruler {0,1,4,6} is maximal. A ruler is optimal if it is both maximal and minimal. Thus, the ruler {0,1,4,6} is also optimal.

There are other types of rulers called Golomb rulers. They require measured distances to be distinct rather than covering all possibilities. Formally, a Golomb ruler is a ruler with a set of marks at integer positions such that no two pairs of marks are the same distance apart. If, however, a Golomb ruler can measure all the distances, it is called a perfect Golomb ruler. As we can deduce, a perfect Golomb ruler is a complete sparse ruler. I leave it to the reader to show that a perfect Golomb ruler must be a minimal complete sparse ruler.

The rulers rule!

I wrote a lot about the inventiveness of my students. Here is more proof.

Puzzle. A police officer saw a truck driver going the wrong way down a one-way street but didn’t try to stop him. Why?

Many of my students came up with the expected answer:

The truck driver was walking.

They also found some legit ways for a truck driver to not be stopped.

• The police officer was too far away.
• There was construction nearby, so the police officer directed the driver to drive the wrong way.
• The truck was a fire truck responding to an emergency.
• The driver bribed the police officer.
• The driver was a kid playing with a toy truck.

Some more ideas, rather far-fetched.

• The police officer was off duty, so he called another police officer to stop the driver.
• The truck driver was going too fast to stop.
• The police officer was responding to a bank robbery, and stopping the truck driver was not high priority.
• The police officer was driving the wrong way too, and it would be hypocritical to stop the truck driver.
• The street was a dead end, and the only way out was to go the wrong way.

Some funny ones.

• The police officer had a history of hallucinating and thought the truck driver was a figment of his imagination.
• The police officer was a ghost.
• The police officer was the truck driver.
• The police officer was busy eating a donut.
• The truck driver was the police officer’s boss.
• The truck driver was the police officer’s grandma.

I often receive letters from parents of math geniuses — “My twelve-year-old is reading an algebraic geometry book: accept him to PRIMES,” or “My ten-year-old finished her calculus course: here is her picture to post on your blog,” or “My two-year-old knows the multiplication table, can you write a research paper with him?” The last letter was a sarcastic extrapolation.

I am happy to hear that there are a lot of math geniuses out there. They are potentially our future PRIMES and PRIMES STEP students. But, it is difficult to impress me. The fact that children know things early doesn’t tell me much. I’ve seen a student who didn’t know arithmetic and managed to pass calculus. I’ve also met a student claiming the full knowledge of fusion categories, which later appeared to be from half-watching a five-minute YouTube video.

There are a lot of products catering to parents who want to bring up geniuses. My grandson received a calculus book for his first birthday: Introductory Calculus For Infants. Ten years later, he still is not ready for calculus.

Back to gifted children. Once a mom brought us her kid, who I can’t forget. The child bragged that he solved 30 thousand math problems. What do you think my first thought was? Actually, I had two first thoughts: 1) Why on Earth would anyone count all the problems they solved? 2) And, what is the difficulty of the problems he solved 30 thousand of?

From time to time, I receive an email from a parent whose child is a true math genius. My answer to this parent is the same as to any other parent: “Let your child apply to our programs. We do a great job at working with math geniuses.”

Our programs’ admissions are done by entrance tests. Surprisingly, or not surprisingly, the heavily advertised kids often do poorly on these tests. It could be that the parents overestimate their children’s abilities. But sometimes, the situation is more interesting and sad: I have seen children who sabotage the entrance tests so as not to be accepted into our programs. We also had students give us hints on their application forms that they were forced to apply.

In the first version of this essay, I wrote funny stories of what these students did. Then, I erased the stories. I do not want the parents to know how their children are trying to free themselves.

Dear parents, do not push your children into our programs. If they do not want to be mathematicians, you are decreasing their chances of getting into a good college. Imagine an admission officer who reads an essay from a student who wants to be a doctor but wastes ten hours a week on a prestigious math research program. Such a student doesn’t qualify as a potential math genius, as their passion lies elsewhere. Nor does this student qualify as a future doctor, as they didn’t do anything to pursue their claimed passion. In the end, the student is written off as a person with weak character.

On the other hand, the students who do want to be in our programs, thrive. They often start breathing mathematics and are extremely successful. Encourage your children to apply to our programs if they have BOTH: the gift for mathematics and the heart for it.

This puzzle was in last week’s homework.

Puzzle. How can an egg fly three meters and not break?

The expected answer:

• The egg flew more than 3 meters and broke afterward.

Some students tried to protect the egg:

• The egg was bubble-wrapped.
• The egg was dropped on a cushion.
• The egg was thrown up, then caught.
• The egg was thrown into water.
• My favorite: The egg used a parachute.

Other students specified qualities of an egg making it more resistant:

• The egg was hard-boiled.
• The egg was made of plastic.
• The egg was a frog egg.
• An educated answer: It could be an ostrich egg, which is extremely strong. (I checked that online, and, indeed, a human can stand on an ostrich egg without breaking it.)
• My favorite: The egg was fried.

Here are some more elaborate explanations:

• The egg flew on a plane.
• The egg was thrown on another planet with low gravity.
• The egg was thrown in space and will orbit the Earth forever.
• My favorite: The egg was not birthed yet: it flew inside a chicken.

To conclude this essay, here is a punny answer:

• The egg was confident, not easy to break by throwing around.

I am so tired of spam emails. I keep thinking about how we can fight spam, and here is an idea.

Gmail should change its system: every email you send to me would cost 1 dollar, payable to me. We can add an exception for people on my contact list. Everyone else, pay up!

I do not often contact strangers. But if I do, it is always important. So paying 1 dollar seems more than fair. On the other hand, this system will immediately discourage mass emails to strangers. Spam would go down, and I would stop receiving emails inviting me to buy a pill to increase the size of a body part I do not have.

This idea of getting paid for reading an email is not new. It was implemented by Jim Sanborn, the creator of the famous Kryptos sculpture. Kryptos is located at the CIA headquarters and has four encrypted messages. People tried to decrypt them and would send Jim their wrong solutions. Jim got tired of all the emails and administered Kryptos fees. Anyone who wants Jim to check their solution, can do so by paying him 50 dollars. I wonder if Jim would still charge the fee if someone sent him the correct solution.

Thinking about it, I would like the payable email system to be customizable, so I can charge whatever I want. After all, I do value my time.

Gmail could get a small percentage. Either Gmail, together with me, gets rich, or spam goes away. Both outcomes would make my life easier.

Puzzle. A goat was on a 10-meter leash. Yet it managed to go 300 meters away from the post. How come?

The standard answer. The leash wasn’t attached to the post.

My students scrutinized the puzzle and found some other possible ambiguities. For example, there might be two posts: the goat was leashed to one and was far away from the other. In another example, the timing is not given. It is possible that the goat was on the leash at one time and unleashed and far away from the post at another time. Here is my favorite answer.

My favorite answer. The goat ate the leash.

Puzzle. Find the largest and the smallest 4-digit numbers n such that when you erase the first two digits of n, you get the sum of the digits of n.

I recently posted a gnome puzzle by Alexander Gribalko.

Puzzle. Nine gnomes repeat the following procedure three times. They arrange themselves on a 3 by 3 chessboard with one gnome per cell and greet all of their orthogonal neighbors with handshakes. Prove that not all pairs of gnomes greet each other.

As often happens with my blog puzzles, I used this puzzle as homework for my students. They calculated that the total number of handshakes needed for all nine gnomes to greet each other is 36. On the other hand, each arrangement of gnomes creates 12 handshakes. This means that the numbers are tight: no greeting can be wasted, and every pair of gnomes need to greet each other exactly once. The students then studied different cases to prove this was impossible.

In each arrangement, a gnome can have either 2, 3, or 4 handshakes. Hence, we can distribute handshakes over three placements as 2+2+4 or 2+3+3. It follows that if a gnome is ever in the center of the grid, he has to be in a corner for the other two arrangements. Therefore, the three gnomes who end up in the center for one of the arrangements never greet each other.

However, I always love solutions that involve coloring the board in a checkerboard manner. Here is my solution.

Solution. Let’s color the board in a checkerboard manner. We assign each gnome a binary string, of length 3, describing the colors of the cells where the gnome was in each placement. There are 8 different possible strings. It follows that at least two gnomes are assigned the same string. But they can’t greet each other if they are standing on the same colors in each arrangement!