Tanya Khovanova's Math Blog

I love Harvard-MIT Math Tournaments. I like the mini-events, especially when I learn a new game. I also like the guts round, where I enjoy the adrenaline rush of watching the progress in real time. I also like the fact that I know many of the kids from different teams: my current students, my former students, the members of my club, my Sergei’s friends.

The problems for the competitions are designed by undergraduate students at MIT and Harvard. Kudos to them. Still, I was somewhat disappointed with the November 2009 problems. Most problems are variations of standard problems with different parameters. It is not easy to design a problem, but I was hoping for something fresh.

My favorite problem from the HMNT 2009 tournament was in the theme round:

There are five guys named Alan, Bob, Casey, Dan, and Eric. Each one either always tells the truth or always lies. You overhear the following discussion between them:

• Alan: “All of us are truth-tellers.”
• Bob: “No, only Alan and I are truth-tellers.”
• Casey: “You are both liars.”
• Dan: “If Casey is a truth-teller, then Eric is too.”
• Eric: “An odd number of us are liars.”

Who are the liars?

My second favorite problem was in the guts round:

Six men and their wives are sitting at a round table with 12 seats. These men and women are very jealous — no man will allow his wife to sit next to any man except for himself, and no woman will allow her husband to sit next to any woman except for herself. In how many distinct ways can these 12 people be seated such that these conditions are satisfied? (Rotations of a valid seating are considered distinct.)

This was the funniest problem:

You are trapped in ancient Japan, and a giant enemy crab is approaching! You must defeat it by cutting off its two claws and six legs and attacking its weak point for massive damage. You cannot cut off any of its claws until you cut off at least three of its legs, and you cannot attack its weak point until you have cut off all of its claws and legs. In how many ways can you defeat the giant enemy crab? (Note that the legs are distinguishable, as are the claws.)

It is difficult to arrange so many problems for four rounds without mistakes. The error in the following problem is not a typo and it bothers me that no one caught it:

Pick a random digit in the decimal expansion of 1/99999. What is the probability that it is 0?

Hey, there is no uniform distribution on an infinite set of integers: picking a random digit is not defined.

Last month I gave my students a problem from Raymond Smullyan’s book The Riddle of Scheherazade:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. How many of them can each say that it is the same color as another one of Hassan’s horses?

Half of my students failed to notice the trick and gave the wrong answer. Recently I gave them the continuation of the problem from the same book:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. Assuming now that Hassan’s horses can talk, how many of them can each say that it is the same color as another one of Hassan’s horses?

This time the majority of my students didn’t notice the trick. This motivated me to continue playing jokes with them. Unfortunately though, Raymond Smullyan had only two problems about Hassan’s horses, so I have to invent the next one myself. Here is what I plan to give my students next time:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. Assuming now that Hassan’s horses can talk and always tell the truth, how many of them will say that it is the same color as another one of Hassan’s horses?

Feel free to continue the series.

My recent blog puzzle where my readers had to choose the odd one out became extremely popular and was republished in many blogs around the world. Some commentators decided that my posting was a joke and an example where the odd one out didn’t exist. I have to disappoint them: as a protest against find-the-odd-one-out questions and to illustrate that sometimes there is no good choice for the odd one out I would have chosen a different picture:

Can you find the odd one out?

Inspired by Michael Huber, who in his new book Mythematics combines math problems with Greek myths, I invented my first logic puzzle. Unlike Huber, I never had any ambition to help Hercules, but I always wanted to assist Frodo.

The day was passing towards sunset when the Company finally caught a long-awaited gleam of water, from which sparkled flickers of sunlight. As they quietly drew nearer, they laid their eyes on the next obstacle — a river that they had to transverse. The Company was footsore and tired and the hobbits were starving. But they couldn’t rest yet. They needed to collect materials with which to construct their raft before it became too dark. By nightfall they managed to build a tiny raft, and eagerly started their supper.

They couldn’t wait until dawn to build more rafts, for they needed to cross the river now. So while they rested, Aragorn smoked his pipe and began to contrive a plan.

