Tanya Khovanova's Math Blog

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.

For the last homework of the year, I gave my students a killer puzzle—literally.

Puzzle. A mysterious man kidnaps people, takes them to his cabin, and offers each victim two identical-looking pills. He claims that one pill is poisonous and the other is harmless. The victim chooses one pill, swallows it with water, and dies, while the killer consumes the other pill and survives. How does the killer manage to get the safe pill every time?

The official answer was that neither pill was poisoned. The poison was in the water.

Some students suggested that the poison becomes active only when mixed with water. I did not give full credit for this solution: saliva contains water, so the proposed chemistry is off.

Naturally, my students suggested other solutions. Here are two good ones, which are similar to each other:

• Both pills are poisonous, but the killer has taken an antidote.
• Both pills are poisonous, but the killer has somehow built up a resistance to the poison.

And here is an ingenious and highly specific answer from a student:

The killer kidnaps only people with deadly peanut allergies. He knows who they are because he is the town’s allergy tester, and both pills contain peanut butter.

ChatGPT offered a solution exploiting the wording: perhaps the victims die after swallowing the pill—but many decades later, of perfectly natural causes.

I feel there should be some more interesting solutions. Any takers?

I gave the following problem as part of the entrance test for my STEP program.

Puzzle. What word would you use to describe a man who does not have all his fingers on one hand?

The test had 17 questions, and this one was the only trick question. My goal was to check whether the students were paying attention.

The standard answer is normal, or something equivalent: regular, average, two-handed, or just a man. Most people do not have all their fingers on one hand; they have some fingers on one hand and some on the other.

Some students gave correct answers with extra flair.

• A cautious answer: A regular person, as to my knowledge, has fingers on both hands.
• A logical answer: A person with multiple hands, if they don’t have all fingers on one hand, then they must have multiple hands. For example, a human would work in this case.
• A funny answer: The man who puts his eggs in two baskets.

I also got answers from people who fallen right into my trap: fingerless, handicapped, genetically-mutated, alien, asymmetrical, injured, one-handed, resourceful, five-fingered, disabilitized, and mono-hand.

Some students sympathized with the man and called him frugal, determined, and a super-hero.

One student misread the problem, but gave a technically correct answer.

• Human, because I don’t see any difference in the man whether he has fingers or not.

This is not the first time I have used this problem on a test. But this year, the variety of answers was awesome. Still, the funniest answer in the misreadings category was:

• A chef.

I gave the following puzzle to my students.

Puzzle. A cowboy rides into town on Friday, stays for three days, then leaves on Friday. How come?

Most of them submitted the standard answer: his horse is named Friday.

One student suggested that the town was named Onfriday. This solution works well when the puzzle is given orally, but my homework was typed, so it feels less elegant.

Here are two more solutions that also work:

• He drank so much that he believed he stayed for three days, while in reality, the other four days were lost in a blackout.
• The cowboy left after three days, then later returned and left again on Friday.

And here is my favorite solution:

• The town has a quirky tradition: they celebrate fried foods and call the day Friday (get it?). The cowboy came for this special event, which happened to be held on a Tuesday.

Puzzle. Two fathers gave money to their sons. The first father gave $200, and the second father gave $100. Yet the total amount received by the sons was only $200. How come?

Standard answer: There were three people: a son, his father, and his grandfather. The grandfather gave the father $200, and the father gave the son $100.

In many puzzles, my students come up with a surprising variety of alternative solutions—but not for this one. For many years of my teaching, this puzzle stayed untouched by new ideas. Perhaps the puzzle is simply too well known. But recently, I finally heard an alternative answer:

• The money was taxable.

In the homework for my STEP program, I gave the following challenge problem.

Puzzle. My sages each wear a hat of a different color. As in standard hat puzzles, they can see everyone else’s hat color. Unlike in many other hat puzzles, they know the color of their own hat as well. I announce which color each of them should end up wearing; this assignment is a permutation of the original colors. Each sage is allowed one swap of hats with another person per day. They have two days to rearrange the hats so that everyone ends up with the correct color. Can they do it?

Many students noticed that the permutation can be decomposed into disjoint cycles and suggested solving the problem cycle by cycle. A few of them even pushed this idea all the way to a complete solution. However, none of them connected the puzzle to a topic we had discussed in class: dihedral groups.

Here is an elegant way to finish the solution once the permutation is decomposed into cycles. A cyclic permutation on n elements can be viewed as a rotation of an n-gon. Any rotation of an n-gon can be written as a product of two reflections. Each reflection of an n-gon, viewed as a permutation, consists only of 1- and 2-cycles. Ta-da!

Every year, after the PRIMES program begins, I send a letter to our students about how to read a math paper. The students in my group are juniors just starting their research. They are often required to read advanced math papers—frequently the first research papers they have ever encountered. This year, I decided to post my letter online, in case it might be helpful to other aspiring mathematicians.

Dear PRIMES and PRIMES-USA students,

Reading math papers can be very difficult and overwhelming. I remember trying to understand every single word of my first research paper and getting stuck on the first paragraph for a long time. That was a mistake. I regret that no one ever taught me how to read math papers. As the joke goes, “There are only two kinds of math books: those you cannot read beyond the first page, and those you cannot read beyond the first sentence.”

Math papers are not stories. They are not meant to be read linearly from beginning to end. Depending on your goal, you read different parts in different ways. Here are some examples.

Goal: Decide whether to read the paper.
Read: The abstract and parts of the introduction.

Goal: See what was accomplished.
Read: The introduction, or locate and read the main theorems.

Goal: Learn a method that might be useful.
Read: Find the relevant method and focus only on that section.

Goal: Get a general idea of the topic.
Read: First understand the structure of the paper. Then try to grasp the main statements at a high level.

Goal: Master the topic.
Read: Read the paper several times, going deeper with each iteration. Try not to get stuck on a sentence; you might understand it on another try. Here is a potential list of objectives for each iteration: you can adjust them and change their order according to your needs.

• First read: understand the structure and the big picture.
• Second read: understand the definitions and main notions.
• Third read: understand the main statements and look at small examples.
• Fourth read: understand the ideas behind the proofs.
• Fifth read: go deeper and start reading the referenced papers.
• Sixth read: try to reproduce the proofs.

Goal: Check for acknowledgments.
Read: The acknowledgments and citations.

The main rule is to keep your goal in mind while reading a paper. If you do not have a specific goal, ask your mentor to suggest exercises or questions to guide your reading. Try not to feel discouraged if you don’t understand everything: the joke at the beginning of this essay implies that everyone has trouble understanding math papers.

Tanya