Archive for the ‘Puzzles’ Category.

YuMSh Olympiad

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?


Share:Facebooktwitterredditpinterestlinkedinmail

Rulers to the Rescue

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!

Share:Facebooktwitterredditpinterestlinkedinmail

The Unstoppable Truck Driver

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.
Share:Facebooktwitterredditpinterestlinkedinmail

Flying Eggs

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.
Share:Facebooktwitterredditpinterestlinkedinmail

A Goat

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.

Share:Facebooktwitterredditpinterestlinkedinmail

Find the Largest and the Smallest

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.

Share:Facebooktwitterredditpinterestlinkedinmail

Gnomes Solution

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!

Share:Facebooktwitterredditpinterestlinkedinmail

A Hat Trick

My readers know that I love hat puzzles. This is why I decided to turn a number trick by Konstantin Knop (in Russian) into a hat trick.

Hat Trick. The audience has a bottomless supply of hats in ten different colors. They arrange ten people in a line and put one of the hats on each person. Then the magician’s assistant comes in and removes a hat from one of the ten people. After that, the magician appears and, abracadabra, guesses the color of the removed hat. The magician and the assistant agreed on a strategy beforehand. What is it?

Keep in mind that this trick won’t work with fewer than ten colors. As a bonus, can you explain why?

Sep 18, 2022 Correction: I meant “with fewer than ten people.”

Share:Facebooktwitterredditpinterestlinkedinmail

The Lomonosov Tournament: Games Contest

A combinatorial games section? At a math competition? I have never heard of it before. But here it is, at the Lomonosov Tournament. The first problem is from the 2012 Tournament (the link is to a Russian version). The problem is by Alexander Shapovalov. I picked it for its elegance and simplicity.

A rectangular band. You have a paper rectangle of size m by n with grid lines, where both m and n are greater than 1. Two players play the following game. The first player cuts the rectangle along any grid line into two rectangles. The next player picks one of the rectangles and cuts it again along a grid line, and so on. The winner is the player who, after their move, can arrange all the rectangles into a band of width 1. Which player is guaranteed a win regardless of the moves of their partner? Consider two cases.

  1. One of the numbers, m or n, is even;
  2. Both m and n are odd.

The next problem, by I. Raskin, is from the 2015 Tournament (in Russian). The problem is about fruits, and I know a lot of great puzzles with bananas and oranges, so I immediately got attracted to this one.

The original version had three types of fruit starting with the letters a, b, and c in Russian. They were oranges, bananas, and plums. I reused bananas and replaced oranges with apples, but I got stuck on the letter c. The players in this game eat their fruits, so using cantaloupes seemed like overkill. Plus, I am on a diet, so I decided on cherries.

Fruits. There are a apples, b bananas, and c cherries on the table. Two players play a game where one move consists of eating two different fruits. The person who can’t move loses. Assuming the players use their best strategies, would the first or the second player win in the following cases?

  1. a = 1 (the answer might depend on the values of b and c);
  2. a = 6, b = 8, c = 10;
  3. a = 7, b = 9, c = 15;
  4. a = 19, b = 20, c = 21.

The last problem is from the 2012 Tournament (in Russian). It has great sentimental value for me, as it was created by John Conway. It also reminds me of the famous Frobenius (chicken McNugget) problem.

Coin mintage. Once upon a time, in a faraway kingdom, two treasurers were minting coins. They decided to make it into a game, taking turns minting coins. Each turn, the player chooses a particular integral denomination and mints an infinite supply of coins of this denomination. The rules of the game forbid choosing a new denomination that can be paid with the existing coins. The treasurer who is forced to mint a coin of denomination 1 loses.

  1. Prove that if the first treasurer starts with denomination 2 or 3, s/he loses.
  2. Is it profitable for the first treasurer to start with denomination 4?
  3. Is it profitable for the first treasurer to start with denomination 6?
  4. Suppose the first treasurer minted coins of denomination 5, and the second treasurer of denomination 6. What is the winning strategy for the first treasurer after that?
  5. Suppose the first treasurer minted coins of denomination 5, and the second treasurer of denomination k. Prove that the largest denomination available for minting is 4k − 5.
  6. Prove that the first treasurer can win by starting with denomination 5. (Hint: Suppose the second treasurer replied with denomination k, and the first treasurer minted 4k − 5 after that. If this strategy wins, the problem is solved. However, if after that, the second treasurer wins by minting denomination m, then minting denomination 4k − 5 was the wrong move. What was the right move?)

Share:Facebooktwitterredditpinterestlinkedinmail

Poisoned Wine

Here is another exciting puzzle posted on Facebook by Konstantin Knop.

Puzzle. Eight glasses of wine are placed in a circle on a round table. Three sages are invited to take the following challenge. In the presence of the first sage, five glasses are filled with good wine and the other three 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 three sages can agree on their strategy beforehand. What is the strategy to keep them all alive?
An extra question. Does a strategy exist if fewer than eight glasses are placed around the table?

Let’s start with two trivial variations. If there is only one sage, s/he knows which glass to drink. Now, suppose there is only one poisoned glass and any number of sages. If the total number of good glasses is not less than the number of sages, the solution is obvious. The first sage drinks the glass clockwise from the poisoned one, and the other sages continue clockwise.

The next slightly less trivial case involves two sages and two poisoned glasses. If the total number of glasses is at least five, the sages are safe. The reason: there are at least two good glasses in a row. So the sages can agree that the first one drinks a good glass followed clockwise by another good glass. If the total number of glasses is less than 5, there is no reliable strategy, as the reader can check.

The above idea works if the number of sages is S, the number of poisoned glasses is P, and the total number of glasses is T, where T is greater than SP. Then, the strategy is the same since there is a guaranteed continuous stretch of S good glasses.

On the other hand, one can argue that for S and P more than 1, and T = S + P, it is impossible to find a strategy.

Our original problem corresponds to the case S = P = 3, and T = 8. Presumably, the strategy doesn’t exist if S = P = 3, and T < 8. If the 8-glasses problem is difficult, here is a much easier version, corresponding to the case S = 2, P = 3, and T = 6.

An Easier Puzzle. Six glasses of wine are placed in a circle on a round table. Two sages are invited to take the following challenge. In the presence of the first sage, three glasses are filled with good wine and the other three 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 two sages can agree on their strategy beforehand. What is the strategy to keep them all alive?

Share:Facebooktwitterredditpinterestlinkedinmail