Tanya Khovanova's Math Blog

In 2016, I posted a cute puzzle, An Asteroid Walk, on my blog. Here it is.

Puzzle. Seven astronauts landed on a small spherical asteroid. They wanted to explore it and walked in different directions starting from the same location. All used the same walking algorithm: walk x kilometers forward, turn 90 degrees left and walk another x kilometers, turn 90 degrees left again and walk the last x kilometers. The value of x was different for different astronauts and was one of 30, 40, 50, 60, 70, 80, and 90.

All but one astronaut finished in the same location. What was the value of x for the astronaut who finished alone? What is the size of the asteroid? To be precise, by size, I mean the great-circle circumference.

I never posted the answer. This post had sat on my to-do list for more than ten years, and I finally got around to it. The answer is surprising: the value used by the lonely astronaut is uniquely determined, but the size of the asteroid is not.

Let c be the circumference of the asteroid, and call the astronauts’ starting point the North Pole. Walking straight ahead means following a great circle. Write r for the remainder of x after removing complete laps, so that 0 ≤ r < c. A complete lap returns an astronaut to the same position with the same heading, so only r matters. Moreover, if we reverse the initial heading and replace r by c − r, the astronaut visits the same turning points and reaches the same endpoint.

Suppose each leg is a quarter of a circumference. The astronaut walks from the North Pole to the equator, turns left and follows the equator for a quarter-circle, then turns left again and returns to the North Pole. The route forms a spherical triangle with three right angles. By symmetry, three-quarters of a circumference per leg also brings the astronaut home. An integer number of complete laps per leg obviously works, too.

Half a circumference behaves differently. Each leg takes the astronaut to the antipode of the previous position, regardless of the turns. After three such legs, the astronaut is at the South Pole.

Now try a circumference of 40 kilometers. The astronauts with x = 40 and 80 make whole laps on each leg. Those with x = 30, 50, 70, and 90 have remainders of 10 or 30 kilometers: a quarter-circle or a three-quarter-circle. All six return to the North Pole. The astronaut with x = 60 has a remainder of 20 kilometers, or half a circumference, and finishes alone at the South Pole. This is the most common answer.

But nothing in the puzzle limits the number of laps an astronaut can make. What happens if the circumference is 40/3 kilometers? A quarter of this circumference is 10/3 kilometers. Measured in quarter-circles, the seven leg lengths are now 9, 12, 15, 18, 21, 24, and 27. Only 18 is congruent to 2 modulo 4. Once again, the 60-kilometer astronaut finishes at the South Pole, and everyone else returns to the North Pole.

More generally, every circumference of the following form works:

c = 40/(2m + 1) kilometers, where m = 0, 1, 2, ….

Indeed, a quarter of the circumference is then 10/(2m + 1) kilometers. If x = 10n, the leg contains n(2m + 1) quarter-circles. Because 2m + 1 is odd, this number is divisible by 4 when n is 4 or 8, is congruent to 2 modulo 4 when n = 6, and is odd for the remaining four values of n. Thus the 60-kilometer astronaut alone travels a half-circle after completing some number of full laps.

Are these all the solutions? And must the six astronauts finish where they started? Yes and yes. Unfortunately, the proof is much less charming than the answer: it is a calculation with trigonometric polynomials. This seems like an appropriate part to outsource to AI.

I used to write a review and list math-related puzzles for each MIT Mystery Hunt. Recently, my team, Death and Mayhem, started a new tradition of adding descriptions to the puzzle list. This makes it easy to find puzzles related to math. Nowadays AI can also help. So I plan to stop writing hunt reviews.

So consider this a farewell to my annual MIT Mystery Hunt reviews. I will just mention some puzzles that my team loved. I will provide the official descriptions where available and perhaps add a comment of my own.

• Urban Angst — Seven pictures. This puzzle might be especially enjoyed for people connected to MIT.
• Shapes — Metamatching puzzle. People found this puzzle satisfying.
• Minute Minute Cryptic — An innocuous-looking cryptic crossword. Great for cryptic lovers.
• Had — This puzzle doesn’t have a description, but it got the largest number of positive comments.
• Multidimensional Crossword — This puzzle has no listed description, but it was praised for its elegance.
• Setting Boundaries — Again, no description. This is a logic puzzle, and several people loved it.
• Dichotomies — This is a metapuzzle with five bite-sized logic/math five feeder puzzles.
• Can you really call it a crossword if… — This is another meta with six minifeeders.

