A Random Scale Solution
I recently posted the following puzzle:
Puzzle. We have 32n identical-looking coins. One of the coins is fake and lighter than the other coins, which all are real. We also have three scales: two normal and one random. Find the fake coin in the smallest total number of weighings.
Here is my son Sergei’s solution. Divide the coins into nine groups of equal size and number the groups in ternary: 00, 01, 02, 10, 11, 12, 20, 21, and 22. On each scale we put three groups versus three groups. On the first scale we compare the three groups that start with 1 with the three groups that start with 2. For the second scale we do the same using the last digit instead of the first one, and for the third scale we use the sum of two digits modulo 3. Any pair of scales, if they are assumed to be normal, would point to one out of nine groups as the group containing the fake coin.
If all three pairs of scales agree on one group, then this is the group containing the fake coin. Thus in three weighings, we reduce the number of groups of coins by a factor of nine. If the pairs of scales do not agree, then the random scale produced a wrong weighing and thus can be found out. How do we do that? We have three out of nine groups of coins each of which might contain the fake coin. We compare two of the groups on all three scales. This way we know exactly which group contains the fake coin and, consequently, which scale generated a wrong weighing. If we know the random scale, we can speed up the rest of the process of finding the fake coin. Thus in the worst case we require 3n+3 weighings.
The big idea here is that as soon as the random scale shows a wrong weighing result it can be found out. So in the worst case, the random scale behaves as a normal scale and messes things up at the very end. Sergei’s solution can be improved to 3n+1 weighings. Can you do that?
The improved solution is written in a paper Взвешивания на «хитрых весах» (in Russian) by Konstantin Knop, that is published in Математика в школе 2009-2. The paper contains an even stronger solution that provides a better asymptotics.
Share:
impartial james:
You can do much better than 3n+1. You can find the fake among 3^{2n} coins with at most 2n + \sqrt{2n} + 1 weighings.
The strategy is easiest to describe when you assume n = 1 + 2 + … + k is a triangular number, in which case it is possible to succeed in 2n + k + 1 weighings (note k is approximately \sqrt{2n}). Call the scales A, B, C. There are 2n unknown trits of information. For the first 2k weighings, use A to attempt to determine the first k trits, then use B to determine the next k trits. Let SA be the set of 3^{2n-k} coins whose first k trits agree with the result of A’s weighings, similarly for SB. This means the fake coin is in SA if and only if A’s weighings were all correct, either because A was a normal scale or by chance.
For the next weighing, use C to weigh SA\SB against SB\SA (\ is set difference).
– If this weighing balances, we know first 2k weighings were correct, leaving 3^{2n-2k} possibilities for the fake. Since n – k = 1 + 2 + … + (k-1) is the previous triangular number, we can recursively apply the same strategy to these coins. By induction, 2(n-k) + (k-1) + 1 = 2n – k more weighings are needed.
– If (say) SA\SB is lighter, then either B or C must have given an incorrect weighing, so A must be a normal scale. We have already used A to measure k trits, so 2n – k more uses of A suffice to find the fake.
Either way, 2n – k more weighings are needed, which combined with the first 2k+1 weighings makes 2n+k+1, as claimed.
For n which are not triangular numbers, write n = T + j, where T is the largest triangular number less than n. Do as described in the last paragraph, except starting with A and B each measuring j trits. In the worst case this will take 2n + 1 + (k+1) weighings, where T is the kth triangular number.
13 March 2017, 4:51 pm