Aragorn was in charge and there were eight of them. The four hobbits — Frodo, Sam, Merry and Pippin — were not very useful in battle. However, the four strong fighters — Aragorn, Gimli, Legolas and Boromir, who were sworn to protect the ring-bearer Frodo — were the best in the land.

The small raft they had built would not hold a lot of weight. Aragorn and Boromir were the heaviest. Gimli was short, but together with his armor he weighed as much as either Aragorn or Boromir. Each one of these three heaviest warriors was close to the raft’s maximum capacity, so they had to each be alone on the raft while crossing the river. Among the strong fighters, only Legolas was able to cross the river with a hobbit. The raft could also accommodate two hobbits.

Weight was not Aragorn’s only consideration: the current was dangerously fast. All the strong men could row, but among the hobbits, only Sam was strong enough to row against such a swift current.

Aragorn also worried about the orcs, who were roaming on both sides of the river. He didn’t want to leave any hobbit(s) alone on a riverside, without the safeguard of a strong fighter. Because he was the ring-bearer, Frodo needed extra protection. Aragorn wanted Frodo to be accompanied by at least two strong men. But lately Boromir had become restless when he was around the ring and Aragorn couldn’t count on him to look after Frodo. That is, while on the riverside, Frodo’s protection had to come from two out of the three remaining strong men: Aragorn, Legolas and Gimli.

Can you help Aragorn design a plan to cross the river?

In my days of competing in math, I met guys who could solve any geometry problem by using coordinates: first they would assign variables to represent coordinates of different points, then they would write and solve a set of equations. It seemed so boring. Besides, this approach doesn’t provide us with any new insight into geometry.

I find geometric solutions to geometry problems much more interesting than algebraic solutions. The geometric solutions that use geometric transformations are often the shortest and the most beautiful.

I.M. Yaglom wrote a great trilogy called The Geometric Transformations. The first book of this trilogy discusses translations, rotations and reflections. The second one — looks at similarity transformations, and the third one talks about affine and projective transformations. A lot of beautiful problems with their solutions are scattered throughout these books. They include all my favorite problems related to transformations.

I think geometry is the weakest link for the USA math team. So we have to borrow the best geometry books from other countries. This trilogy was translated from Russian and Russians are known for their strong tradition of excellence in teaching geometry.

Below you can find sample problems from Geometric Transformations 1, Geometric Transformations 2 and Geometric Transformations 3 — not necessarily in this order.

I.M. Yaglom wrote a great trilogy called The Geometric Transformations. The first book of this trilogy discusses translations, rotations and reflections. The second one — looks at similarity transformations, and the third one talks about affine and projective transformations. A lot of beautiful problems with their solutions are scattered throughout these books. They include all my favorite problems related to transformations.

I think geometry is the weakest link for the USA math team. So we have to borrow the best geometry books from other countries. This trilogy was translated from Russian and Russians are known for their strong tradition of excellence in teaching geometry.

Below you can find sample problems from Geometric Transformations 1, Geometric Transformations 2 and Geometric Transformations 3 — not necessarily in this order.

Problem 1. Let A be a point outside a circle S. Using only a straightedge, draw the tangents from A to S.

Problem 2. At what point should a bridge be built across a river separating two towns A and B (see figure) in order that the path connecting the towns be as short as possible? The banks of the river are assumed to be parallel straight lines, and the bridge is assumed to be perpendicular to the river.

Problem 3. Suppose you have two lines drawn on a piece of paper. The intersection point A of the two lines is unreachable: it is outside the paper. Using a ruler and a compass, draw a line through a given point M such that, were the paper bigger, point A would belong to the continuation of the line.

I am strongly opposed to questions of the type “which is the odd one out” during IQ tests. On the other hand, I do not mind them in different settings, especially when they are fun. Inspired by Martin Gardner, I spent a lot of time drawing this picture, and now I have to share it with the world. So, which is the odd one out?

I love the MIT Mystery Hunt. I like the adrenalin rush when solving problems under pressure. Plus, I like the togetherness of doing problems with other people. During the hunt I usually do not have time to look at all the puzzles: some of them are solved by my teammates while I’m sleeping and others are solved before I get to see them.

