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.

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?

I like pets, but, for various reasons, I can’t have one. So I flirt with other people’s pets. There is a black cat across the road who likes sitting in my driveway. So I had to buy a new car with a backup camera to make sure the cat is safe. As you can imagine, I couldn’t skip this problem about cats posted by Konstantin Knop on Facebook.

Puzzle. One cat eats one stick of sausage in 27 minutes. You have four identical sticks of sausage and five cats. Using only the cats and the sausages, measure exactly one minute.
All the cats eat at the same constant rate, and all the sausage sticks are identical. You may measure time intervals only between moments when cats finish sausage sticks. At each such moment, you may redistribute the cats among the remaining sausage sticks.

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?

Here is another puzzle posted on Facebook by Konstantin Knop.

Puzzle. One day, three inhabitants of the Island of Knights and Liars invited a foreign correspondent to visit so that they could tell him about their island. Knights always tell the truth, while liars always lie.

• The first inhabitant said, “The island has at most AT inhabitants. All the islanders are liars.”
• The second added, “The island has at most BAT inhabitants. Not all the islanders are liars.”
• The third disagreed, “The island has exactly CAT inhabitants. At least two islanders are knights.”

Unfortunately for the correspondent—and for us—he did not know the local number words very well. He knew only that AT, BAT, and CAT stood for three consecutive positive integers in increasing order.

How many knights and how many liars live on the island?

Konstantin Knop wrote to me about a weighing puzzle. Apparently, the balance scale keeps inserting itself into our conversation.

Puzzle. There are several coins, each weighing either 10 grams or 11 grams. Determine the parity of the number of coins of each weight using a balance scale.

Given the total number of coins, it is enough to find one of the parities. The other parity follows.

The first interesting case has four coins. How can we determine the parity of the number of 10-gram coins in two weighings?

The solution is on the surface: compare the coins in pairs. A balanced pair contributes either zero or two 10-gram coins, so it does not change the parity. An unbalanced pair contributes exactly one 10-gram coin, so it changes the parity. Thus, the parity is the parity of the number of unbalanced weighings.

Now try eight coins. The same pairwise method takes four weighings. But three weighings are enough.

Puzzle. There are 8 coins, each weighing either 10 grams or 11 grams. Determine the parity of the number of coins of each weight in three weighings on a balance scale.

Konstantin knows a way how to solve the problem for 16 in four weighings and for 32 coins in five weighings. Here is the challenge.

Puzzle. Is it true, that 2ⁿ coins can be solved in n weighings?

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.

Here is a new puzzle by Nikolai Chernyatiev.

Puzzle. Five sages, who all know one another, are blindfolded, seated in a row in a dimly lit hall, and then have their blindfolds removed. Each sage can see both of their immediate neighbors, but no farther; the sages at the ends know that they are at the ends. After that, each sage writes down one of the numbers 1, 2, or 3. The complete information — who wrote which number, in seating order — is then announced to everyone.
Before being seated, the sages may agree on a rule for choosing 1, 2, or 3 based on what they see. After the five numbers are announced, each sage must reconstruct the full left-to-right order of all five sages.

I love puzzles related to information theory, and this is a lovely example. Let’s do a quick sanity check. There are 5! = 120 possible orders of the sages. The announced numbers form a ternary string of length 5, giving 3⁵ = 243 possible announcements. That is more than enough in principle; so far, so good.

AI can produce a possible table of answers, but the resulting strategy is not very inspiring. Fortunately, there is a much more elegant solution based on the following neat fact:

Among any three distinct residues modulo 5, exactly one is the average of the other two. Equivalently, any three vertices of a regular pentagon form an isosceles triangle: one of the three vertices lies on the axis of symmetry of the other two.

But wait: Konstantin Knop proved a much tighter result. Each sage can get away with writing down only one of two numbers. Wow!

Alexander Karabegov sends me new puzzles from time to time. This time, however, it is not a puzzle but a math joke.

Joke. If a woman gives birth to a child at the age of 30, then 60 years earlier, her child was twice as old as she was. Whatever that means.

I’ve been staring at my icosahedron, trying to solve the following puzzle by Konstantin Knop.

Puzzle. One face of an icosahedron is special. The numbers 2, 3, and 5 are written at its vertices in some order. All other vertices of the icosahedron are labeled with 1. In one query, we may ask an oracle for the product of the numbers assigned to any subset of icosahedron’s vertices. What is the minimum number of queries needed to determine the special face?

However, I misread the problem. I ended up solving a different puzzle instead—and had quite a bit of fun doing it.

Puzzle. One face of an icosahedron is special. The numbers 2, 3, and 5 are written at its vertices in some order. All other vertices of the icosahedron are labeled with 1. In one query, we may ask an oracle for the product of the numbers assigned to vertices of any one face of the icosahedron. What is the minimum number of queries needed to determine the special face?

I won’t post the solutions just yet, but let me begin with a simple observation: one question cannot possibly be enough. Indeed, with one question, the oracle’s answer must be a divisor of 30, and 30 has only 8 positive divisors. But an icosahedron has 20 faces, so a single question cannot distinguish among all possible choices for the special face.