Tanya Khovanova's Math Blog

In a Turing test a human judge on one end of an interface interacts with either a computer or another human through this interface. If the judge can’t differentiate a machine from a human, then the computer is said to pass the test. One big goal of folks working in Artificial Intelligence is to build a computer that, when subjected to this test, is indistinguishable from a human.

However, while some people are working hard trying to build programs that can pass as humans, other people are working hard inventing tests that can differentiate between humans and those programs. Such tests are sometimes called Reverse Turing tests. As computer science progresses, the programs that are pretending to be humans as well as reverse tests are becoming increasingly complex.

For example, banks frequently want to prevent malicious computer programs from trying to log into their customers’ accounts. As a nice touch the judges are computers in this case. There are different methods designed to confirm that a human is trying to log in. In one of them a picture of a word, called CAPTCHA is presented on a screen, and the program requires that this word be typed in.

I wanted a CAPTCHA with words “Turing Test” in it for this posting. I looked online trying to find a way to do it. I couldn’t. There is a ton of software that can produce random CAPTCHAs from a dictionary but nothing could do a particular word. Finally, rather than looking for software, I found a human, a kind gentlemen named Leonid Grinberg who with some GIMP help manually implemented a self-referencing ” symbolizing the race between computers and tests.

As text recognition software becomes better and better, these CAPTCHAs become more and more difficult to read by a human. The last time I tried to login, I was only able to type the right word on my fourth try. Very soon computers will be better than humans at parsing CAPTCHAs. Humans are loosing the race on visual methods like this one.

Here’s another example. Some malicious software can recognize and capture email addresses on webpages to use for spam. While we don’t want them to recognize email addresses, we do want people to be able to do so. Thus we need a way to present email addresses as a reverse Turing test.

The standard safety recommendation is to avoid writing out the full and exact email address. Here’s an example: billgates AT gmail DOT com. Actually, I think computers are so smart nowadays that they can learn this trick. Another idea is to show a picture of your email address instead of using characters. Here we return to the image idea, which most computers can nowadays recognize.

Another idea of how to hide an email address is to give simple clues, which point to characters in the email address. For example, if you have “4” in your address, you might say that the character is the sum of two and two. I already invented a version of my email address in which each letter of my username is an answer to a simple question. Unfortunately, I think that the question answering systems like Start, as well as its huge new competitor Wolfram Alpha, will learn to answer these questions very soon. I can construct more sophisticated questions, but that would require my readers to spend more time to figure it out including going back to school for a calculus class.

So, recently, I’ve come up with a new idea. I made the description of my email simpler, but the paragraph describing my email didn’t contain all the necessary information:

I have an email account with Yahoo. My account name consists of seven lower case letters: five letters of my first name concatenated with the first two letters of my last name.

People who want to contact me can easily find my name in the title of my webpage or in my url, but I hoped it would take the evil computers some time to figure out what to look for, where it’s located and how to turn it into an address.

The day after I changed my contact web page, I went to my math coaching work at AMSA. During my break, I wanted to unwind by solving a light up puzzle, but it appeared that the new security system at AMSA forbids Internet access to all gaming sites. Thus, being still wound up I decided to do some work and went to my personal page for some materials. I was blocked again. The software politely informed me that access to personal websites was not permitted either. Oops. If a computer can understand that it is a personal website, it probably can figure out the name of the corresponding person. Oops-Oops-Oops. I am loosing the race against computers again. My recent idea to protect my email address from spam lasted one day until my first reality check.

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 added my favorite webcomics from “Not So Humple Pi” to my collection of funny math pictures.

Suppose you got accepted to the college of your dreams, say MIT. If you are so poor that MIT gives you a full financial package or you are so rich that the cost is not an issue, then you might throw a party. Everyone else, however, needs to wait for the financial package letter from MIT. The dream depends on the willingness and the ability of the parents to pay.

Suppose your father looks at the bill in shock. Then he takes you for a walk and tells you to forget about MIT and go to the state college, as he can’t pay the requested amount.