I’ve never tried to go back and check out the puzzles I missed nor the puzzles from the previous hunts, probably because without the goal of winning and without my team, I might find them boring. Often the solving process involves tedious Internet browsing to identify the images of different people or objects. I would only be motivated if the puzzle were related to something I am very interested in, such as Ballroom dancing. But I’m not thrilled at the thought of browsing through all the problems in order to find one that is relevant to the Tango.

In short, I need an index to the puzzles. For example, it would be nice to direct the lovers of square dancing to the Do Sa Do puzzle, or fans of Star Trek to the Alien Species puzzle. I hope that nobody blames me for hinting that those aliens are from Star Trek. I’m convinced that Trekkies who only want to solve Star Trek-related puzzles would immediately recognize them anyway. I do believe that I am not revealing too much by saying that the Facebook puzzle will appeal to the aficionados of the television show “24”.

It would be extremely useful to humanity to at least mark the MIT Mystery Hunt puzzles that are self-consistent, and do not require activities. For example, some of the puzzles involve interaction with headquarters, so you can’t solve them after the hunt. Some of the puzzles might expire, as for example the puzzle with pictures of different announcements in the infinite corridor.

Unfortunately, such an index doesn’t exist, and I do not have the time or expertise to create one myself. But I can fill this void at least partially by presenting a guide to math puzzles from the previous four hunts. I can’t promise that my guide is complete, as navigating the MIT Mystery Hunt website is very tiresome.

Before going into the math puzzles, I would like to list Sergei’s favorite type of puzzle: Duck Konundrums. The first Duck Konundrum puzzle appeared in 2000. It was created by Dan Katz, which is why his initials are in the title. One really needs to follow the instructions for this puzzle. This is very unusual as traditionally hunt puzzles do not have instructions at all. Do not be relieved: the instructions are really very complicated. The next Duck Konundrum puzzle appeared in 2002 and was considered to be even more amusing. People loved it, and this type of puzzle became a tradition in subsequent hunts. Here is my list of Duck Konundrums:

• 2000 — 5.6: The Duck Konundrum.
• 2002 — D2: The Mighty Duck Konundrum.
• 2004 — D3: The Fellowship Of The Duck.
• 2006 — The Cock Conundrum — A combination of the Duck Konundrum and a cute boys’ puzzle.
• 2007 — D4: Ducks Playing Poker.
• 2008 — Mystery Rallye — A Duck Konundrum style puzzle without ducks.
• 2009 — The Amazing Juggling Troupe Of Duckkon Undrum V.

Many Mystery Hunt puzzles appeal to mathematicians. I have to warn you though. Puzzles often are divided into two stages. In the first stage, you need to solve a puzzle, like solving sudoku, a crossword or finding all the wedding dates of the people in the pictures. The second stage requires you to produce a word or a phrase that is the answer to the puzzle. The second stage might be as simple as listing the people in chronological order of their wedding dates and then taking the first letters of their last names. This second stage could also be quite difficult. Depending on your tastes one stage of the puzzle might be much more rewarding than the other. If you love solving sudokus, you might find it more fun to just stop with that solution, instead of continuing on to the second stage.

2006

• Got Your Number — Some recognizable numbers at the second stage (my favorite for the year).
• 783658 — Sudoku at the second stage.
• Hey, Look, A Grid! — A bunch of numbers in a grid.
• Feel Your Way — A very frustrating minesweeper.
• Gross Solitaire — A tedious logic puzzle.
• All for One and One for All — The “26L. in the A.” type of puzzle with first-order logic notation.
• Fun with Formulae — Decipher recognizable formulae.
• Numeracy — A list of very big numbers.

2007

