How many weighings of a balance scale are needed to find a lighter counterfeit c
ID: 2902320 • Letter: H
Question
How many weighings of a balance scale are needed to find a lighter counterfeit coin among four coins? Which one of the following is the best algorithm to find the lighter coin?
At least 2 weighings are needed. We first put two coins in each pan. If the scale balances, we know the remaining coin is the counterfeit. If the scale does not balance, we compare the two coins that are lighter, and the lighter one is the counterfeit. At least 3 weighings are needed. We first compare the first two coins. If one is lighter, we compare it with the other two coins, and the lighter one of these is the counterfeit. At least 2 weighings are needed. We first compare the first two coins. If one is lighter, it is the counterfeit. If they balance, then we compare the other two coins, and the lighter one of these is the counterfeit. At least 6 weighings are needed. We compare each coin with every other coin, and the lightest one is the counterfeit. At least 3 weighings are needed. We compare one coin with every other coin, and the lighter one is the counterfeit.Explanation / Answer
A.Divide the pile of coins into two equal piles and weigh them against each other. The heavier/lighter pile contains the counterfeit coin. If the number of coins is odd remove one coin. If the weighing is equal the removed coin is the counterfeit, otherwise it can be discarded from the search.
B. Repeat step A with the heavier/lighter pile.
This will find the suspect coin in n steps where C/2^n < 2 and C is the number of coins. For four coins 4/2^2 =1 so 2 steps are needed
At least 2 weighings are needed. We first compare the first two coins. If one is lighter, it is the counterfeit. If they balance, then we compare the other two coins, and the lighter one of these is the counterfeit.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.