3

I know the famous 12 coin, 3 weighings problem has been asked a few times already. And I saw at least one solution which can be adapted to this problem. Here's a generalisation (one of the many which could be done of course).

Suppose you have 120 coins, all identical, except for 1 which is a slightly different weight. You have a pan balance, and need to make as few weighings as possible to identify both (a) which coin is counterfeit, and (b) whether it's heavier or lighter.

Pan balance

There's no cheating, like adding coins on half way (weigh?) through - that would be an additional weighing.

The answer may surprise some people. I would like to know:

  • How many weighings are needed, and
  • A reasonable strategy for doing this

A common solution to the 12 coin puzzle involves...I can barely type the word...cases (gasp)! That would get tricky for 120 coins, but you are, of course, most welcome to do so! I can't promise to read through all the cases and mark it right though.

Rohcana
  • 4,010
  • 21
  • 49
Dr Xorile
  • 23,406
  • 3
  • 47
  • 125
  • I'm not quite sure what kind of solution you expect. The extension of a well known solution to 120 coins, which you don't want to read? – Sleafar Sep 12 '15 at 18:36
  • My concern is with cases. The solutions that use cases are long, even for the 12 coin puzzle. But other strategies exist... – Dr Xorile Sep 12 '15 at 18:38
  • You mean something like the 2nd answer here: http://puzzling.stackexchange.com/questions/183/twelve-balls-and-a-scale ? – Sleafar Sep 12 '15 at 18:52
  • Exactly! The 1st answer uses cases, but the second is more easily generalizable. – Dr Xorile Sep 12 '15 at 18:58
  • Specifically, look at my accepted answer at the bottom if you want a strategy that doesn't use cases. –  Sep 13 '15 at 02:51

2 Answers2

3

First, number the coins using Balanced Ternary. This is a ternary numeral system using the digits -, 0, and + to represent -1, 0, and 1.

For the sake of brevity I'm going to illustrate this using 12 coins, but this can be easily extended to larger numbers. Just add more trits to each number. (For example, 120 coins would require 5 trits, corresponding to 5 weighings.)

  • 1 = 00+
  • 2 = 0+-
  • 3 = 0+0
  • ...
  • 11 = ++-
  • 12 = ++0

Each of these can also be inverted by swapping each symbol.

  • -1 = 00-
  • -2 = 0-+
  • -3 = 0-0
  • ...

This numbering now tells us where to place the coins.

For the first weighing, put all the coins with a + in their first trit on the right pan, and all the coins with a - in their first trit in the left pan. Leave all the coins with a 0 in their first trit off. Then record the result: if it tips to the left, that's a -. If it tips to the right, that's a +. If it is balanced, that's a 0.

Repeat as many times as necessary, then look at the number you've recorded. With 12 coins there will be three weighings, so the result might be e.g. +-+ (tipped to the right, tipped to the left, tipped to the right). This is the number of the false coin. If it's positive, that coin is heavier. If it's negative, that coin is lighter. If the number is zero, no coin was fake.

HOWEVER, this doesn't actually work precisely as I have written it. No positive number has a - in its first trit, so the first weighing will have one pan empty. Unless you have a stock of real coins to compare against (a variant of the problem), it won't be a useful measurement.

So we need to invert some of the coins' numbers (so coin 5 might become coin -5), then interpret the result differently if one of these is chosen: a negative number will now mean that the fake coin is heavier, and a positive number that it is lighter.

This is where I got stuck in my own experimentation, but some web research indicates that John Conway came up with a very clever way to determine which ones to flip: go through the coins, and look at the first "change" in the sequence. If it is - to 0, or 0 to +, or + to -, keep it positive. Otherwise, invert that number.

This isn't as elegant as I would like—it feels like there should be some way to decide mathematically which numbers to invert. But for now, that solution is the best I have.

Glorfindel
  • 28,033
  • 9
  • 96
  • 142
Draconis
  • 251
  • 1
  • 5
1

Each weighing allows you to triple the number of coins, so you should be able to do 36 coins in four weighings, 108 in five, but require six for 121 coins. The solution for 12 coins only gets complex for the endgame. For 108, you split them into three batches of 36 and weigh two batches. If they balance, you are down to the 36 case. If not, you have 36 H coins (which might be heavy) and 36 L coins (which might be light). Weigh 12H+12L against 12H+12L. No matter the result, you now have 12H+12L and can weigh 4H+4L against 4H+4L. No matter the result, you are in the 12 coin case where the first weighing did not balance.

Ross Millikan
  • 8,419
  • 30
  • 47