• Clash of the Titans — A mixture of skyscraper type puzzles with logic.
• A Midterm Progress Report to the Enron Board of Directors, July 2000 — Many logic puzzles involving numbers.
• Captain Red Herring’s Buried Pirate Booty — A variation of battleship puzzles.
• The Joy of Accountancy — A kakuro variation.
• Splits and Mergers — A combination of mazes.
• Nur einzelne Zahlen erlaubt! — A sudoku-related puzzle.
• Transmogrifiers — Figure out unknown functions.
• Puzzle Editing — A real treat! You need to solve several Japanese puzzles: Fillomino, Nurikabe, Masyu, Light Up, Heyawake, Hitori and Edel.
• Man, I Hate These %#!&@ Sudokus! — You need the extra pdf file to solve these interrelated sudoku puzzles.
• I Only Get a Measly $200? — A logic puzzle related to the Monopoly games requires an extra pdf file.

2008

• Knots and Crosswords — As it says: crosswords with some knots.
• Cursed — A kakuro variation.
• The Cult of Helios — First you have to figure out what this puzzle is about.
• Bad Beat Jackpot — Some poker math.
• Twisty Little Passages — Map the maze.
• Chimera — An interesting mixture.
• Trouble in Triplicate — Related to the game of Set.
• War Game — A logic puzzle.
• All Geared Up — You need to be good with arithmetic to count all rotations.
• Functions — This is my favorite of the year, especially good for sequence fans.

2009

• Cloaked Battleships — A variation on battleship puzzles.
• Growth Involves Reconstructing Legos — A variation on skyscraper puzzles.
• Mos Eisley Spaceport — A graph-fitting puzzle.
• Malthusian Catastrophes — Requires a lot of calculations.
• Plan 4 From Outer Space — You need to solve a lot of equations.
• The Sexaholics of Truthteller Planet — A logic puzzle, my favorite for the year.
• Cross Something-Or-Others — Eight beautiful variations of kakuro. To get to the answer you need to use three more pages: first, second and third. This one was my second favorite of the year.
• Our Crew Is Replaceable. Your Package Isn’t. — Six river crossing puzzles.
• His Alien Barbarian Girl and Her Robot Dog — The puzzle is a colorful version of battleship puzzles. To get to the answer you need to combine this puzzle with its matching doctor puzzle.
• His Troubled Teen — A nice logic puzzle. To get to the answer you need to complement this with the matching doctor puzzle.
• His Investigative Journalist — Jigsaw sudokus, but you have to work to get to them. To get the answer you need to solve the matching doctor puzzle.

It would also be nice to have some ratings for puzzles. I am not sure how to persuade the webmasters of the MIT Mystery Hunt page to do the index and the rating. Feel free to send them an encouraging email.

Konstantin Knop sent me the following coins puzzle, which was created by Alexander Shapovalov and first appeared at the Regional round of the all-Russian math Olympiad in 2000.

Baron Münchhausen has 8 identical-looking coins weighing 1, 2, …, 8 grams. The Baron knows which coin is which and wants to demonstrate to his guests that he is right. He plans to conduct one weighing on a balance scale, so that the guests will be convinced about the weight of one of the coins. Can the Baron do this?

This being a sequence-lover blog, we want to create a sequence out of this puzzle. The sequence is the following: Let the Baron initially have n identical-looking coins that weigh exactly 1, 2, …, n grams. Then a(n) is the minimum number of weighings on a balance scale that the Baron needs in order to convince his guests about the weight of one of those coins.

The original puzzle can be restated as asking whether a(8) = 1. The sequence is defined starting from index 1 and the first several terms are easy to calculate: 0, 1, 1, 1, 2, 1, 1, 1. Can you continue this sequence?

Let’s look at where ones occur in this sequence:

Theorem. If the weight of a coin can be confirmed with one weighing, then one cup of that weighing must contain all the coins with weights from 1 to some i, and the other cup must contain all the coins with weights from some j to n. Furthermore, either the scale must balance, or the cup containing the 1-gram coin must be lighter.