I have finally become a queen — though only in a research paper. In Immensely Questionable Tests, I am Queen Tanya, and my ten PRIMES STEP student coauthors are my sages.

The project began with a probability puzzle from Mathematical Puzzles and Curiosities, my book with Ivo David and Yogev Shpilman. Here I present an equivalent version, without probabilities, to match our project.

Puzzle. How many correct answer choices are there?

a) 1    b) 1    c) 2    d) 2

The intended answer is 2: exactly two choices say 2. So far, so good. Now erase one of the 1s. How many correct answer choices are among a) 1, b) 2, and c) 2?

Now 1 appears once and 2 appears twice. Either value can be an answer. But calling all three choices correct would require the answer to be 3. What is going on here?

We restrict the answer choices to positive integers. We call a value m valid if it occurs exactly m times among the choices. Now we can discuss valid answers without getting into paradoxes.

Our first paper Self-Referential Tests counts tests with valid answers as a function of the cost, defined as the sum of all test options. The paper answers many questions related to different types of tests. For example, what is the cheapest test with k distinct valid values? The cheapest such test uses one 1, two 2s, and so on, through k copies of k. Its cost is 1² + 2² + … + k². For three distinct valid values, the cheapest test is 1, 2, 2, 3, 3, 3, costing 14.

Our second paper, Immensely Questionable Tests, mentioned at the very start of this essay, deals with the paradoxical nature of such tests.

For example, consider a test with these options:

1, 2, 2, 3, 3, 3, 3, 4, 4, 4.

The valid values are 1 and 2, accounting for three options. This tempts us to say that the correct answer is 3. But there are four threes on the test, suggesting that the correct answer should be 4 instead. And there are three fours, taking us back to 3. We are going in circles! It is surprisingly difficult to decide which answers should be called correct. We were not able to agree on the answer. So we turned our confusion into a story about a queen and her sages. Ironically, even in a fairy tale, I keep teaching people mathematics.

Here is an old puzzle that I have used in my classes for years.

Puzzle. Two people take turns placing quarters on a round table so that the quarters fit on the table and no two quarters overlap. The person who can’t move loses. Who has a winning strategy?

It is easy to see that the first player always wins by using the symmetry of the table. On the first move, the first player puts the first coin directly in the center of the table. For each subsequent move, the first player places a coin in the spot that is centrally symmetric to where the coin was placed on the previous move.

This year, something unusual happened. It seems I have a couple of true mathematicians among my STEP students. They added the following detail.

The first player wins, except when the table is smaller than the quarter.

Here is another puzzle from Konstantin Knop.

Puzzle. A town has 801 residents, and they vote on 9 different questions. On each question, everyone votes either “Yes” or “No”, and the majority wins. A resident is happy with the result of a question if the final decision matches their own vote. We will call a resident satisfied if they are happy with at least 5 of the 9 final decisions. What is the smallest possible number of satisfied residents?

I leave the solution to the reader, but I want to recast the puzzle in the language of coding theory.

Write each ballot as a string of 9 zeros and ones. For example, a 1 can mean “Yes” and a 0 can mean “No”. A ballot is then a point in the 9-dimensional Hamming cube. The final result is another string of 9 zeros and ones, obtained by taking the majority vote in each coordinate.

The Hamming distance between two strings is the number of positions in which they differ. A resident is satisfied exactly when their ballot has Hamming distance at most 4 from the final result. So the puzzle becomes:

Puzzle. Given 801 binary strings of length 9, how few can lie within Hamming distance 4 of their coordinate-by-coordinate majority?

I promised not to give away the solution, but I can’t resist one more observation: we can flip zeros and ones in any coordinate without changing the problem. Therefore, without loss of generality, we may assume that the final result is 111111111. Then we can restate the puzzle again.

Puzzle. Given 801 binary strings of length 9 such that every coordinate contains at least 401 ones, how few of the strings can have at least five ones?

I’ve been throwing away my old math books: the information is easily accessible online. Yesterday, I stumbled upon a book I hadn’t used in a long time. I opened it and started laughing.

