83 replies to this topic

[wangsacl]

You've got 27 coin, each of them is 10 g, except for 1. The 1 different coins has a masses different. It could be 9 g, or 11 g (heavier, or lighter by 1 g).
The question is, in how many minimum ways, you can determine the different coins, and is it heavier, or lighter?
I have no answer to this question.
Do you?

[mdsl]

Assuming you have a simple scale, my answer is 9.

First divide the coins into 3 piles of 9.

Measure 2 piles at a time until you find the pair that is equal in mass. This can take up to 3 tries, but if you were lucky you could get it on the first try.

Put the piles of coins with equal mass to the side.

Repeat the process this time with 3 piles of 3 coins, maximum 3 measurements.

Repeat the process this time with the 3 remaining coins, find the two that are equal, the remaining coin has a different mass.

If you are a very luck person you coulp potentially only have to make 4 meaurements, 3 to rule out equal pairs and 1 to compare the final coin to the rest.

9 is the most you would have to do the efficient way, and at any point you can observe is the unequal pile has more or less mass.

[CedricLi]

I guess the question is lack of some information such as, by using a scale with weight of 1g, 2g, 5g, and 10g, isn't it?

[bonanova]

I guess the question is lack of some information such as, by using a scale with weight of 1g, 2g, 5g, and 10g, isn't it?

It's a balance scale that compares what's in the two pans.
You can get the answer by just comparing groups of coins.

[bonanova]

Duplicate post.
Looking around the forum for an eraser ... <_<

[PDR]

Spoiler for fewer than 9...

1-9 vs 10-18
-if it balances, the odd one is in 19-27
-if it doesn't balance:

[PDR]

Spoiler for fewer than 9...

1-9 vs 10-18
-if it balances, the odd one is in 19-27
-if it doesn't balance:

[PDR]

sorry - accidentally hit submit - here's my answer...

Spoiler for fewer than 9...

this can be done in 5 weighings:

weigh coins [1-9] vs [10-18] (ie coins 1 thru 9 on one side, coins 10 thru 18 on the other)
if it balances, the odd one is in 19-27
if it doesn't balance, weigh [1-9] vs [19-27]
-if it balances, the odd one is in 10-18
-if it doesn't balance, the odd one is in 1-9

after 2 weighings we know which group of 9 has the odd one and weather the odd coin is heavier or lighter than the others. For the remainder of the explanation, I'll assume it's in group 1-9, but the logic will work for either of the other groups.

weigh [1-5] vs [6-9 and 27] (ie coins 1 thru 5 on one side, 6 thru 9 and 27 on the other. For this example, know #27 is ok, if the odd one is in the 19-27 group, we'd pick one of the good coins from another group to include instead)
after the 2nd weighing we learned whether to look for heavier or lighter group, so pick either 1-5 or 6-9 as having the odd coin based on heavy vs light
whichever group the odd one is in, weigh 2 coins vs 2 coins
for example for 1-5, weigh [1-2] vs [3-4] - if they balance its #5, if not pick the correct side based on heavier or lighter learned in weigh #2 and weigh them against each other
alternatively, if it's in 6-9, weigh [6-7] vs [8-9], pick the heavier or lighter pair based on weigh #2 and weigh them against each other.
This process should work regardless of which one it is, and whether it's lighter or heavier.

[Jkyle1980]

I think I've got it in 4 measurements:

Separate the coins into 3 stacks of 9 (A, B, C). Weigh stack A against B and then A against C. Take the stack with the different weight (note lighter or heavier) and break it into 3 stacks of 3 (D, E, F). Weigh stack D against E. If D and E are equal, then F is the odd stack. If D and E are not equal, the lighter or heavier (based on the A, B, C comparison) is the odd stack. You now have three coins (G, H, I). Weigh G and H. If G equals H, then I is the odd and is lighter or heavier (based on the A, B, C comparison). If G and H are not equal, then the lighter or heavier (based on the A, B, C comparison) is the odd coin.

[bonanova]

Jkyle1980's solution is correct, and much less verbose than what follows.

You can distinguish among 3**N cases in N weighings.
There are 54 possible cases in this puzzle [one of 27 coins is heavy or light].
So three weighings [27 cases] won't do it, but four [81 cases] can.

Spoiler for Here's a very slightly modified approach

Use Jkyle1980's groups of nine coins: A, B, C.

[1] A = B: C has a heavy or light coin [18 cases]
[2] A < B: A has a light coin or B has a heavy coin [18 cases]
[3] A > B: A has a heavy coin or B has a light coin [18 cases]

[1] Split C into groups of three coins: C1, C2, C3 and weigh C1 vs. C2.

C1 = C2: C3 has a heavy or light coin [6 cases] Name the C3 coins c3a, c3b, c3c.
c3a = c3b: if c3a </> c3c, then c3c is the heavy / light coin.
c3a < c3b: if c3a </= c3c, then c3a is light / c3b is heavy.
c3a > c3b: if c3a =/> c3c, then c3b is light / c3a is heavy.

C1 < C2: C1 has a light coin or C2 has a heavy coin [6 cases]
C1 = C3: [C2>C1=C3] C2 has a heavy coin.
Procedure 1:
Name the coins c2a, c2b, c2c.
c2a = c2b: c2c is heavy
c2a < c2b: c2b is heavy
c2a > c2b: c2a is heavy
C1 < C3: [C2>C1<C3] C1 has a light coin. Apply Procedure 1 to determine the light coin.
C1 > C3: [C3>C1>C2] Impossible.

C1 > C2: C1 has a heavy coin or C2 has a light coin [6 cases]
C1 = C3: [C1=C3>C2] C2 has a light coin. Apply Procedure 1 to determine the light coin.
C1 < C3: [C2<C1<C3] C1 Impossible.
C1 > C3: [C2<C1>C3] C1 has a heavy coin. Apply Procedure 1 to determine the heavy coin.

[2] Weigh A vs. C

A = C: [A=C<B] B has a heavy coin [9 cases]
Procedure 2:
Split the B coins into groups of three: B1, B2, B3
B1 = B2: B3 has a heavy coin. Apply procedure 1 to determine which.
B1 < B2: B2 has a heavy coin. Apply procedure 1 to determine which.
B1 > B2: B1 has a heavy coin. Apply procedure 1 to determine which.
A < C: [B>A<C] A has a light coin [9 cases] Apply Procedure 2 to determine which.
A > C: [B>A>C] Impossible

[3] Weigh A vs. C

A = C: [A=C>B] B has a heavy coin [9 cases] Apply Procedure 2 to determine which.
A < C: [B<A<C] Impossible
A > C: [B<A>C] A has a heavy coin [9 cases] Apply Procedure 2 to determine which.