How many Weighings for N coins?

Detalles

Categoría padre: Detras del pesaje

Categoría: Quiz

Publicado en Domingo, 28 Agosto 2011 18:57

Impactos: 3466

How Many Weighings for N Coins?

Mike Boughton wrote the original puzzle:

> There is an old one called the 12 penny problem:  You have 12 coins, all
> apparently alike, but one is either heavier or lighter.  Your job is to
> find which and which one in 3 weighings on a balance using only the coins
> themselves.
>
> This version does not require any math.  Somehwere I saw a response that
> does. Not only did it contain the solution for 12, which takes a few
> minutes to figure out, but the general solution of how many weighings it
> takes for n coins.

Start with the simplifiying assumption that you know the odd coin is heavier (or lighter).  Call this the "Known Weight" problem.  Then weighing A:B will result in knowing which group the odd coin is in.

If A=B, then the odd coin is in C.
If A>B, then the odd coin is in A.
If A<B, then the odd coin is in B.

Then you can divide that group into three equal groups, say a, b, and c, and repeat the process.

Thus, the odd coin can be found out of 3^N coins in N weighs.

Weighs  Number  Group   Group   Group
1       3       1       1       1
2       9       3       3       3
3       27      9       9       9       27 = 3^3
...

If the number of coins is not divisible by 3, then divide the number into two (N/3)+1 groups with the remainder in the third group.

Using this technique, the odd coin of known weight can be found out of N coins in log3(N) weighs, and since the number of weighs must be an integer, in roundup[log3(N)] weighs.

Weighs  Number  Group   Group   Group
1       2       1       1
2       5       2       2       1
3       15      5       5       5       log3(15) = 2.46

Now add back in the fact that you don't know whether the odd coin is heavier or lighter.  This just adds one more weighing.  Divide the coins into three groups as before, say A, B, and C, and first weigh A:C, and then weigh A:B.

If A>C, then B must contain standard coins, so weigh A:B.
If A>B, then just like the Known Weight problem with a heavier coin in A.
If A=B, then just like the Known Weight problem with a lighter coin in C.
If A<C, then B must contain standard coins, so weigh A:B.
If A<B, then just like the Known Weight problem with a lighter coin in A.
If A=B, then just like the Known Weight problem with a heavier coin in C.
If A=C, then A and C must contain standard coins, so weigh A:B
If A>B, then just like the Known Weight problem with a lighter coin in B.
If A<B, then just like the Known Weight problem with a heavier coin in B.

Using this technique, the odd coin of unknown weight can be found out of N coins in 1+roundup[log3(N)] weighs.

• < Previo
• Siguiente >