The inscription says, “To Tanya, in memory of Sasha Beilinson’s PhD thesis defense. May you always be in a good mood. Volodya, June 30, 1988.”

Suddenly, this one book connected three famous mathematicians: Neil Koblitz, Alexander Beilinson, and Volodya. For my readers who don’t speak Russian: Volodya is the nickname for Vladimir. Can you guess who Volodya is?

Vouchers are supposed to make shopping cheaper, right? Apparently, the shopkeeper in the following puzzle didn’t know. By the way, the puzzle is from Mathematical Puzzles and Curiosities, my book with Ivo David and Yogev Shpilman.

Puzzle. A shop sells vouchers with price tags of 1, 2, 3, … dollars. There is exactly one voucher of each price. Buying the voucher tagged N makes your very next voucher cost N times its own price tag. Each multiplier applies only to the next purchase; the multipliers do not accumulate. Your first voucher costs exactly its price tag.

You have 26 dollars. What is the largest number of vouchers you can buy?

For example, buying the vouchers tagged 1, 2, 3, and 4, in that order, costs 1 + 1 · 2 + 2 · 3 + 3 · 4 = 21 dollars.

I will leave the 26-dollar puzzle to you. Meanwhile, suppose you have already chosen a finite set of vouchers and must buy all of them. In what order should you buy them to spend as little as possible? And what order makes you spend as much as possible?

My PRIMES STEP students and I chose this puzzle as the starting point in our research. We got many results and wrote a paper From a Voucher Puzzle to Extremal Sums of Adjacent Products, available on arXiv.

Here is the coolest part: the cheapest and the most expensive purchase orders depend only on the ranks of the price tags. They work for any finite set of distinct positive integers. You need to know which price is smallest, second-smallest, and so on. You do not need to know what the actual prices are.

Let us play with four vouchers. For price tags 1, 2, 3, and 4, the cheapest orders are 3, 2, 1, 4 and 2, 3, 1, 4 for the total cost of 15 dollars. The most expensive orders are 2, 4, 3, 1 and 3, 4, 2, 1 for the total cost of 25 dollars.

Now suppose the shop changes the price tags to 2, 7, 10, and 100. These numbers are much less evenly spaced. It looks as though we should start over with new calculations. We do not have to. We simply replace the smallest old number by the smallest new number, the second-smallest by the second-smallest, and so on. The first cheapest order becomes 10, 7, 2, 100 for the total cost of 10 + 70 + 14 + 200 = 294 dollars, and the first most expensive order becomes 7, 100, 10, 2 for the total cost of 7 + 700 + 1000 + 20 = 1,727 dollars.

We also studied two relatives of the voucher cost. The pairwise cost is what you pay if the first voucher is free but still applies its multiplier to the next purchase: just add the products of neighboring price tags. For the order 1, 2, 3, 4, this gives 1 · 2 + 2 · 3 + 3 · 4 = 20 dollars. For the loop cost, arrange the price tags in a circle and include the product of the last and first tags too, giving 20 + 4 · 1 = 24 dollars. Both variations have recipes for minimizing and maximizing the cost: and again the result depends only on the ranks of the price tags.

In all three costs, we have the same intuition. To maximize the cost, we want to cluster the most expensive vouchers together, creating large products of neighboring price tags. For the smallest cost, we want to put the largest price tags next to the smallest ones.

There is a particularly tidy order maximizing all three costs. Number the vouchers by rank, starting with 1 for the cheapest. Take the even ranks in increasing order, followed by the odd ranks in decreasing order. For eight vouchers, this gives 2, 4, 6, 8, 7, 5, 3, 1. These are ranks, not prices: all eight actual price tags could be odd. The minimizing orders also use only ranks, although they weave the large and small numbers together differently.

For more examples, and the exact results, check our paper From a Voucher Puzzle to Extremal Sums of Adjacent Products.

I have always liked the following idea for education. Ask students to watch a lecture on some topic at home, and then do the homework with the teacher in class.

The United States has an enormous number of teachers, but only a small fraction of them are truly fantastic lecturers. So why should every teacher give essentially the same lecture? Why not record the best lectures, put them online, and assign them as homework? Then class time could be used for what is much harder to do alone: solving problems, asking questions, discussing mistakes, and getting individual help from the teacher.

