Tanya Khovanova's Math Blog

Do you know that numbers have destinies? Well, to have a destiny, a number needs to have a life, or in mathematical terms, destinies are defined with respect to an operation or a function.

I know the term “destiny” from John Conway, the creator of the Game of Life. It would be harmonious to assume that he suggested this term.

Case 1. SOD. Suppose our function is the sum of digits of a number, denoted as SOD. Then the trajectory of a number k is the sequence a(n), such that a(0) = k and a(n+1) = SOD(a(n)).

Two numbers have the same destiny with respect to SOD if the tails of their trajectories coincide. Suppose a(n) and b(n) are two trajectories. Then the numbers a(0) and b(0) on which these trajectories are build have the same destiny if there exist N and M, such that for any j, a(N+j) = b(M+j). In particular, all numbers in the same trajectory a(n) have the same destiny.

In the above example of SOD, any trajectory of a positive integer ends with a one-digit non-zero number repeating many times. It follows that all the natural numbers have 9 different destinies with respect to SOD, which only depend on the remainder of the number modulo 9.

Given an operation, we can build another sequence that is called “the first occurrence of a new destiny”. This is the sequence of numbers c(n) such that c(n) is the smallest number with its destiny. For the SOD operation, the sequence of the first occurrences of new destinies is finite and is equal to: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Case 2. The next prime. Let us consider a different example. Let the function f(n) be the next prime after n. Then wherever we start, the tail of the trajectory with respect to the function f(n) is a sequence of consecutive prime numbers. Therefore, with respect to this function all integers have the same destiny.

Case 3. Reverse. Suppose f(n) is a reverse of n. If a number is a palindrome, then its trajectory is a one-cycle consisting of that number. If a number is not a palindrome, then its trajectory is a two-cycle consisting of a number and its reverse. The first appearance of a new destiny is sequence A131058 — a list of numbers n whose reverse is not less than n. In this case, instead of studying destinies, it might be more interesting to study types of destinies. For this operation we have two types: one-cycles for palindromic integers and two-cycles for non-palindromic integers.

Case 4. The sum of proper divisors. For the next example, let f(n) denote the sum of proper divisors. Let’s look at the trajectory of 15: it is 15, 9, 4, 3, 1, 0. The sum of proper divisors of zero is not-defined or is equal to infinity, whichever you prefer. So, let us say the trajectory of 15 is finite, and ends with 1, 0. This situation makes the definition of destinies more complicated, but it is appropriate to say that finite sequences have the same destinies if they end with the same number. For our example of sums of proper divisors all finite sequences end with 0. Thus all the numbers whose trajectories are finite have the same destinies. The sequence of new destinies starts 1, 6, 28, 220, …; and we do not know what the next number is because for 276 we do not know the behavior of its trajectory. Even when we know what kind of life the number is living the destinies are not always clear.

Case 5. TITO. The next interesting example is the TITO operation. TITO is an abbreviation of “Turning Inside, Turning Outside”. By definition, to calculate TITO(n) you need to reverse the prime factors of n, multiply them back together (with multiplicities) and reverse the result. For example, to calculate TITO(68), we first find prime factors of 68, which are 2, 2 and 17. We reverse them and multiply: 2*2*71 = 284. Then we reverse the result: TITO(68) = 482.

It is easy to see that prime numbers are among the fixed points of the TITO operation. That means all prime numbers have different destinies of the same type: they end with a one-cycle. There are numbers other than prime that have one-cycle destinies. For example, a palindrome that is a product of palindromic primes is a fixed point of the TITO operation. There are other cases too: for example 26 is a fixed point, but is neither prime nor palindromic. There are numbers that have one-cycle destinies, but are not the fixed points of TITO operation themselves. For example, the trajectory of 49 starts with the following sequence: 49, 94, 841, 4648, 8212, 80041, 415003, 282145, 54796, 849667, 3652951, 35429422, 2941879, 27075955, 5275759, 5275759, 5275759. ….

