## Coins Sequence

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) ≥ log3(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 Tn. Then a(Tn) ≤ a(n) + Tn – n – 1. Proof. The first weighing is 1+2+3 … +n = Tn. 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,…,Tn-1), (Tn). We can check the first group in a(n) weighings, the second group in Tn – n – 2 weighings, and we already used one. QED.

Similarly, a(Tn+1) ≤ a(n) + Tn – 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.

Share:

1. #### Andrei Zelevinsky:

Hi, Tanya. Check this out: https://bravchick.livejournal.com/7815.html.

2. #### Tanya Khovanova:

From Max Alekseyev:

Exhaustive search tells that each a(7), a(8), a(9) >= 3.

btw, for 6 coins there exists exactly two essentially different solutions with two weightings:

6=1+2+3 and 1+6<3+5

3+6>1+2+5 and 1+3<5

3. #### Konstantin Knop:

I can prove that a(12)=a(13)=a(14)=a(15)=a(16)=a(17)=3 and a(53)=4.

4. #### Konstantin Knop:

Another interesting variant:
You have 8 coins weighing 1, 2, …, 8 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6, 7, 8) on the top of each coin should correspond to its weight. How can you determine whether ONE of the numbers is correct, using the balance scale only ONCE?

5. #### Tanya Khovanova:

Konstantin,

Wow, that’s amazing programming.

Now we have enough information to know that the coin sequence is not in the OEIS. The only other sequence that starts the same is A084558 (a(n) = largest m such that n >= m!), which is clearly a different sequence. Would you like to submit the coin sequence to the OEIS?

6. #### Tanya Khovanova:

I would like to clarify the coin puzzle suggested by Konstantin:

Baron Munchhausen has 8 coins weighing 1, 2, …, 8 grams that look the same. Baron knows which coin is which and wants to demonstrate to his guests that he is right . He plans to conduct one weighing on the balance scale without using anything else, so that the guests will be convinced about the weight of one of the coins. Can the baron do this?

7. #### Tanya Khovanova:

Konstantin Knop provided me with the following reference for the six-coins problem. This problem appeared at the last round of Moscow math Olympiad in 1991. The author of this problem is Sergey Tokarev:
https://kvant.mirror1.mccme.ru/1991/09/p70.htm

8. #### Alexey Ustinov:

I think that it will be more natural to think about lower bounds in more general case. Suppose we can choose arbitrary weights for our coins and we want to prove that they have correct labels. Problem could be more simple if we assume that no two groups has equal weights. Is log_2(n) the right order for the number of weighings?

9. #### Tanya Khovanova:

Alexey U.,

An interesting case is when coins’ weights form a geometric progression with the ratio at least 2. In particular, no two groups of coins have equal weights. I just received a proof from Alexey Radul that in this case you need at least n-1 weighings:

Observe that in any weighing with geometric weights, the scales are never equal, and the heaviest coin on the scale determines the result completely. Now suppose there is a sequence of weighings that purports to verify the geometric labels. Consider the coin labeled k (for k > 1). Is there a weighing in which that coin is the highest labeled coin on the scale? If not, I claim the sequence of weighings cannot distinguish between the correct labeling, and the situation where k has been switched with the next smaller coin (say k/2). Why?
Well, every weighing that includes a coin labeled higher than k will come out the same, every weighing that includes neither k nor k/2 will come out the same, and every weighing that includes k/2 but not k will also come out the same, because in those cases k/2 was supposed to dominate, and k can dominate in its stead perfectly well. Therefore, each coin labeled k (k > 1) must appear in a weighing where it is the heaviest coin, and therefore there must be at least n-1 weighings.
Q.E.D.

10. #### Alexey Ustinov:

It is clear. But what is the right order of lower bound for the number of weighings (if we want to minimize this number using spesial weights)? Is it log n or n?

11. #### Tanya Khovanova’s Math Blog » Blog Archive » Another Coins Sequence, jointly with Alexey Radul:

[…] 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. […]

It is clear that the sequence is non-decreasing. Suppose we are doing the problem for N. Add a weight of value N+1 and label N+1. Solve the problem for N+1. This is a solution for N because if it turns out tht they are correctly labelled from 1 to N+1 then obv its true that 1 to N were correctly labelled. And if it is proved that they aren’t also, since N+1 was labelled correctly, the mistake was definitely in 1…N. Hence clearly, the sequence is non-decreasing.