Proof. What does it mean for the Baron to convince his guests about the weight of some coin with one weighing? From the perspective of the guests, a weighing is a number of coins in one cup, a number of coins in the other cup, and a number of coins not on the scale, together with the result the scale shows (one or the other cup heavier, or both the same weight). For the guests to be convinced of the weight of some particular coin, it must therefore be the case that all possible arrangements of coin weights consistent with that data agree on the weight of the coin in question. Our proof strategy, therefore, is to look for ways to alter a given arrangement of coin weights so as to change the weight given to the coin whose weight is being demonstrated, thus arriving at a contradiction.

First, obviously, the coin whose weight k the Baron is trying to confirm has to be alone in its group: either alone on some cup or the only coin not on the scale. After that we can divide the proof of the theorem into several cases.

Case 1. The coin k is on a cup and the scale is balanced. Then we want to show two things: k = n, and the coins on the other cup weigh 1, 2, …, i grams for some i. For the first part, observe that if k < n, then the coin with weight k+1 must not be on the scale (otherwise it would overbalance coin k). Therefore, we can substitute coin k+1 for coin k, and substitute a coin one gram heavier for the heaviest coin that was on the other cup, and produce thereby a different arrangement with the same observable characteristics but a different weight for the coin the Baron claims has weight k.

To prove the second part, suppose the contrary. Then it is possible to substitute a coin 1 gram lighter for one of the coins on the other cup. Now, if coin k-1 is not on the scale, we can also substitute k-1 for k, and again produce a different arrangement with the same observable characteristics but a different weight for the coin labeled k. On the other hand, if k-1 is on the scale but k-2 is not, then we can substitute k-2 for k-1 and then k-1 for k and the weighing is again unconvincing. Finally, if both k-1 and k-2 are on the scale, and yet they balance k, then k=3 and the theorem holds.

Consequently, k = n = 1 + 2 + … + i is a triangular number.

Case 2. The coin k is on the lighter cup of the scale. Then: first, k = 1, because otherwise we could swap k and the 1-gram coin, making the light cup lighter and the heavy cup heavier or unaffected; second, the 2-gram coin is on the heavy cup and is the only coin on the heavy cup, because otherwise we could swap k with the 2-gram coin and not change the weights by enough to affect the imbalance; and finally n = 2 because otherwise we could change the weighing 1 < 2 into 2 < 3.

Thus the theorem holds, and the only example of this case is k = 1, n = 2.

Case 3. The coin k is on the heavier cup of the scale. Then k = n and the lighter cup consists of some collection of the lightest available coins, by the same argument as Case 1 (but even easier, because there is no need to maintain the balance). Furthermore, k must weigh exactly 1 gram more than the lighter cup, because otherwise, k-1 is not on the lighter cup and can be substituted for k, making the weighing unconvincing.

Consequently, k = n = (1 + 2 + … + i) + 1 is one more than a triangluar number.

Case 4. The coin k is not on a cup and the scale is not balanced. Then, since k must be off the scale by itself, all the other coins must be on one cup or the other. Furthermore, all coins heavier than k must be on the heavier cup, because otherwise we could make the lighter cup even lighter by substituting k for one of those coins. Likewise, all coins lighter than k must be on the lighter cup, because otherwise we could make the heavier cup even heavier by substituting k for one of those coins. So the theorem holds; and furthermore, the cups must again differ in weight by exactly 1 gram, because otherwise we could swap k with either k-1 or k+1 without changing the weights enough to affect the result on the scale.

Consequently, the weight of the lighter cup is k(k-1)/2, the weight of the heavier cup is 1 + k(k-1)/2. Thus the total weight of all the coins is n(n+1)/2 = k²+1. In other words, case 4 is possible iff n is the index of a triangular number that is one greater than a square.

Case 5. The coin k is not on a cup and the scale is balanced. This case is hairier than all the others combined, so we will take it slowly (noting first that all the coins besides k must be on some cup).

Lemma 1. The two coins k-1 and k-2 must be on the same cup, if they exist (that is, if k > 2). Likewise k-2 and k-4; k+1 and k+2; and k+2 and k+4.