There are numbers that generate two-cycles. For example, 12 and 156. For numbers n that have only palindromic factors, TITO(n) is equal to the reverse of n. If n is not a palindrome and the reverse of n has only palindromic factors, then the trajectory of n is a two-cycle. Not all two-cycles are like that. Take for example 291 which is a product of primes 3 and 97. Thus, TITO(291) is the reverse of 3*79, which is equal to 732. On the other hand, 732 = 2*2*3*61. Hence, TITO(732) = reverse(2*2*3*16) = 291.

There are longer cycles too. Take for example 15, which generates a cycle of length 7: 15, 51, 312, 447, 3282, 744, 213, 15, …. Also, for some numbers we do not know if there is a cycle. The smallest number for which I myself do not know whether the trajectory tends to infinity or collapses into a cycle is 78.

For the TITO operation we might be more interested in types of destinies. Personally, I am interested not only in the types of destinies, but also in sets of numbers that have the same destinies for the same reasons. For example, I am interested in dividing numbers of one-cycle TITO destinies into three groups: primes, palindromes with palindromic primes and other cases.

Case 6. RATS. I kept the RATS operation for dessert as, in my opinion, it is the most interesting operation with respect to destinies. RATS is the abbreviation of Reverse Add Then Sort. For example, to calculate RATS(732) we need to reverse 732 getting 237, then add 732 and 237 together getting 969, then sort the digits. Thus, RATS(732) = 699.

Let’s look at the RATS sequence starting with one: 1, 2, 4, 8, 16, 77, 145, 668, 1345, 6677, 13444, 55778, 133345, 666677, 1333444, 5567777, 12333445, 66666677, 133333444, 556667777, 1233334444, 5566667777, 12333334444, 55666667777, 123333334444, 556666667777, …. We can prove that this sequence is infinite, because numbers fall into a repetitive pattern with an increasing number of digits. This is the first such example in this discussion. John Conway calls the destiny of 1 “the creeper”. Conway conjectured that RATS destinies are either the creeper or a cycle.

New destinies do not appear too often in this sequence. That is why the sequence of new destinies might be of interest: 1, 3, 9, 29, 69, 2079, 3999, 6999, 10677, 20169, …. This sequence is A161590 in the Online Encyclopedia of Integer Sequences and it needs more terms. The length of the corresponding periods starting from the second term are: 8, 2, 18, 2, 2, 2, 14, which is the sequence A161593.

Destinies are kinda fun.

Decades ago there was a study in Russia that claimed that a woman worked four more hours a day than a man on average. Men and women were equal in Russia and all had the same 40-hours-a-week jobs. Women were not, by and large, housewives, for they worked full-time.

So where did the additional four hours come from? They were devoted to house chores. In Russia, women did everything at home — at a time when life in Russia was much more difficult. For example, my family didn’t have a washer, or a dryer or a dish-washing machine. Plus, everything was in deficit, so to buy milk or a sweater, women had to stand in lines, sometimes for hours.

My mother was very bitter because her husband, my father, never helped her. So I always hoped that when I got married, my husband would take on some of the house chores.

When I married Andrey, he was somewhat helpful — better than the average Russian husband. Then, when I was at grad school, we had a baby named Alexey. Andrey convinced me that I had to take over all the child care because only women could get academic maternity leave. It seemed logical and I agreed.

In a year, when the leave was over, I felt that Andrey should take over some of these duties. He refused. He insisted that since I already had published a paper when I was an undergrad, and since he still didn’t have his research results for his PhD, that he had to stay focused on his work. I wasn’t strong enough to resist.

We signed up for government child care — private care didn’t exist — but we were on the waiting list for a couple of years. Almost no one in Russia — certainly not graduate students — could afford a private babysitter. I couldn’t really work on my PhD research because between caring for the house and the baby, I never had big chunks of time. The best I could do was to start preparing for my qualifying exams.

Allow me to digress from my main story for a moment to mention my gray notebook. This notebook was our baby diary. Initially I recorded important baby data — like the first time Alexey smiled. But later, as soon as Alexey turned one year old, he became very eloquent; and this notebook became my son’s quote book.

One day Andrey and I went out and my mom babysat Alexey, who was two years old. When we returned, my mother recited the following quote from Alexey:

When will Daddy be back from the university and Mommy from the store?

I don’t really remember the long hours in stores or the cooking and cleaning. I remember the quote.

