Weighing in a Harder Way

[Guest]

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?

[Guest]

weigh 9 against 9. if equal the odd coin is in the last 9, and you have 18 normal coins.

   weigh 3 agianst 3. if equal the odd coin is in the last 3.

	   weigh 1 against 1. if equal, the last coin is odd.

	   if unequal, weigh a coin against a normal coin.

   if unequal, weigh 1 light and 1 heavy against 1 light 1 heavy.

	  if equal, one of the remaining two coins must be odd, weigh against a normal coin.

	  if unequal, you have one light and one heavy coin, weigh one of the coins against a normal coin.

now for the tricky part. if 9 against 9 is unequal, weigh 3 heavy and 3 light against 3 heavy and 3 light.

	 no matter the result, you have 3 heavy and 3 light left. weigh 1 light 1 heavy against 1 light 1 heavy.

	 again no matter the result, you have 1 heavy and 1 light left. weigh one coin against a normal coin.

[ujjagrawal]

Atmost 4 measurements are enough, for 27 coins, equation goes like this

For m numbers of coin, where m>= 3^n (maximize n).

n measurements if it known whether different coin is heavier or lighter than other.

n +1 , if if you don't know if different coin is heavier or lighter than other.

[bhramarraj]

Divide 27 coins in three groups of 9 coins named 9A, 9B, 9C. Name dissimilar coin as D.

CASE- I

Compare 9A and 9B. Say 9A = 9B. Then 9C contains D.

Compare 9A and 9C. Say 9A > 9C. Then D is the lighter coin.

Now we know 9C has D which is a lighter coin, so we divide 9C into three groups of 3 coins named 3C1, 3C2, 3C3 and compare 3C1 and 3C2. If equal we know 3C3 has lighter coin, If unequal we know that lighter group contains lighter coin. Now compare two coins of the lighter group. And we know the lighter coin. Same procedure is adopted when 9A < 9C, as we would be knowing that 9C contains D which then would be heavier coin.

CASE-2

Say 9A > 9B. Then we know that 9C does not contain D.

Now if 9A = 9C. Then we know 9B contains lighter coin D.

If 9A > 9C. Then we know 9A contains heavier coin D.

If 9A < 9C. Then we know 9A contains lighter coin D.

Then next two weighing will reveal the coin D.

Thus max. 4 weighing will be required to know the dissimilar coin and whether it is lighter or heavier.

[bhramarraj]

Sorry.... my solution at post no. 80 was not clear and with some errors. So as a penalty I am posting more clear solution... thanks

Divide 27 coins in 3 groups, each of 9 coins, say 9A, 9B, & 9C. W1: Compare 9A & 9B. Three possibilities are as under:

[a] 9A = 9B, OR 9A > 9B, OR [c] 9A < 9B. CASE [a]: W1: 9A = 9B, (counterfeit coin is in group 9C).

Divide 9C in 3 groups, say 3C1, 3C2, & 3C3. W2: Comparing 3C1 & 3C2, again there are three possibilities as under:

[a1] 3C1 = 3C2,

[a2] 3C1 > 3C2,

[a3] 3C1 < 3C2,

CASE [a1]:

W1: 9A = 9B, (counterfeit coin is in 9C).

W2: 3C1 = 3C2, (counterfeit coin is in group 3C3). Name three coins in 3C3 as 1C31, 1C32, & 1C33.

W3: Compare 1C31 & 1C32. Again there are three possibilities as under:

[a11]: 1C31 = 1C32,

[a12]: 1C31 > 1C32,

[a13]: 1C31 < 1C32.

CASE [a11]:

W1: 9A = 9B, (counterfeit coin is in group 9C).

W2: 3C1 = 3C2, (counterfeit coin is in group 3C3).

W3: 1C31 = 1C32, (1C33 is COUNTERFEIT COIN).

W4: Compare 1C31 v/s 1C33, to know whether 1C33 is LIGHTER or HEAVIER than the normal coin 1C31.

CASE [a12]:

W1: 9A = 9B,

W2: 3C1 = 3C2, (counterfeit coin is in group 3C3).

W3: 1C31 > 1C32, (Either 1C31 or 1C32 is counterfeit coin).

W4: Compare 1C31 v/s 1C33,

If 1C31 = 1C33, then 1C32 is COUNTERFEIT COIN, and is LIGHTER.

If 1C31 > 1C33, then 1C31 is COUNTERFEIT COIN, and is HEAVIER.

If 1C31 < 1C33, then 1C31 is COUNTERFEIT COIN, and is LIGHTER.

CASE [a13]: Similar procedure as described in CASE [a12].

CASE [a2]:

W1: 9A = 9B, (counterfeit coin is in group 9C).

