There are 75 coins supposedly of same weight but you know thatone coin is fake a

Question

There are 75 coins supposedly of same weight but you know thatone coin is fake and weighs less than the rest. You have a balancescale and you can put atmost 15 coins on each side of the scale ata time and it will tell you if the two sides weigh the same orwhich side is lighter if they dont weigh the same. Write anefficient algorithm for finding the fake coin. How many weighingswill you do in the worst case? Please explain in detail. Thanks. Sheryl. There are 75 coins supposedly of same weight but you know thatone coin is fake and weighs less than the rest. You have a balancescale and you can put atmost 15 coins on each side of the scale ata time and it will tell you if the two sides weigh the same orwhich side is lighter if they dont weigh the same. Write anefficient algorithm for finding the fake coin. How many weighingswill you do in the worst case? Please explain in detail. Thanks. Sheryl.

Explanation / Answer

Algorithm: 1) If number of coins are less than or equal to 30, make it intogroups of equal number of coins and weigh them,     find the side which weigh less and numCoins= number of coins on the side which weighs less,repeat step1    This way finally you will get groups of 1 coins...thatwill be the fake coin 2) If number of coins are more than 30, make it groups of 15 coinsand the last one may contain less than 15 coins (if number of coinsis not a multiple of 15), 2.a) Now select two groups containing 15 coins each and weigh them,if u find any side which weigh less, then repeatstep12.b) If two sides weight the same, thenselect any one group and compare that with the other groups. 2.c) If the last group has less than 15 coins, then mix the lastgroup with the current group and goto Step1 Solving given example using the abovealgorithm: There are 75 coins.....75>30.... So by step2....we will divide it into 5 groups of 15 coins each(here the last group also contains 15 coins since 75 is amultiple of 15) now select two groups and weigh them.... In the worst case we will find the fake coin after we compare allthe groups of 15 coins each. SO there will be four comparisons with 15 coins each.... Now we got the group containing the fake coin Now by step1..divide it into groups of 7,7,1 now weight grousps with 7 coins... in worst case one of the groups have the fake coin.. again by step 1 we will get groups 3,3,1 in worst case one of the groups have the fake coin.. again by step1 we will get groups of 1,1,1 weigh groups containing 1 coin each....n we will find the fakecoin There are a total of : 4 + 1 + 1 + 1                         = 7 comparisons in the worst case i.e.. There are 5 groups...15, 15, 15, 15, 15 1st comparison: 15---- 15 , select one group and compare it withthe third group 2nd comparison: 15---- 15 , select one group and compare it withthe fourth group 3rd comparison: 15---- 15 , select one group and compare it withthe fifth group 4th comparison: 15---- 15 , select one group and divide it into7,7,1 5th comparison: 7---- 7 , select one group and divide it into3,3,1 6th comparison: 3---- 3 , select one group and divide it into1,1,1 7th comparison: 1---- 1 , if they weight differnt, the fake one isthe one which weigh less...else the third one is the fake coin

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.