Ponder This Challenge - June 2002 - Coin weighing using scale

Ponder This Challenge:

This month's puzzle is based on a suggestion of Alex Marmer. It's another coin-weighing problem.

You are given a scale with two pans. This scale will report the difference, in grams, between the masses on the two sides, as well as telling you which side is heavier. So if you place 25 grams on the left pan and 27 grams on the right, you find out that the right side is heavier by 2 grams.

You are given N bags of coins, apparently identical. Each bag contains ten coins. Exactly one bag is full of counterfeit coins, and the rest are full of honest coins . All honest coins are equally massive, all counterfeit coins are equally massive, and counterfeit coins are heavier than honest coins. But you don't know beforehand the masses of honest coins or of counterfeit coins.

You are given the opportunity to make three weighings on your scale, after which you must decide which bag is bogus. You're allowed to open the bags and use an arbitrary number of coins from each bag, if that helps; just keep track of where you got the coins.

What is the largest value of N which can be accommodated?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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

Solvers

• Jacques Willekens (6.5.2002 @ 10:00 AM EDT)
• Michael Malak (6.5.2002 @ 10:00 AM EDT)
• Chris Wilson (6.5.2002 @ 10:00 AM EDT)
• Chu-Wee Lim (6.5.2002 @ 11:45AM EDT)
• Graeme McRae (6.6.2002 @ 10:30AM EDT)
• Maxim G. Smith (6.6.2002 @ 10:30AM EDT)
• Christopher Howe (6.6.2002 @ 10:30AM EDT)
• Robert J. Sides (6.10.2002 @ 10:00AM EDT)
• Ervan Darnell (6.10.2002 @ 10:00AM EDT)
• Ed Sheppard (6.10.2002 @ 10:00AM EDT)
• John G. Fletcher (6.10.2002 @ 10:00AM EDT)
• John McGee (6.10.2002 @ 4:00PM EDT)
• Christie Bolton (6.12.2002 @ 1:30PM EDT)
• Sunil Srivastava (6.14.2002 @ 10:30AM EDT)
• Dan Ungureanu (6.14.2002 @ 10:30AM EDT)
• Piotr Zielinski (6.14.2002 @ 10:30AM EDT)
• Ashish Mishra (6.17.2002 @ 9:30AM EDT)
• Sorav Bansal (6.17.2002 @ 9:30AM EDT)
• Varun Sagar Malhotra (6.17.2002 @ 1:30PM EDT)
• Itsik Horovitz (6.20.2002 @ 10:00AM EDT)
• Andy Lowry (6.20.2002 @ 10:00AM EDT)
• Ish Dham (6.20.2002 @ 10:00AM EDT)
• Nagendra (6.20.2002 @ 10:00AM EDT)
• David McCabe (6.20.2002 @ 10:00AM EDT)
• BV Vaidyanath (6.20.2002 @ 10:00AM EDT)
• Alex Wagner (6.20.2002 @ 10:00AM EDT)
• Sarang Aravamuthan (6.21.2002 @ 10:00AM EDT)
• Doug Scripture (6.21.2002 @ 10:00AM EDT)
• Shmuel spiegel (6.21.2002 @ 10:00AM EDT)
• José Manuel Ezquerra (6.21.2002 @ 10:00AM EDT)
• Vince Lynch (6.25.2002 @ 10:00AM EDT)
• Adrian Fernandes (6.25.2002 @ 10:00AM EDT)
• Stephen Martin (6.25.2002 @ 10:00AM EDT)
• Thomas Russo (6.25.2002 @ 10:00AM EDT)
• Peter Bennett (6.25.2002 @ 2:00PM EDT)
• Mitchell A. Kaplan (6.26.2002 @ 2:00PM EDT)
• Divyesh Dixit (6.26.2002 @ 3:00PM EDT)