tag:blogger.com,1999:blog-4115025577315673827.post3139898643698267418..comments2020-05-20T14:21:54.596+05:30Comments on CSE Blog - quant, math, computer science puzzles: Coin Weighing ProblemPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-4115025577315673827.post-76633337635297873872010-02-18T11:32:18.019+05:302010-02-18T11:32:18.019+05:30@sid.. before going into details of your analysis....@sid.. before going into details of your analysis..<br /><br />Do 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.<br /><br />.. (Suman) solution seems to be correct. :) ThanxPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-19645969062300326302010-02-18T11:24:44.640+05:302010-02-18T11:24:44.640+05:30Disclaimer: Difficult solution.
Solution:
Claim ...Disclaimer: Difficult solution.<br /><br />Solution:<br /><br />Claim 1: 10 coins with 1 faulty and no information lighter or heavier can be done in 3 steps.<br /><br />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 (<a href="http://en.wikipedia.org/wiki/Balance_puzzle#The_twelve-coin_problem" rel="nofollow">standard 12 marble puzzle</a>)<br /><br />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.<br /><br />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). <br /><br />Compare (S11+S23) and (S21+S13).<br /><br />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.<br /><br />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.<br /><br />So, the two problems can be solved in 3 steps.<br /><br />Now the solution:<br />Divide the set of 90 coins into 3 sets of 30 coins each. Weigh two groups of 30 coins against each other. <br /><br />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.<br /><br />If not equal, Divide 30 coins of potentially heavy set into 10, 10, 10 coins and same with potentially light set.<br /><br />Compare (1 potentially heavy set+one potentially light set) with <br />(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.<br /><br />So, the problem can be solved in 5 steps. 500$ only!! :)<br /><br />Phew!! Very difficult problem :)<br />But nice and simple (though not optimal) approach by Bhanu.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-61646151907088687442010-02-17T18:49:02.208+05:302010-02-17T18:49:02.208+05:30I think the general formula is n=
log_3{2N+3} wher...I think the general formula is n=<br />log_3{2N+3} where n are the min no of comparisons req and N total no of coins. <br /><br />We can prove this by proving two lemmas:<br /><br />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). <br /><br />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}.<br /><br />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.<br /><br />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. <br />(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}.)<br /><br />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.<br />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)sidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-81556446953133746062010-02-17T11:20:48.971+05:302010-02-17T11:20:48.971+05:30Divide the 90 coins into group of 3.
1st compari...Divide the 90 coins into group of 3. <br /><br />1st comparison:<br /><br />Say A,B,C.<br />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).<br /><br />2nd comparison:(for 30L, 30H case)<br /><br />Now we weight like this:<br />10L 20E | 20L 10H <br />if left hand side is heavier that means the faulty coin is in 20L group.<br />if both side are equal the faulty coin is in 20H.<br />else<br />we have 10L,10H group from which we have to identify the faulty coin.<br /><br />3rd comparison:(for 10L,10H case)<br /><br />Now we weight like this:<br />3L 7E | 7L 3H<br />So following the above logic we can have 3 different outcomes:<br />--> faulty in 7L<br />--> faulty in 7H<br />--> faulty in 3H,3L<br /><br />4th comparsion: ( for 3L,3H)<br /><br />1L 2E | 1H 2L<br /><br />3 outcomes:<br />--> faulty in 2L<br />--> faulty in 2H<br />-->faulty in 1L,1H<br /><br />The faulty coin can be determined in one more comparsion. So total 5 comparison.<br /><br />Now lets take the cases that we have not included so far.<br /><br />Say the faulty is in 7L:(after 3 comparison)<br />We compare 3L against 3L and <br />if the mismatch then take 2 from the lighter group and weight them, hence detection in total 5 comparison.<br />else the remaining coin is lighter.<br />Same logic for 7H case<br />So total 5 comparsion<br /><br />Say faulty is in 20L ( after 2nd comparison)<br />we comapre 7 against against and follow the previous step.<br /><br />Total 5 comparison.<br /><br />Same for 20H case.<br /><br />Now say A=B and C contains the biased coin.(After 1 comparison)<br />we group it in 10-10-10. and follow the same logic<br /><br />This problem is best viewed in a tree diagram to analyze all the cases.<br /><br /><br />Also to generalize, this grouping can be done in bottom up manner.<br />From 4H,4L we can determine the faulty coin in 2 comparison, so we grow up from here.<br />4H,4L,<br />12H,12L,<br />36H,36L ( from total of 108 coins)SKBhttps://www.blogger.com/profile/00452713314235089901noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-67290465817657739492010-02-16T19:22:38.181+05:302010-02-16T19:22:38.181+05:30@Bhanu. Nice. Thanx.
Lets try and improve this to...@Bhanu. Nice. Thanx.<br /><br />Lets try and improve this to a maximum 500$.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-23765286499389935292010-02-16T15:53:58.791+05:302010-02-16T15:53:58.791+05:30Divide those 90 coins into 3 groups each containin...Divide those 90 coins into 3 groups each containing 30 coins<br />Let us call them as A,B,C<br /><br />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.<br /><br />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<br /><br />A>B<br />compare A&C <br />if A>C then the required coin weighs more and is in A<br />else if A==c<br />required coin weighs less and is in B <br /><br />Now we have 30 coins out of which one coin is different(let us say it is less)<br /><br />btw till now we spent 200$<br /><br />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$<br /><br />Now we have 10 coins<br />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.<br /><br />Hence the minimum of 5 and a maximum of 6 comparisons are required and hence min=500$ &max=600$Bhanu prakashhttps://www.blogger.com/profile/09639032761703842062noreply@blogger.com