If you know for sure that your father has the money, what is the first question that you should ask him? The first question should be: “Are you still married to my mother?” If you are not completely clueless, you ought to know the answer to this question already. The family status of your parents may be the deciding factor in whether or not you can get your father to pay.

If your parents are divorced, your college expenses might be covered by their divorce agreement. In this case, there would be a legal document designating how your parents need to pay. If your father refuses to pay, your mother can use the divorce agreement to threaten your father with a complaint. The threat might be enough. If it is not, the court will probably force the reluctant father to pay according to the divorce agreement. So if your parents are divorced, it might be a good idea for you to scrutinize their divorce agreement.

Even if your parents’ lawyers neglected to include college expenses in the divorce agreement, you might still be able to finance your college education. Your mother, for example, might sue your father for college expenses.

I wonder what happens if the divorce agreement covers your college expenses, but neither parent wants to pay. I’m curious whether or not it is possible for the child to sue the parents based on the agreement he/she is not a party to. If any reader knows the answer, I’d appreciate hearing from you.

If your parents are together, there is no divorce agreement to protect your interests. It seems that legally the situation favors the children of divorced parents. If your parents do not love each other and have stayed in their marriage for your sake, it might be to your financial advantage to persuade them to divorce well before you need to go to college. Do not disregard reminding their lawyers to include college expenses in the agreement.

Israel Gelfand was my scientific adviser from the time I was 15. This is the story of how Gelfand helped me, when at 20 I was an undergrad at Moscow State University. At that time, I was married to Sasha (Alexander) Goncharov, who was also Gelfand’s student.

Sasha was more driven by mathematics than I. I had a lot of different interests: I wanted to hang out with friends, go to movies and read books. Sasha only wanted to do mathematics. His only other obsession was with what our colleagues (including me) were doing mathematically. So he was constantly asking me about the math problems I was thinking about.

For example, I was sitting at my side of the desk working, and he asked me to tell him about my problem. A few minutes later, I was forced to interrupt my work to go grocery shopping, because the household chores fell to me. As soon as I returned with bread and milk, Sasha excitedly told me the solution to my problem. It made me feel stupid, as if I should have solved it while I was waiting in the line for bread and milk. That feeling blocked out all the other feelings I should have been noticing, such as frustration and annoyance with Sasha.

Without his interference, I would have happily solved the problem myself. I was about to start my serious research, but I worried that I’d end up as a supplier of new problems for his papers.

You might wonder why I didn’t stop sharing my math with Sasha. But at that time, I wasn’t very in touch with my feelings and I prided myself on being a logical person. The idea that a husband and wife would discuss their work together seemed logical. Besides, even though I wasn’t particularly interested, Sasha was always ready to tell me about his math problems. It seemed important for me to be fair and to reciprocate. So I was stuck in a situation I didn’t know how to resolve.

I never confided this issue to any math colleagues. I never mentioned it to Gelfand — mostly because I was too scared of him to initiate any conversation. Besides, Gelfand delegated most of his responsibilities to others, because he was quite famous and busy. For example, all official paperwork related to his adviser role was done by Alexandre Kirillov. With me avoiding Gelfand and Gelfand being busy, we almost never spoke one-on-one.

You can understand my surprise when one day Gelfand approached Sasha and me to have a chat. He told us that we were about to start our own research, and while he permitted me to ask Sasha about what he was doing, he would not allow Sasha to interfere with my research.

Gelfand was a great judge of character. Without anyone telling him, he perceived what was going on in our marriage and gave me an excuse to stop Sasha’s prying. It was an appreciated gift.

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.

In the book “Mythematics: Solving the Twelve Labors of Hercules” Michael Huber adds details to Hercules’ labors so that in order that he can do each task, you need to help Hercules solve two or three math problems. For example, to defeat the Nemean Lion Hercules needs to solve the problem “Zeus Makes a Deal”, which is a Greek-myth version of the Monty Hall problem.