Proof. Suppose they’re not. Then we can rotate k, k-1, and k-2, that is, put k on the cup with k-1, put k-1 on the cup with k-2, and take k-2 off the scale. This makes both cups heavier by one gram, producing a weighing with the same outward characteristics as the one we started with, but a different coin off the scale. The same argument applies to the other three pairs of coins we are interested in, mutatis mutandis.

Lemma 2. The four coins k-1, k-2, k-3 and k-4 must be on the same cup if they exist (that is, if k ≥ 5).

Proof. By Lemma 1, the three coins k-1, k-2, and k-4 must be on the same cup. Suppose coin k-3 is on the other cup. Then we can swap k-1 with k-3 and k with k-4. Each cup becomes heavier by 2 grams without changing the number of coins present, the balance is maintained, and the Baron’s guests are not convinced.

Lemma 3. If coin k-4 exists, that is if k ≥ 5, all coins lighter than k must be on the same cup.

Proof. By Lemma 2, the four coins k-1, k-2, k-3 and k-4 must be on the same cup. Suppose some lighter coin is on the other cup. Call the heaviest such coin c. Then, by choice of c, the coin with weight c+1 is on the same cup as the cluster k-1, …, k-4, and is distinct from coin k-2 (because c is on a different cup from k-3). We can therefore swap c with c+1 and swap k with k-2. This increases the weight on both cups by 1 gram without changing how many coins are on each, but moves k onto the scale. The Baron’s guests are again unconvinced.

Lemma 4. The theorem is true for k ≥ 5.

Proof. By Lemma 3, all coins lighter than k must be on the same cup. Further, if a coin with weight k+4 exists, then by the symmetric version of Lemma 3, all coins heavier than k must also be on the same cup. They must be on the other cup from the coins lighter than k because otherwise the scale wouldn’t balance, and the theorem is true.

If no coin with weight k+4 exists, that is, if n ≤ k+3, how can the theorem be false? All the coins lighter than k must be on one cup, and their total weight is k(k-1)/2. Further, in order to falsify the theorem, at least one of the coins heavier than k must also be on that same cup. So the minimum weight of that cup is now k(k-1)/2 + k+1. But we only have at most two coins for the other cup, whose total weight is at most k+2 + k+3 = 2k + 5. For the scale to even have a chance of balancing, we must have

k(k-1)/2 + k+1 ≤ 2k + 5 ⇔ k(k-1)/2 ≤ k + 4 ⇔ k(k-1) ≤ 2k + 8 ⇔ k² – 3k – 8 ≤ 0.

Finding the largest root of that quadratic we see that k < 5.

So for k ≥ 5, the collection of all coins lighter than k is heavy enough that either one needs all the coins heavier than k to balance them, or there are enough coins heavier than k that the theorem is true by symmetric application of Lemma 3.

Completion of Case 5. It remains to check the case for k < 5. If n > k+3, then coin k+4 exists. If so, all the coins heavier than k must be on the same cup. Furthermore, since k is so small, they will together weigh more than half the available weight, so the scale will be unbalanceable. So k < 5 and n ≤ k+3 ≤ 7.

For lack of any better creativity, we will tackle the remaining portion of the problem by complete enumeration of the possible cases, except for the one observation that, to balance the scale with just the coin k off it, the total weight of the remaining coins, that is, n(n+1)/2 – k must be even. This observation cuts our remaining work in half. Now to it.

Case 5. Seven Coins. n = 7. Then 5 > k ≥ n – 3 = 4, so k = 4. Then the weight on each cup must be 12. One of the cups must contain the 7 coin, and no cup can contain the 4 coin, so the only two weighings the Baron could try are 7 + 5 = 1 + 2 + 3 + 6, and 7 + 3 + 2 = 1 + 5 + 6. But the first of those is unconvincing because k+1 = 5 is not on the same cup as k+2 = 6, and the second because it has the same shape as 7 + 3 + 1 = 2 + 4 + 5 (leaving out the 6-gram coin instead of the asserted 4-gram coin).