My son Alexey taught me to play “The Settlers of Catan .” This game is so good that throughout the four years of his undergraduate studies, he played it every evening. I am exaggerating of course, but only so slightly. He also taught me some of the game’s wisdom.

Lesson 1. Trading is beneficial for both traders.

When you agree to exchange your two rocks for one grain, one grain is more valuable to you than two rocks. The opposite is true for your trading partner.

Presumably, the same principle works for the economy. If I buy a sweater at T.J.Maxx for $20, I need the sweater more than $20. And if the store sells this sweater for $20, they are hoping to make some profit, that is, that the sweater cost them less than $20. Supposedly, shopping transactions are profitable for both parties.

Lesson 2. Trading is bad for non-trading players.

This is the consequence of the fact that in “Settlers of Catan” there is only one winner. If something is good for someone, it is bad for everyone else. In real life you do not have to lose if someone wins. With each shopping transaction everyone gains. This is the reason why shopping must be good for the economy.

Lesson 3. Powerful players can persuade other players to trade against their best interests.

Shortly after I moved to the US, I became very aware of my own smell. My smell didn’t change with my move from Russia, nor did my sense of smell change. I was just bombarded with deodorant advertisements, and due to the vulnerability of my self-perception, in one year I bought more deodorants than in all my previous 30 years. I have a friend who has an exceptional sense of smell. He told me that people often use much more deodorant and perfume than they need.

Lesson 4. You pay a lot for storage.

In Settlers, if you have more than seven cards and the dice rolls seven, you need to discard half of your hand. So if you have six cards and someone offers you three grains for one sheep, consider the storage price before jumping into this bargain deal.

Once I bought so much discounted toilet paper that it lasted me for months and months. When it was time to move to a different apartment, I had to pay for the largest truck available to fit all my junk.

Lesson 5. It is important to understand the goal of the person you are trading with.

A profitable deal becomes a big mistake when, as a result of the trade, your trading partner builds a settlement right in the spot where you were planning to build.

Similarly, if your doctor prescribes you a medication, it would behoove you to know whether he will reap any profit from it himself.

Lesson 6. If a player is the only receiver of rock in the game he dictates the price.

This is like a monopoly. I needed my last laptop more than the $1,000 I paid for it. But this price included pre-installed Windows, which I didn’t want and which I immediately deleted. I was forced to pay extra for Windows because of Microsoft’s monopoly.

So, is shopping good for the economy?

What about that skirt I bought and never used and eventually threw away? I wasted $20 on it. But the store didn’t gain that $20; they only gained their profit margin, which could have been $5. That means that together we wasted $15.

I do not throw away every piece of clothing I buy, but it is true that we buy more things than we need.

I think that going shopping to help our country get out of an economic crisis is a ridiculous idea. If you are shopping for other reasons than necessity, you do not help anyone and as a group we lose.

My son Alexey wins almost every game of “Settlers of Catan” he plays. So does my friend Mark Shiffer. The main reason is that they both know how to use trading effectively. To me that indicates that there are probably other people out there who know how to effectively sell deodorants, pills, clothing and other junk to us. I suspect that I lose in every shopping transaction, as I am an unskilled trader. If most folks are like me, could it be that shopping is actually bad for the economy?

Many years ago I conducted an experiment. I asked several sets of friends who had written joint math papers what they thought their individual contributions were. I asked them separately, of course. As the result of this experiment I formulated the conjecture:

The total of what joint authors estimate their contributions to be is always more than 100%.

Here is an actual example of answers I received from the two authors of a joint paper.

Author 1: My contribution is 80%. I suggested a breakthrough idea that made this paper possible. He just typed everything.

Author 2: My contribution is 80%. I did all the work. She just suggested a good idea.

You can see how the answers are synchronized. It is clear that both are telling the truth. People just tend to over-value their own input.

In other cases each author thinks that she or he generated the main idea. It doesn’t mean that one of them is lying. Very often they are absolutely sincere. Take this example of Alice and Bob, who are working on a paper together. Alice suggests that they might have better progress on their theorem if they consider graphs with symmetries first. Bob is engrossed in his thoughts and doesn’t register Alice’s suggestion. Next day, he comes up with an idea to add a group action on graphs. He sincerely believes that this was his own idea. It would be hard to know whether this had been provoked by Alice’s suggestion, or had come to Bob independently. Alice assumes that they are working on her idea.

