Coin Weighing Problem
Yet another coin problem. Read this today in "Heard from the Street". Found it interesting.
Problem: You are given a set of scales and 90 coins. The scales are of the old balance variety, that is a small dish hangs from each end of the rod that is balanced in the middle. You must pay 100$ every time you use the scales.
The 90 coins appear to be identical. In fact, 89 of them are identical and one is of a different weight. Your task is to identify the unusual coin and to discard it while minimizing the maximum possible cost of weighing. What is your algorithm to complete this task?
Note that the unusual coin may be heavier than the others or it may be lighter. You are asked to both identify it and determine whether it is heavy or light.
Previously asked coin puzzles:
Another Coin Problem
Coins Puzzle
Consecutive Heads
Five Thieves and Bounty
Update (18/02/10): Solution posted by me in comments!! A non-optimal but simpler solution posted by Bhanu (M.Tech Student, CSE, IITB). Another solution posted by Suman in comments!! Thanx
Problem: You are given a set of scales and 90 coins. The scales are of the old balance variety, that is a small dish hangs from each end of the rod that is balanced in the middle. You must pay 100$ every time you use the scales.
The 90 coins appear to be identical. In fact, 89 of them are identical and one is of a different weight. Your task is to identify the unusual coin and to discard it while minimizing the maximum possible cost of weighing. What is your algorithm to complete this task?
Note that the unusual coin may be heavier than the others or it may be lighter. You are asked to both identify it and determine whether it is heavy or light.
Previously asked coin puzzles:
Another Coin Problem
Coins Puzzle
Consecutive Heads
Five Thieves and Bounty
Update (18/02/10): Solution posted by me in comments!! A non-optimal but simpler solution posted by Bhanu (M.Tech Student, CSE, IITB). Another solution posted by Suman in comments!! Thanx
Divide those 90 coins into 3 groups each containing 30 coins
ReplyDeleteLet us call them as A,B,C
Compare A&B, If their weights are different, the coin we need is in one of these two groups.If A&B weigh same, C is the required group.
After finding the required group we need to find whether the coin of interest weighs more or less than the normal coin.I will explain this with an example
A>B
compare A&C
if A>C then the required coin weighs more and is in A
else if A==c
required coin weighs less and is in B
Now we have 30 coins out of which one coin is different(let us say it is less)
btw till now we spent 200$
Next divide these 30 into three groups of 10 each.As we know the characteristic of the coin, one comparison is sufficient to get the required 10.so 200$+100$
Now we have 10 coins
we can divide these coins in groups of 3,3,4 or 4,4,2.In either case the we need 2 comparisons in the best case and three in the worst case.
Hence the minimum of 5 and a maximum of 6 comparisons are required and hence min=500$ &max=600$
@Bhanu. Nice. Thanx.
ReplyDeleteLets try and improve this to a maximum 500$.
Divide the 90 coins into group of 3.
ReplyDelete1st comparison:
Say A,B,C.
If A>B, lets mark A as 30H (possibility of a heavier coin in this group) and B as 30L (possibility of a lighter coin in this group)and C as 30E( all equal weights coin).
2nd comparison:(for 30L, 30H case)
Now we weight like this:
10L 20E | 20L 10H
if left hand side is heavier that means the faulty coin is in 20L group.
if both side are equal the faulty coin is in 20H.
else
we have 10L,10H group from which we have to identify the faulty coin.
3rd comparison:(for 10L,10H case)
Now we weight like this:
3L 7E | 7L 3H
So following the above logic we can have 3 different outcomes:
--> faulty in 7L
--> faulty in 7H
--> faulty in 3H,3L
4th comparsion: ( for 3L,3H)
1L 2E | 1H 2L
3 outcomes:
--> faulty in 2L
--> faulty in 2H
-->faulty in 1L,1H
The faulty coin can be determined in one more comparsion. So total 5 comparison.
Now lets take the cases that we have not included so far.
Say the faulty is in 7L:(after 3 comparison)
We compare 3L against 3L and
if the mismatch then take 2 from the lighter group and weight them, hence detection in total 5 comparison.
else the remaining coin is lighter.
Same logic for 7H case
So total 5 comparsion
Say faulty is in 20L ( after 2nd comparison)
we comapre 7 against against and follow the previous step.
Total 5 comparison.
Same for 20H case.
Now say A=B and C contains the biased coin.(After 1 comparison)
we group it in 10-10-10. and follow the same logic
This problem is best viewed in a tree diagram to analyze all the cases.
Also to generalize, this grouping can be done in bottom up manner.
From 4H,4L we can determine the faulty coin in 2 comparison, so we grow up from here.
4H,4L,
12H,12L,
36H,36L ( from total of 108 coins)
I think the general formula is n=
ReplyDeletelog_3{2N+3} where n are the min no of comparisons req and N total no of coins.
We can prove this by proving two lemmas:
First divide the coins into three equal parts. compare two parts. If unequal then we can label each of these coins as L or H (in the sense that a L coin, if not a normal coin will have to be a lighter coin and vice versa).
So lemma 1: If all N coins are labelled (i.e L or H) then we can find the unequal coin in log_3{N}.
Also if the first two parts are equal then the last part will contain the unequal coin. But now we have coins which we know are normal.
So lemma 2: If there are N coins with an additional coin which is known to be normal then from the N coins we can find the unequal coin in log_3{2N+1) comparisons.
(To see this we observe that for n=2 we can do a maximum of 4 coins. i.e. for n=2 N=4. Now for finding for n=3, let N=N1+N2.All in N2 are labelled after the first comparisons. If the unequal coin is in N2 => N2=3^2. Now N1=4 so N=4+3^2=1+3+9. So by induction we see that N=(3^n - 1)/2 => n=log_3{2N+1}.)
Now we dont have a normal coin. So divide N into three equal parts. Compare two parts, so we get labels for 2N/3. Now for n-1 comparisons we can do it for 3^(n-1) coins. But 2N/3 is even so these 2N/3=3^(n-1)-1.
and for the first part we can do it for (3^(n-1)-1)/2 coins by lemma 2. so adding we get N=(3^n -3)/2 which is n=log_3{2N+3)
Disclaimer: Difficult solution.
ReplyDeleteSolution:
Claim 1: 10 coins with 1 faulty and no information lighter or heavier can be done in 3 steps.
Add two good coins to the set. So, you have 12 coins out of which one is faulty. Finding that coin can be done in 3 steps (standard 12 marble puzzle)
Claim 2: 2 sets S1 and S2 of 10 coins each with one faulty coin, either S1 with heavier coin or S2 with lighter coin can be solved in 3 steps.
Divide S1 into S11 (3coins lets say 3h coins as 3 coins potentially heavier), S12 (3h coins) and S13 (4h coins). Similarly divide S2 into S21 (3l coins), S22 (3l coins) and S23 (4l coins).
Compare (S11+S23) and (S21+S13).
If equal, left is to check from S12 (3h coins) and S22 (3l coins) in 2 steps. Similarly now compare (1h from S21 + 1l from S22) with (1h from S21 + 1l from S22). If equal, its all upto 1h from S12 and 1l from S22. This can be done in 1 step. If not equal, we have 1 potentially heavy coin and 1 potentially lighter coin. This can be done in 1 step. So, we solve the part in 3 steps.
If not equal, similarly again we have 1 potential heavy set of 3 coins and 1 potential light set of 4 coins. This can be done similarly in 2 steps.
So, the two problems can be solved in 3 steps.
Now the solution:
Divide the set of 90 coins into 3 sets of 30 coins each. Weigh two groups of 30 coins against each other.
If equal, divide the rest 30 into 3 groups of 10 each. Weigh two groups here to reduce the problem either to claim1 or claim2. So, the problem is solved in 5 steps.
If not equal, Divide 30 coins of potentially heavy set into 10, 10, 10 coins and same with potentially light set.
Compare (1 potentially heavy set+one potentially light set) with
(1 potentially heavy set+one potentially light set). If equal, we reduce our problem to claim2 directly. If one side is heavier, the problem reduces to finding a heavy coin in set of 10 or a light coin in set of 10 which is again claim2. So, this can also be done in 5 steps.
So, the problem can be solved in 5 steps. 500$ only!! :)
Phew!! Very difficult problem :)
But nice and simple (though not optimal) approach by Bhanu.
@sid.. before going into details of your analysis..
ReplyDeleteDo you realise that using log_3{N} for any counting even if the set is reduced by 1/3 every time is wrong. As we have to take ceiling of N/3 every time.
.. (Suman) solution seems to be correct. :) Thanx