Case 5. Six Coins. n = 6. Then 5 > k ≥ n – 3 = 3, and n(n+1)/2 = 21 is odd, so k must also be odd. Therefore k=3, and the weight on each cup must be 9. The 6-gram coin has to be on a cup and the 3-gram coin is by presumption out, so the Baron’s only chance is the weighing 6 + 2 + 1 = 4 + 5, but that doesn’t convince his skeptical guests because it looks too much like the weighing 1 + 3 + 4 = 6 + 2.

Case 5. Five Coins. n = 5. Then 5 > k ≥ n – 3 = 2, and n(n+1)/2 = 15 is odd, so k must also be odd. Therefore k=3, and the weight on each cup must be 6. The only way to do that is the weighing 5 + 1 = 2 + 4, which does not convince the Baron’s guests because it looks too much like 1 + 4 = 2 + 3.

Case 5. Four Coins. n = 4. Then the only way to balance a scale using all but one coin is to put two coins on one cup and one on the other. The only two such weighings that balance are 1 + 2 = 3 and 1 + 3 = 4, but they leave different coins off the scale.

The remaining cases, n < 4, are even easier. That concludes the proof of Case 5.

Consequently, by the argument similar to the one in case 4 we can show that the number of coins in case 5 must be the index of a square triangular number.

This concludes the proof of the theorem.

Now we can describe all possible numbers of coins that allow the Baron to confirm a coin in one weighing, or, in other words, the indices of ones in the sequence a(n). The following list corresponds to the five cases above:

1. n is a triangular number. For example, for six coins the weighing is 1+2+3 = 6.
2. n = 2. The weighing is 1 < 2.
3. n is a triangular number plus one. For example, for seven coins the weighing is 1+2+3 < 7.
4. n is the index of a triangular number that is a square plus one. For example, the forth triangular number, which is equal to ten, is one greater than a square. Hence the weighing 1+2 < 4 can identify the coin that is not on the cup. The next number like this is 25. And the corresponding weighing is 1+2+…+17 < 19+20 +…+25.
5. n is the index of a square triangular number. For example, we know that the 8th triangular number is 36, which is a square: our original problem corresponds to this case.

If we have four coins, then the same weighing 1+2 < 4 identifies two coins: the coin that weighs three grams and is not in a cup and the coin weighing four grams that is in a cup. The other case like this is for two coins. Comparing them to each other we can identify each of them. It is clear that there are no other cases like this. Indeed, for the same weighing to identify two different coins, it must be the n-gram on the cup, and the n-1 coin off the scale. From here we can see that n can’t be big.

As usual we want to give something to think about to our readers. We have given you the list of sequences describing all the numbers for which the Baron can prove the weight of one coin in one weighing. Does there exist a number greater than four that belongs to two of these sequences? In other words, does there exist a total number of coins such that the Baron can have two different one-weighing proofs for two different coins?

To conclude this essay we would like to note that the puzzle we are discussing is related to the puzzle in one of Tanya’s previous posts:

You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?

The latter puzzle appeared at the last round of Moscow math Olympiad in 1991. The author of this problem was Sergey Tokarev.

Here is a strange puzzle that was inspired by the palindrome problem. Suppose you have a sequence of words in some alphabet with the initial term a and all the other terms b: a, b, b, b, b, etc. Suppose this sequence generates palindromes every time you concatenate the first several terms, not counting the first term itself. So, ab, abb, abbb, and so on — are all palindromes. We call words b “papaya” words, when a exists, such that a and b generate the sequence with this palindrome property. Can you describe papayas?

Theorem. The word b is a papaya word if and only if b is a substring of Reverse(b)Reverse(b).

Proof. After we have added b so many times that the initial part a is much smaller than half of the concatenated string, the middle part of the concatenated string would consist of several words copies of the word b. The middle of the reverse string consists of several concatenations of Reverse(b). So the word b must be a substring of Reverse(b)Reverse(b). On the other hand, suppose b is a substring of Reverse(b)Reverse(b). Then Reverse(b)Reverse(b) is of the form xby, and we can choose a = y.

Theorem. Papaya words are either palindromes or concatenations of two palindromes.