When you acknowledge other people’s contribution, keep in mind that their perception might be different from yours. If you do not want to hurt other people’s feelings, you might consider inflating your gratitude.

The conjecture doesn’t apply to single-author papers. First of all, mathematicians never claim their contribution is 110% as non-mathematicians do. In many cases, especially when there are acknowledgements in the paper, it would be illogical to claim 100% contribution. Most mathematicians are logical, so if they are gracious enough to acknowledge the help of others, they are unlikely to claim 100%.

I would be curious to continue the experiment and either prove or disprove my conjecture. I’d appreciate your help. If you want to be part of this experiment, you can provide the following numbers in your comments: your average contribution to your own papers; and also your weighted average contribution to your joint papers.

I always thought that the famous equation

10² + 11² + 12² = 13² + 14²

is sort of a miracle, a random fluke. I enjoyed this cute equation, but never really thought about it seriously. Recently, when my son Sergei came home from MOP, he told me that this equation is not a fluke; and I started thinking.

Suppose we want to find five consecutive integers such that the sum of the squares of the first three is equal to the sum of the squares of the last two. Let us denote the middle number by n, which gives us the equation:

(n–2)² + (n–1)² + n² = (n+1)² + (n+2)².

After simplification we get a quadratic equation: n² – 12n = 0, which has two roots, 0 and 12. Plugging n = 0 into the equation above gives us (–2)² + (–1)² + 0² = 1² + 2², which doesn’t look like a miracle at all, but rather like a trivial identity. If we replace n with 12, we get the original miracle equation.

If you looked at how the simplifications were done, you might realize that this would work not only with five integers, but with any odd number of consecutive integers. Suppose we want to find 2k+1 consecutive integers, such that the sum of the squares of the first k+1 is equal to the sum of the squares of the last k. Let us denote the middle number by n. Then finding those integers is equivalent to solving the equation: n² = 2k(k+1)n. This provides us with two solutions: the trivial solution 0, and the non-trivial solution n = 2k(k+1).

So our miracle equation becomes a part of the series. The preceding equation is the well-known Pythagorean triple: 3² + 4² = 5². The next equation is 21² + 22² + 23² +24² = 25² + 26² + 27². The middle numbers in the series are triangular numbers multiplied by four.

Actually, do you know that 10² + 11² + 12² = 13² + 14² = 365, the number of days in a year? Perhaps there are miracles or random flukes after all.

My son, Sergei Bernstein, got accepted to MIT through early action. Because the financial costs of studying at MIT worried me, I insisted that Sergei also apply to Princeton and Harvard, as I had heard they give generous financial packages. In the end, Sergei was rejected by Princeton and wait-listed and finally rejected by Harvard. Though many people have been rejected by Princeton and Harvard, not too many of them have won places on US teams for two different international competitions — one in mathematics and the other in linguistics. To be fair, Sergei was accepted by these teams after Princeton had already rejected him. Nonetheless, Sergei has an impressive mathematical resume:

• In 2005 he was the National MathCounts Written Test Champion.
• In 2005 he was the National MathCounts Master’s Round Champion.
• In 2007 and 2009 he was a USAMO winner.
• In 2008 he passed Math 55a at Harvard taught by Dennis Gaitsgory, which is considered to be the hardest freshman math course in the country. More than 30 students started it and less than 10 finished. Sergei was one of the finishers, and he was only a high school junior.
• In 2007, 2008 and 2009 he competed at a 12th grade level at the Math Kangaroo, while he actually was in 10th, 11th and 12th grade. He placed first all three times.
• In 2009 he was on the US team at the Romanian Masters in Mathematics competition, which might be a harder competition than the International Mathematical Olympiad. He got a silver medal and was second on the US team.
• In 2009 he placed 5th in the North American Computational Linguistics Olympiad, making it to the Alternate US Team for the International Linguistics Olympiad.

I am trying to analyze why he was rejected and here are my thoughts.