W2: 3C1 > 3C2, (counterfeit coin is either in group 3C1 OR in 3C2.)

W3: Compare 3C1 v/s 3C3, there are three possible results:

[a21]: 3C1 = 3C3,

[a22]: 3C1 > 3C3,

[a23]: 3C1 < 3C3,

CASE [a21]:

W1: 9A = 9B, (counterfeit coin is in group 9C).

W2: 3C1 > 3C2, (counterfeit coin is either in group 3C1 OR in 3C2.)

W3: 3C1 = 3C3, (counterfeit coin is in the group 3C2 and is LIGHTER).

Name three coins in 3C2 as 1C21, 1C22, & 1C23.

W4: Comparing 1C21 & 1C22, three possibilities are as under:

If 1C21 = 1C22, then 1C23 is COUNTERFEIT COIN, and is LIGHTER.

If 1C21 > 1C22, then 1C22 is COUNTERFEIT COIN, and is LIGHTER.

If 1C21 < 1C22, then 1C21 is COUNTERFEIT COIN, and is LIGHTER.

CASE [a22]:

W1: 9A = 9B, (counterfeit coin is in group 9C).

W2: 3C1 > 3C2, (counterfeit coin is either in group 3C1 OR 3C2.)

W3: 3C1 > 3C3, (counterfeit coin is in the group 3C1 and is HEAVIER). Name three coins in 3C1 as 1C11, 1C12, & 1C13.

W4: Comparing 1C11 & 1C12, three possibilities are as under:

If 1C11 = 1C12, then 1C13 is COUNTERFEIT COIN, and is HEAVIER.

If 1C11 > 1C12, then 1C11 is COUNTERFEIT COIN, and is HEAVIER.

If 1C11 < 1C12, then 1C12 is COUNTERFEIT COIN, and is HEAVIER.

CASE [a23]: This can also be solved similarly as above CASE [a22].

CASE [a3] can also be solved with the same procedure as in CASE [a2].

CASE :

W1: 9A > 9B, (counterfeit coin is either in group 9A or in 9B).

W2: Compare 9A v/s 9C, three possibilities are as under:

[b1] 9A = 9C, (counterfeit coin is in 9B and is LIGHTER)

[b2] 9A > 9C, (counterfeit coin is in 9A and is HEAVIER)

[b3] 9A < 9C, (counterfeit coin is in 9A and is LIGHTER)

CASE [b1]:

W1: 9A > 9B,

W2: 9A = 9C, (counterfeit coin is in 9B and is LIGHTER) Divide 9B in three groups 3B1, 3B2, & 3B3. W3: Compare 3B1 & 3B2,. Again there are three possibilities as under:

[b11]: 3B1 = 3B2, (counterfeit coin is in 3B3 and is LIGHTER).

[b12]: 3B1 > 3B2, (counterfeit coin is in 3B2 and is LIGHTER).

[b13]: 3B1 < 3B2, (counterfeit coin is in 3B1 and is LIGHTER).

CASE [b11]:

W1: 9A > 9B, (counterfeit coin is either in group 9A or in 9B).

W2: 9A = 9C, (counterfeit coin is in 9B and is LIGHTER)

W3: 3B1 = 3B2, (counterfeit coin is in 3B3 and is LIGHTER).

Name three coins of 3B3 as 1B31, 1B32, 1B33.

W4: Compare 1B31 v/s 1B32,

If 1B31 = 1B32, then 1B33 is COUNTERFEIT COIN, and is LIGHTER.

If 1B31 > 1B32, then 1B32 is COUNTERFEIT COIN, and is LIGHTER.

If 1B31 < 1B32, then 1B31 is COUNTERFEIT COIN, and is LIGHTER.

CASE [b12]:

W1: 9A > 9B, (counterfeit coin is either in group 9A or in 9B).

W2: 9A = 9C, (counterfeit coin is LIGHTER and is in group 9B).

W3: 3B1 > 3B2, (counterfeit coin is in 3B2 and is LIGHTER).

Name three coins of 3B2 as 1B21, 1B22, 1B23.

W4: Compare 1B21 & 1B22,

If 1B21 = 1B22, then 1B23 is COUNTERFEIT COIN and LIGHTER.

If 1B21 > 1B22, then 1B22 is COUNTERFEIT COIN and LIGHTER.

If 1B21 < 1B22, then 1B21 is COUNTERFEIT COIN and LIGHTER.

CASE [b13] may be solved as above CASE [b12].

CASE [b2]:

W1: 9A > 9B, (counterfeit coin is either in group 9A or in 9B).

W2: 9A > 9C, (counterfeit coin is in 9A and is HEAVIER)

Divide 9A in three groups as 3A1, 3A2, 3A3.