Proof. Suppose our word consists of two palindromes cd. Then the reverse of it is dc and its double is dcdc. The word cd is a substring of dcdc, thus according to the first theorem, cd is a papaya word. Let’s do the other direction. Suppose the word b is a substring of Reverse(b)Reverse(b). Then Reverse(b)Reverse(b) is of the form xby. Then b = yx, and Reverse(b) = xy, which equals Reverse(x)Reverse(y). From here, Reverse(x) = x and Reverse(y) = y. If x or y has zero length, then our word is a palindrome. QED.

Hey, do you already know why we call these words papayas?

Just for fun we would like to study the structure of papaya words. Any one-character or two-character word is a papaya word, so the patterns are: a, aa, ab. For three-character words there are four patterns: aaa, aab, aba, abb. For four-character words there are 10 patterns: aaaa, aaab, aaba, abaa, aabb, abab, abba, abbb, abac, abcb. In this manner we get the sequence of the number of n-character papaya patterns: 1, 2, 4, 10, 21, 50 etc, which is sequence A165137 in the OEIS. This sequence depends on the number of letters in your alphabet. But the first n terms of these sequences are the same for all alphabets that have at least n letters.

Let us assume that we are working with an infinite alphabet. The complementary sequence would be the number of patterns for non-papaya words. The total number of patterns is described by sequence A000110 — Bell numbers: the number of word structures of length n using an infinite alphabet. So the beginning of this complementary sequence A165610 is: 0, 0, 1, 5, 31, 153, etc. The list of corresponding patterns is abc, aabc, abbc, abcc, abca, abcd, etc.

Historically, we first invented the corresponding sequence for numbers, not for words. We call a number a papaya number if it is a palindrome or a concatenation of two palindromes. If we use numbers instead of words in the problem, we need to carefully look at what happens if we encounter initial zeroes. Let’s take the papaya number 2200100, and see if we can find a number a, such that adding 22010 repeatedly to this sequence starting with a will always generate a palindrome. The number a must be 00100. But this is not a number. We have two choices: to say that we are working with strings of digits, or to allow several numbers to start the sequence before we add b repetitively and before getting to palindromes. In the latter case our sequence can start 0, 0, 100, 22010, 22010, and so on.

As we mentioned before, the number of patterns of papaya numbers will start the same as the number of patterns of papaya words. Later the sequence of patterns of numbers A165136 will be smaller than the corresponding sequence for words. As the sequence of Bell numbers is much more famous than the sequence A164864 of patterns of numbers, we expect the papaya patterns sequence corresponding to the infinite alphabet to be more interesting and important than the sequence of papaya patterns for numbers.

Though papaya numbers might be less important than papaya words with an infinite alphabet, they have an advantage in that we can generate more sequences with them. For example we can calculate the number of positive papaya number with n digits, as in the sequence A165135: 9, 90, 252, 1872, 4464, 29250, etc. And we can also calculate the sequence A165611 of n-digit non-papaya numbers: 0, 0, 648, 7128, 85536 etc.

This geometric problem was given to me by Arkady Berenstein:

There are n points on the plane, but not all of them are on one line. Prove that a line exists that passes through exactly two points of this set.

Arkady gave me a beautiful solution to this problem. First, draw a line through each pair of points. Suppose you calculate all the distances from each point to all the lines that the point doesn’t belong to. Pick the smallest distance. The corresponding line will be the one with two points. To finish the solution you need to fill in the details. That process is usually left to the reader.

I suspect that there might also be a solution using linear algebra. Can you find one?

I would like to reformulate this problem without using geometry. Suppose there is a set of n elements. Let’s call a family of subsets line-like if any two distinct subsets of this family can have as an intersection not more than one element. Then the geometry problem above has a set-theoretical analogue:

You have a set of n elements and a line-like family of subsets of this set such that any two elements of the set belong to a subset from this family, and that the family doesn’t contain the whole set. Is it true that there always exists a subset in this family consisting of two elements?

Usually I give such problems as homework for the reader, but this time I decided to change my habit, so I’m including the picture which contains the solution of this problem by my son Alexey Radul.

Conclusion: geometry is important.