June 2002
N=7491.
To start, define G(k) as the number of k-tuples of positive integers, between 1 and 10 inclusive, where each k-tuple is relatively prime (meaning that no integer larger than 1 evenly divides all k entries).
By the principle of "inclusion and exclusion", we can calculate:
G(3) = 10**3 - 5**3 - 3**3 - 2**3 - 1**3 + 1**3 + 1**3 = 841.
G(2) = 10**2 - 5**2 - 3**2 - 2**2 - 1**2 + 1**2 + 1**2 = 63.
G(1) = G(0) = 1.
Taking for example G(3), we start with all 10**3 triples, then subtract off the 5**3 triples of even integers, subtract off the 3**3 triples of integers divisible by 3 (3,6,9), and the 2**3 triples of integers divisibly by 5, and the 1**3 triple of integers divisible by 7 (7,7,7). Then we have to add back the triples (6,6,6) and (10,10,10), each of which had been included once but subtracted twice, so has to be added back in to bring its contribution to 0.
For each of the 8 choices of a triple of letters ("L" or "R"), and each of the G(3) choices of relatively prime positive integers, we will assign one bag. If the letters were (L,L,R) and the integers were (4,6,3), then on the first weighing we would put four coins from this bag on the left pan; on the second weighing, six coins on the left; and on the third weighing, three coins on the right pan.
For each of the 12 arrangements of two letters and one "0" (such as (0,L,L)), and each of the G(2) choices of pairs of integers, we will assign one bag. (0,L,L) along with (2,3) means that on the first weighing we don't use this bag; the second weighing sees two coins from this bag on the left pan; the third weighing sees three coins on the left pan.
Each of 6 arrangements of one letter and two "0", along with the G(1)=1 choice of a single integer (1), in the same way: (0,R,0) with (1) means that on the second weighing we place one coin on the right, and ignore the other weighings.
Finally one bag is assigned to (0,0,0) and the 0-tuple (); its coins are never weighed.
Calculate 8*G(3)+12*G(2)+6*G(1)+1*G(0)=8*841+12*63+6*1+1*1=7491.
First, notice that on each of the three weighings, we have an equal number of coins on the left and on the right, because for bag and its assignment of letters (L,L,R) and integers (2,3,1), another bag has the opposite letters (R,R,L) and the same integers (2,3,1).
Now suppose the honest coins have mass m grams and the counterfeit coins are m+z grams. If the counterfeit bag had letters (L,R,0) and 2-tuple (3,5), then the first weighing would show the left side being heavier by 3z, the second weighing shows the right side heavier by 5z, and the third weighing shows them equal. We can read off the letters (L,R,0) directly. Sinnce we don't know z, we know only the ratio (3z:5z), which could mean either (3,5) or (6,10). This is why we chose our k-tuples to be relatively prime -- (6,10) is disallowed, and we know the correct answer to be (3,5).
So we can successfully distinguish among 7491 bags.
To show this is also an upper bound, we just reverse the argument. Suppose we even know the mass m of an honest coin, but still do not know the mass m+z of a counterfeit coin. Then we still cannot distinguish more than 7491 bags.
On the first weighing, if there are L1 coins on the left and R1 on the right, and LC1 of those on the left and RC1 of those on the right are counterfeit, then the scale will show ((L1-R1)*m + (LC1-RC1)*z) extra weight on the left.
Let's denote k1=LC1-RC1. Since we know m, L1 and R1, we can deduce
the product k1*z=(LC1-RC1)*z, where |k1| is at most 10. Repeat the process on each of three weighings. We obtain a triple (k1*z,k2*z,k3*z).
As mentioned before, the triple (3z,-5z,0z) is indistinguishable
from the triple (6w,-10w,0w), where w=z/2.
So all we have to go on is the ratios and the signs of the three numbers. Each pairing of (letters) with (k-tuple of relatively prime integers) can be associated with only one bag, since otherwise two bags would be indistinguishable. This shows that 7491 is the largest achievable N.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com