Ok … you have seven coins, two are counterfeit and you have a balance scale.?
What is the least number of weighings to find the counterfeit ones and is there an algebraic solution?
Sorry, you don’t know whether the counterfeits are lighter or heavier.
Related posts:
- you are given 5 coins and a balance scale. The coins look alike but one is counterfeit and either heavier ….? you are given 5 coins and a balance scale. The coins look alike but one is counterfeit and either heavier or lighter than the others. Find the counterfeit coin using...
- You are given twelve gold coins and a simple balance scale. One of the coins is counterfeit.? You are given twelve gold coins and a simple balance scale. One of the coins is counterfeit, but it is not known whether it is lighter or heavier than the...
- If you have 8 coins and a balance scale. The coins look alike, but 1 is counnterfeit and lighter than the othe If you have 8 coins and a balance scale. The coins look alike, but 1 is counnterfeit and lighter than the other 7. Which is the counterfeit coin using 2...
- I hav 9 gold coins that r identical exept for 1(counterfeit), how do I find it w 2 tries on a balanc scale? I have 9 gold coins that are identical in appearance. However, one is counterfeit and weighs slightly less. Using a balance scale, how can I find the counterfeit coin in...
- I hav 9 gold coins that r identical exept for 1(counterfeit), how do I find it w 2 tries on a balanc scale? I have 9 gold coins that are identical in appearance. However, one is counterfeit and weighs slightly less. Using a balance scale, how can I find the counterfeit coin in...
Consider this problem from the point of view of the information theory. The amount of unknown information is equal to log(42) (logarithm of all possible combinations to have 2 fake coins from a set of 7 coins, taking into account that fake coins can be both heavier or lighter). According to the Shannon formula, the average amount of information, which we extract from a test is equal to the sum of -p_i * log p_i, where p_i is the probability of i-th outcome. This sum is maximal when probabilities of different outcomes are equal. In case of 3 possible results of a weighing, the maximal amount of information extracted from a single weighing is equal to I_{max} = log 3. If we can arrange weighings in an optimal way, then after n weighing we will get the amount of information equal to n*log(3). We can find fake coins after n weighings only when n*log(3) > 42, or 3^n>42, or n>3.
We see that the least number of weighings is greater than 3. However, this does not prove that 4 weighings will be sufficient, because the above reasoning refers the maximal amouint of information, which can be extracted only if three differents outcomes of each single weighing have equal probabilities. Such weighings are not possible to make in practice, and after n weighings we always get less information than n*log(3). In principle, we can get 3^4= 81 different results of weighings, but some of these results will correspond to the same choices of 2 fake coins. And there is no garantee, that we will cover all 42 possibilities.
Thus, a purely algebraic approach solves only a part of the problem. To prove that the least number of weighings is 4, we need to describe the process explicitely.
Take two coins numbered as "1" and "2" and weigh them.
(A) If coins "1" and "2" have different weights, say "1"> "2", then we weigh coin "3" versus coin "4" and coin "5" versus coin "6". We have three weighings at this point and one weighing is remaining. There are two possible outcomes:
(1) "3"= "4" and "5"= "6". This means that coins "3", "4", "5", and "6" are real, and coin "7" is fake. Weighing "7" versus one of the real coins, say "3", we determine whether fake coins are lighter or heavier. This allows to spot the fake coin from the couple "1", "2".
(2) Coins in one of the pairs "3"-"4" or "5" -"6" have different weights, say "3">"4". Then coins "5" to "7" are real. Take one of these coins and weigh it versus coin "3". This will tell us, which of the coins "3" and "4" is fake. We also determine whether fake coins are lighter or heavier, and spot the fake coin from the couple "1", "2".
(B) If coins "1" and "2" have the same weights, then they are both real or both fake. Then we weigh "1"+"2" versus "3"+"4".
We have two weighings at this point and two weighings are remaining.
(1) If "1"+"2"="3"+"4", then they are all real. Then we weigh "1" versus "5", and "1" versus "6", which allows to spot two fake coins from three remaining coins.
(2) If "1"+"2" are not equal to "3"+"4", then we weigh "3" versus "4". This is the third weighing and one weighing is remaining.
(2a) If "3"= "4" , then either "1" and "2" are fake, or "3" and "4" are fake, while "5", "6", "7" are real. Take, say "7" and weigh it versus "1". This allows to spot the fake couple.
(2b) If "3" is not equal to "4", then one of them is fake, while "1" and "2" are real. From the results of the previous measurement "1"+"2" versus "3"+"4", we know whether the fake coins are heavier or lighter, and hence we know which of "3", "4" is fake. To spot the remaing fake coin we need only one weighing. Put "5" versus "6". If they are equal, then "7" is fake. If "6" and "7" are not equal, then we know which of them is fake.
As it has been described, fake coins can be found from 4 weighings.We have also proved that 3 weighings is not sufficient. Hence, 4 is the least number.
First, find out how many possibilities there are. Do you know if the fake ones are lighter or heavier?
There are 6+5+4+3+2+1 possibilities for which coins are fake, so if you know if the fake one is heavier or lighter, there are 21 possibilities. If you don’t know, then there are 21 * 2 = 42 possbilities.
Then you take the smallest power of 3 that is bigger than the number of possibilities, and the power is the number of weighings you need. So for 21 possibilites, it would be 3 because 3^3=27. For 42 it would be 4. 3^4=81
This is because each weighing has 3 possible outcomes: Side A is heavier; Side B is heavier; or they balance. Each time you add another weighing, you multiply the number of possible outcomes by 3.
If they are all the same weight then you are out of luck. If the counterfeited ones weight differently, then you can find which ones are fake by first weighting 3 coins, vs 3 coins.