1. His application forms to Harvard and Princeton were different from MIT. Yes, MIT was his first choice and he wrote a customized essay for MIT. For other places he had a common essay. But as he was supposed to be flagged as a top math student, his essay should have been irrelevant, in my opinion.
2. Admissions offices made a mistake. I can imagine that admissions offices never heard of the Romanian Masters in Mathematics competition, because it is a relatively new competition and the USA only joined it in 2009 for the first time. On its own, though, it should have sounded impressive. Also, they might not have known about the Math 55 course at Harvard, as usually high-schoolers do not take it. But that still leaves many other achievements. Many people told me that admissions offices know what they are doing, so I assume that I can disregard this point.
3. Princeton and Harvard knew that he wanted to go to MIT and didn’t want to spoil their admission rate. I do not know if colleges communicate with each other and whether Princeton and Harvard knew that he was admitted early to MIT. Because he had sent them a common application essay, they may have been suspicious that they weren’t his first choice.
4. Harvard and Princeton didn’t want him. I always heard that Harvard and Princeton want to have well-rounded people, whereas MIT likes geeks. I consider Sergei quite well-rounded as he has many other interests and achievements beyond mathematics. Perhaps his other accomplishments aren’t sufficiently impressive, making him less round than I thought he was.
5. Harvard and Princeton are not interested in mathematicians. Many people say that they want future world leaders. I think it is beneficial for a world leader to have a degree in math, but that’s just my personal opinion. And of course, to support their Putnam teams, it is enough to have one exceptional math student a year.
6. Sergei couldn’t pay. Yes, we marked on the application that we need financial help. In the current financial crisis it could be that even though Harvard and Princeton do not have enough money to support students, they do not want to go back and denounce their highly publicized generosity.

Many people told me of surprising decisions by Ivy League schools this year. The surprises were in both directions: students admitted to Ivy League colleges who didn’t feel they had much of a chance and students not admitted that had every right to expect a positive outcome. I should mention that I personally know some very deserving kids who were admitted.

I wonder if there has been a change in the financial demographics of the students Harvard and Princeton have accepted this year. If so, this will be reflected in the data very soon. We will be able to see if the average SAT scores of students go down relative to the population and previous years.

I do not know why Sergei wasn’t accepted; perhaps I’m missing something significant. But if it was because of our finances, it would be ironic: Sergei wasn’t admitted to Princeton and Harvard for the same reason he applied there.

I recently got a new job — to coordinate math students at RSI (Research Science Institute). RSI provides a one-month research experience based at MIT for high school juniors. The program is highly competitive and kids from all over the world apply for it.

Before the program started, I asked around among mathematicians for advice on how to do a great job with these talented kids. I was surprised by the conflicting opinions on the value of the program. I thought you’d be interested in hearing those opinions, although I confess that I do not remember who said what, or anyone’s exact words. I will just repeat the gist of it.

Former participants:

• I went there, it was awesome.
• I went there, it was underwhelming.
• Canada/USA math camp is more fun for sure.
• RSI is an absolutely fantastic experience for students, and I think the adults who take part enjoy it very much as well.

Potential participants:

• Cool, if I get there I’ll try to prove the Riemann Hypothesis.
• Last year Eric Larsen won $100,000 as a result of this program. If twenty math students participate, then the expected return is $5,000 per one month of work — not bad for a high-schooler.
• MIT is my dream school; just to be there will be inspiring.
• I will prove the Riemann Hypothesis.
• Yeah, I can become famous.
• Cool, I want to be a mathematician — I should try this.
• I love Canada/USA math camp and I’d rather go there.

Grad students, former and potential mentors:

• My professor doesn’t have a good problem for me. If he gives a nice problem to a high school student, that will be unfair.
• It’s just a job.
• What if I solve the problem first, do I keep silent? — That doesn’t make any sense.
• What if this high school student is better than me? That would be a bummer.
• This job was a lot of fun; I enjoyed it.
• I used to participate in RSI myself, and that was great. Now I would like to be on the giving side.
• RSI teaches students how to get versed in impressing people. For the Meet-Your-Mentor Night the students showed up in suits. How many real mathematicians do you know that own a suit?

Professors on the program in general:

