0

Most people are familiar with the following problem:

A well-known example has nine (or fewer) items, say coins (or balls), that are identical in weight save for one, which in this example is lighter than the other —a counterfeit (an oddball). The difference is only perceptible by weighing them on scale—but only the coins themselves can be weighed. Is it possible to isolate the counterfeit coin with only two weighings?

To find a solution, we first consider the maximum number of items from which one can find the lighter one in just one weighing. The maximum number possible is three. To find the lighter one we can compare any two coins, leaving the third out. If the two coins tested weigh the same, then the lighter coin must be one of those not on the balance. Otherwise, it is the one indicated as lighter by the balance.

Now, imagine the nine coins in three stacks of three coins each. In one move we can find which of the three stacks is lighter (i.e. the one containing the lighter coin). It then takes only one more move to identify the light coin from within that lighter stack. So in two weighings we can find a single light coin from a set of 3 X 3 = 9.

By extension, it would take only three weighings to find the odd light coin among 27 coins, and four weighings to find it from 81 coins.

wikipedia: https://en.wikipedia.org/wiki/Balance_puzzle

Simple enough.

But what if you have an unknown number of coins, one being lighter than the other, and you want to know the minimum number of times you will have to use the scale to find the odd one out.

Does anyone know of a formula to calculate it?

Thanks

Community
  • 1
Freddie
  • 3
  • 2
  • Is there only 1 lighter coin? – qwertylpc Jul 16 '15 at 14:15
  • @f' : I assume he means: generalise a formula for any number 'n' to determine the maximum amount of weighings required. So instead of solving this for a given number of coins, solve it for ANY number. – Tim Couwelier Jul 16 '15 at 14:22
  • I don't think that this is a duplicate of the linked question. The linked question involves a ball which may be lighter or heavier. When the odd one out is known to be lighter, as in this question, the strategy is much simpler. – f'' Jul 17 '15 at 11:14
  • I was surprised that I couldn't find this question already on Puzzling.SE, but Math.SE has a duplicate: http://math.stackexchange.com/questions/69565/ – f'' Jul 17 '15 at 11:15

1 Answers1

2

I would have to guess that for an amount n the amount of weighings x would have to go according to the following rule

$n\le3^x$

or therefor:

$x=\lceil\log_3n\rceil$

I'll explain my reasoning:

for n = 2 and n = 3: One single weighing suffices

for n = 4 to 9: Can always be split out in two groups of either 2 or 3, with a remainder smaller then 3. Either way the initial weighing will reduce the problem to the steps for n=2 or n=3, so 1 weighing + 1 extra for the lower grade of the problem = 2

for n = 10 to 27 Can always split this up in two equal groups of 4 to 9, with a remainder of at most 9. Therefor one single weighting reduces this to a lower grade of the problem. So now we have three weighings: a first to reduced it to maximum 9 elements containing the odd one out, a second to reduce it to maximum 3 elements, and a third for the decider.

You've probably noticed a pattern emerging now: Using the partitions in three groups you can always take down the complexity one step each time. You just need a rule to figure out how many steps.

Community
  • 1
Tim Couwelier
  • 4,349
  • 21
  • 37