There are obvious advantages. A recorded lecture can be given by someone who explains the subject exceptionally well. Students can pause the video, replay a difficult part, slow it down, or go back to something they missed. A live lecture marches forward at one speed, whether or not everyone is ready.

There is also an advantage for teachers. Giving the same lecture every year or every other year might be boring. It might be more fun noticing where a student is stuck, asking the right question, or explaining one difficult point in several different ways. In this system, the classroom teacher becomes less of a performer and more of a mentor.

The biggest problem is obvious: what happens if some students do not watch the lecture? Currently, if a student doesn’t do their homework, they fall behind and have to catch up. But the next lecture can still proceed as planned. If some students skip the lecture, the teacher might get stuck repeating it instead of deepening students’ understanding, defeating the whole idea.

In college, however, the situation is somewhat different. Students who regularly attend lectures are usually motivated enough to watch a required video beforehand. And if they don’t, it is reasonable to hold them responsible for being unprepared.

What I especially like about this approach is that it uses the scarce resource where it matters most. A great lecture can be recorded once and watched by gazillions of students. But when a student is stuck on a problem and needs someone to understand exactly why they are stuck, a recording is not enough. That is when having a teacher in the room is most valuable.

The reason I decided to write about this idea now is the proliferation of AI. AI seems particularly well suited to helping students understand a lecture. A student can ask AI to explain a difficult point again, give another example, slow down, fill in a missing step, or answer a follow-up question. AI could even replace the lecture itself.

Homework is different. AI can explain the topic to a student, but the student still needs to understand it on their own. Part of the point of homework is the struggle. When AI helps with the solution, it makes the struggle easier or completely removes it, making the homework useless. When AI simply solves the homework problem, it damages the student’s understanding and progress. In addition, part of the value of the homework is receiving feedback from the teacher after grading. Grading AI’s solutions wastes everyone’s time.

Suddenly, this old idea of mine seems more important than ever: swap lectures and homework. AI can explain; the teacher can train the students to think.

Here is a famous riddle.

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?

The standard answer: the truck driver was walking.

My students are usually very inventive, but this time they came up with only two alternative answers worth mentioning:

• The truck was a fire truck rushing to a fire.
• It was Halloween, and the police officer was just a kid dressed as one.

I am sure there are more cute ways to explain the situation. Do you have one?

AI is changing mathematics very fast. I personally write papers faster and make far fewer typos. My friends, who are research mathematicians, are scared that they might soon become irrelevant. But what about math majors?

A math degree is extremely versatile. Math majors find jobs in finance, insurance, cryptography, computer science, and so on. Not to mention teaching. Once a lawyer told me that mathematics was the best preparation for arguing cases. Funnily, when I teach my STEP students proof writing, I tell them to imagine that I am a skeptical judge and they want to convince me they are right.

I personally worked as a specifications writer and an analyst. I did that at two different companies, but I was doing the same thing. I had to figure out what the client wanted, then translate it into a precise, high-level specification that programmers could implement. That experience seems especially relevant to working with AI. Before asking for a solution, we need to figure out what the problem is. After receiving a solution, we need to decide whether it actually solves that problem and how to present the solution to other people.

Mathematics is great because it structures the mind. I’ve seen many mathematicians who decided to become programmers and became strong programmers very fast. Being precise and knowing how to follow the logic was great help. I think the value of mathematics is this structured mind.

AI makes answers easier to obtain. But what is left? We still need to learn new things, pose questions, and understand answers. It is also good to be able to explain them. Another very important thing is the process of finding the answer. Here is where recreational mathematics comes in, as it was never primarily about producing new answers.

If these are the goals, then why would students take classes in advanced algebraic geometry that require 3 semesters of prerequisites? Well, I can think of many reasons to take advanced algebraic geometry. However, back to my point: Recreational mathematics allows for serious mathematical thinking without much background. Moreover, recreational mathematics is accessible to more students. In addition, while learning recreational mathematics, people can learn things they would really need in life. Optimal stopping problems, for example, help us understand how to buy a better house. They discuss when we should make an offer and when we should continue looking. Just as importantly, they make us formulate our goals and assumptions. Actually, the experience of recreational mathematics would be great for students beyond math majors.

Plus, recreational mathematics is so much fun! That is not a minor advantage. When outsourcing a solution is easy, we need problems that make us want to do the thinking ourselves.