W3: Compare 3A1 & 3A2, there are three possibilities as under:

[b21] 3A1 = 3A2, (3A3 contains counterfeit coin and is HEAVIER).

[b22] 3A1 > 3A2, (3A1 contains counterfeit coin and is HEAVIER).

[b23] 3A1 < 3A2, (3A2 contains counterfeit coin and is HEAVIER).

CASE [b21]:

W1: 9A > 9B, (counterfeit coin is either in group 9A or in 9B).

W2: 9A > 9C, (counterfeit coin is in 9A and is HEAVIER)

W3: 3A1 = 3A2, (3A3 contains counterfeit coin and is HEAVIER).

Name three coins of 3A3 as 1A31, 1A32, 1A33.

W4: Compare 1A31 & 1A32,

If 1A31 = 1A32, then 1A33 is the COUNTERFEIT COIN and is HEAVIER.

If 1A31 > 1A32, then 1A31 is the COUNTERFEIT COIN and is HEAVIER.

If 1A31 < 1A32, then 1A32 is the COUNTERFEIT COIN and is HEAVIER.

CASE [b22]:

W1: 9A > 9B, (counterfeit coin is either in group 9A or in 9B).

W2: 9A > 9C, (counterfeit coin is in 9A and is HEAVIER)

W3: 3A1 > 3A2, (3A1 contains counterfeit coin and is HEAVIER).

Name three coins of 3A1 as 1A11, 1A12, 1A13.

W4: Compare 1A11 & 1A12,

If 1A11 = 1A12, then 1A13 is the COUNTERFEIT COIN and is HEAVIER.

If 1A11 > 1A12, then 1A11 is the COUNTERFEIT COIN and is HEAVIER.

If 1A11 < 1A12, then 1A12 is the COUNTERFEIT COIN and is HEAVIER.

Similarly CASE [b23] may be solved.

CASE [c] may be solved similarly as CASE .

THUS WE SEE 4 WEIGHING ARE REQUIRED TO KNOW THE COUNTERFEIT COIN OUT OF 27 COINS.

Edited June 5, 2012 by bhramarraj

[difabor]

It should take minimum 4 ways.

The exact dependency is: W = log₃(2*N + 1) (roughed to closest integer not less then it)

I can proove this, but in Russion

[difabor]

Well, if somebody is interested, I'll try to prove it in English. Let me know.

[themzs]

I do not believe the answer is correct and believe this is quicker (4 turns). Separate the coins into 3 stacks of 9 (A, B, C). Weigh stack A against B (Turn 1). If A & B are equal you know the heavier or lighter coin is in C and I will skip figuring the different coin for C, because A being more or less than B will take more turns. Note which way the scale moved in reference to A (either up or down). Seperate A and B into 3 stacks with 3 coins each A1, A2, A3 and B1, B2 and B3. Remove stacks A3 and B3 from the scale. Move stacks A2 and B2 to opposite sides of the scale and measure (Turn 2). If the Scale moves the same way you know the different coin is in stack A1 or B1. If the scale moves the opposite way you know the different coin is in A2 or B2. If the scale is even, you know the different coin is in A3 or B3. In 2 turns you have narrowed it down to 6 coins. Regardless of which item you can follow the same steps for turn 3. Say the scale moved the same way as turn 1 so the coin is in stack A1 or B1. Divide stacks into 3 coins A11, A12, A13 and B11, B12, B13. Remove coins A13 and B13. Move coins A12 an B12 to opposite side of the scale (Turn 3). If the scale moves the same way you know the different coin is A11 or B11. If the scale moves a different direction you know the coin is A12 or B12. If the scale is even you know the coin is A13 or B13. Say the scale moved the opposite direction of turn 2 in turn 3. Then you know A12 is heavier or B12 is lighter. Weigh either of these coins against any other coin and by turn 4 you have not only determined which coin is different, but wether it is heavier or lighter.

Z

Edited November 26, 2012 by themzs

[jmaurier]

minimum 3 max 6 (If you are splitting into 3 piles each time).

incase you don't know: "!=" means "not equal"

BEST CASE = 3 tries

1)if A=B then the coin is in C. Split C into three piles (again A,B,C)

2)if A=B then the coin is in C again. Split C into the three last coins.

3)if A=B then C is the coin.

WORST CASE = 6 tries

1)A!=B (piles of 9)

2)Now test A and C

if A=C then split B into ABC

if A!=C then split A into ABC

3)A!=B (piles of 3)

4)Now test A and C

if A=C then split B into ABC

if A!=C then split A into ABC

5)A!=B (last 3 coins)

6)Now test A and C

if A=C then B is the coin

if A!=C then A is the coin