• Usually students study mathematics for many years. RSI allows them to actually do mathematics.
• I studied for many years before I could start to do research. This RSI experiment is degrading to mathematics and disrespectful to mathematicians.
• Most students are wired towards problem solving, and very often they need only one basic idea and 15 minutes to solve a problem. Research has a completely different pace; it is important that kids try it.
• Some students go to this program because they want to win competitions and get to good colleges. These goals should be secondary. We should accept students because they want to try research.
• One month for research? Is this a joke? Do you like fast food?
• These are the best students from around the country. It feels nice when a potential future Fields medalist looks up to you.
• These students might be better than average undergraduate students at MIT. It might be fun to work with them.
• I think that the number of students who might be a good fit for such a program is very small; the number of professors who might be a good fit is very small too. If this program grows it might become completely useless.
• High school students are being mentored by grad students, who themselves have just started their own research. Grad students do not have enough experience to really guide people through research.
• It is such a great opportunity to get a taste of research while you are in high school.
• People usually choose projects for their research. These kids are given projects: this is not research — it’s slave labor.
• One month is not enough for interesting research. It would be good if students use this month to jump-start some research and then continue it after the program.
• It’s a waste of time to learn mathematics for many years and then discover that you do not like research. This program gives an opportunity for students to decide whether they are interested in research very early in their lives. This is tremendously useful.

I asked some math professors to suggest problems for these students:

• I have some problems I can give, but they require deep knowledge of topology. The students would need to take some courses to understand the second paragraph of the paper I would give them, which they can’t succeed in doing in a month. Can we replace this program with my course?
• It wouldn’t be nice to give them a problem that is too difficult. If the problem is easy, then I usually have an idea how to solve it. Instead of wasting two hours describing an easy problem to students, I can use this time to solve it myself.
• Ask Ira Gessel or Pavel Etingof. I have heard that they generate problems faster than their graduate students solve them.
• I have some leftover problems I can give away. However my concern is this: what if they solve it or mostly solve it, but then go back to school without writing their paper. What do I do? Giving the same problem to someone else or writing a paper myself without mentioning the student would not be kosher. Writing a joint paper for them is a burden. I need to think about a leftover problem I do not care about.
• If I have a good project, I will give it to my graduate students. Why would I invest in a high school student who is here for a month and probably is not ready for this anyway?
• That’s great, the online database of integer sequences contains tons of conjectures. They even have an index pointing towards “Conjectured sequences” and towards “Unsolved problems”. Besides, you can search the database for the words “conjecture”, “apparently” or “appears”. There is also an article by Ralf Stephan describing 100 conjectures from the OEIS.
• I have some things I need to calculate, but I do not know programming. If someone can do this for me that would be good.
• They usually want to submit papers for competitions, which means they do not want me to be a coauthor. I do not have problems I just want to throw away.
• Richard Stanley keeps a list of unsolved problems, ask him.
• There is a list of unsolved problems on wiki, but they are too difficult.
• They can always try to find a different proof for something.

The 2009 RSI has just begun. We have awesome students, great mentors and quite interesting problems to solve. I am positive we’ll prove the negativists wrong.

Let me remind you of a very interesting problem from my posting Oleg Kryzhanovsky’s Problems.

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?

I do not want you to find the weight of each coin; I just want you to say yes if the labels are correct, or no if they are not.

I have given this problem to a lot of people, and not one of them solved it. Some of my students mistakenly thought that they succeeded. For example, they would start by putting the coins labeled 1 and 2 on the left cup of the scale and 3 on the right cup. If these coins balanced, the students assumed that the coins on the left weighed 1 and 2 grams and that the coin on the right weighed 3 grams. But they’d get the same result if they had 1 and 4 on the left, for example, and 5 on the right. I am surprised that no one has solved it yet, as I thought that this problem could be offered to middle-schoolers, since it does not actually require advanced mathematical skills.

If you want to try to solve this problem, pause here, as later in this essay I will be providing a number of hints on how to do it. The problem is fun to solve, so continue reading only if you are sure you’re ready to miss out on the pleasure of solving it.

I propose the following sequence a(n). Suppose we have a set of n coins of different weights weighing exactly an integer number of grams from 1 to n. The coins are labeled from 1 to n. The sequence a(n) is the minimum number of weighings we need on a balance scale to confirm that the labels are correct. The original Oleg Kryzhanovsky’s problem asks to prove that a(6) = 2. It is easy to see that a(1) = 0, a(2) = 1, a(3) = 2. You will enjoy proving that a(4) = 2 and a(5) = 2.