The problems in Mythematics are quite advanced. They range in topic from algebra, geometry and probability to differential equations and integral calculus. Plus, as a reward for helping Hercules, Huber gives you variations on Sudoku puzzles.

Solving some nice math problems might not be the only reason for people to buy this book. Here are some other reasons:

• Greek myth lovers may find extra motivation to do mathematics.
• People will earn that extra gratification of imagining that they are doing good deeds while solving math puzzles.
• Puzzle lovers can learn or refresh their knowledge of Hercules’ labors.

I like Huber’s approach. Future possibilities for more books are endless. Let’s write new math problems based on Harry Potter, Batman, the Bible or, maybe, The Joy of Sex.

In the book “Mythematics: Solving the Twelve Labors of Hercules” Michael Huber adds details to Hercules’ labors so that in order that he can do each task, you need to help Hercules solve two or three math problems. For example, to defeat the Nemean Lion Hercules needs to solve the problem “Zeus Makes a Deal”, which is a Greek-myth version of the Monty Hall problem.

The problems in Mythematics are quite advanced. They range in topic from algebra, geometry and probability to differential equations and integral calculus. Plus, as a reward for helping Hercules, Huber gives you variations on Sudoku puzzles.

Solving some nice math problems might not be the only reason for people to buy this book. Here are some other reasons:

• Greek myth lovers may find extra motivation to do mathematics.
• People will earn that extra gratification of imagining that they are doing good deeds while solving math puzzles.
• Puzzle lovers can learn or refresh their knowledge of Hercules’ labors.

I like Huber’s approach. Future possibilities for more books are endless. Let’s write new math problems based on Harry Potter, Batman, the Bible or, maybe, The Joy of Sex.

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.

I would like to tell you a story from my childhood and how I started on my math path.

When I was in elementary and middle school, I was very good with mathematics. Actually, I was by far the best math student in my class and my math teacher didn’t know what to do with me. Our algebra book had 2,000 problems and was intended to cover three years of study. But I worked out those problems, one after another, whenever I had a free minute in my math class. As I result, I got way ahead of everyone else.

One day a new boy named Lenya Kostyukov joined our class. He had extraordinarily long eye-lashes that covered his eyes, and all the girls envied him. He was a nice smart kid, but other than his lashes, I didn’t notice him very much. After a year or two, he announced that he was leaving our school, because he had been accepted to a math school for gifted children.

“Why is he going to a math school? I am the math star here. Why aren’t I going to a math school?” I knew about math schools, and I knew that I was good at math; I just never made the connection. I never felt that I was supposed to apply. Despite enjoying my reputation, I just passively went with the flow. Lenya figuratively kicked me in the butt. If he can, why can’t I?

So I applied to the same school on the last permissible day and was accepted. It turned out that I accidentally went to the room where they were giving the test for a grade higher than mine. I passed it with flying colors. My parents, though, were scared of a long commute and didn’t really want me to go so far away. They found a different math school closer to home, and used my extraordinary results to convince that school to accept me, even though their application date had passed.

For many years I continued to be a very passive person. Applying to a math school was the single big step I took for myself, but it was a defining step. I am grateful to Lenya for that. Or more likely to his parents, who were actively looking around trying to find the best place for their gifted son, and as a byproduct found a place for me. Once I was on the path of mathematics, I had the guidance of teachers and supervisors, for better or for worse, which allowed me to continue to be passive.

I have described my defining moment to you, but I don’t want to leave you in the dark about Lenya’s fate. Here’s what happened to him.

As I mentioned, Leonid (Lenya’s formal name) and I ended up in different math schools, so I lost track of him. Four years later I went to study math at Moscow State University and stumbled upon a guy with very long eye-lashes. We recognized each other immediately and eventually became friends.

He was doing logic and was very good at it. He was recommended for graduate school. But by that time our MSU administration noticed his lashes too. The lashes were obviously very suspicious; they hinted at the existence of non-Russian blood in his veins. As it was the period of brutal anti-semitism at MSU, they didn’t allow him to go to graduate school.

Leonid Kostyukov dropped mathematics and became a famous writer.