In general, we can prove that a(n) ≤ n-1. For any k < n, the k-th weighing compares coins labeled k and k+1. If we get the expected result every time, then we can confirm that the weights are increasing according to the labels.

On the other hand, we can prove that a(n) ≥ log₃(n). Indeed, suppose we conducted several weighings and confirmed that the labels are correct. To every coin we can assign a sequence of three letters L, R, N, corresponding to where the coin was placed during each weighing — left cup, right cup or no cup. If two coins are assigned the same letters for every weighing, then we can’t confirm that the labels on these two coins are accurate. Indeed, if we switch the labels on these two coins, the results of all the weighings will be the same.

My son, Alexey Radul, sent me the proof that a(10) = a(11) = 3. As 3 is the lower bound, we just need to describe the weighings that will work.

Here is the procedure for 10 coins. For the first weighing we put coins labeled 1, 2, 3, and 4 on one side of the scale and the coin labeled 10 on the other. After this weighing, we can divide the coins into three groups (1,2,3,4), (5,6,7,8,9) and (10). We know to which group each coin belongs, but we do not know which coin in the group is which. The second weighing is 1, 5 and 10 on the left, and 8 and 9 on the right. The left side should weigh less than the right side. The only possibility for the left side to weigh less is when the smallest weighing coins from the first and the second group and 10 are on the left, and the two largest weighing coins from the first two groups are on the right. After the second weighing we can divide all coins into groups we know they belong to: (1), (2,3,4), (5), (6,7), (8,9) and (10). The last weighing contains the lowest weighing coin from each non-single-coin group on the left and the largest weighing coin on the right, plus, in order to balance them, the coins whose weights we know. The last weighing is 2+6+8+5 = 4+7+9+1.

Here is Alexey’s solution, without explanation, for 11 coins: 1+2+3+4 < 11; 1+2+5+11 = 9+10; 6+9+1+3 = 8 +4+2+5.

Let me denote the n-th triangular number as T_n. Then a(T_n) ≤ a(n) + T_n – n – 1. Proof. The first weighing is 1+2+3 … +n = T_n. After that we can divide coins into groups, where we know that the labels stay within the group: (1,2,…,n), (n+1,n+2,…,T_n-1), (T_n). We can check the first group in a(n) weighings, the second group in T_n – n – 2 weighings, and we already used one. QED.

Similarly, a(T_n+1) ≤ a(n) + T_n – n.

For non-triangular numbers there are sometimes weighings that divide coins into three groups such that the labels can only be permuted within the same group. For example, with 13 coins, the first weighing could be 1+2+3+4+5+6+7+8 = 11+12+13. After that weighing we can divide all coins into three groups (1,2,3,4,5,6,7,8), (9,10), (11,12,13).

In all the examples so far, each weighing divided all the coins into groups. But this is not necessary. For example, here is Alexey’s solution for 9 coins. The first weighing is 1+2+3+4+5 < 7+9. When we have five coins on the left weighing less than two coins on the right, we have several different possibilities of which coins are where. Other than the case above, we can have 1+2+3+4+6 < 8+9 or 1+2+3+4+5 < 8+9. But let’s look at the next weighing that Alexey suggests: 1+2+4+7 = 6+8. Or, three coins from the previous weighing’s left cup, plus one coin from the previous weighing’s right cup equals the sum of the two coins that were left over. This can only be true if the coins in the first weighing were indeed 1+2+3+4+5 on the left and 7+9 on the right. After those two weighings everything divides into groups (1,2,4), (3,5), (6,8), (7) and (9). The last weighing 1+7+9 = 4+5+8, resolves the rest.

To check 7 or 8 coins in three weighings is simpler than the cases for 9, 10, and 11 coins, so I leave it as an exercise. As of today I do not know if it is possible to check 7, 8 or 9 coins in two weighings. Consider this a starred exercise.

I invite you to play with this amusing sequence and calculate some bounds. Also, let me know if you can prove or disprove that this sequence is non-decreasing.