Russian Coins
Source: 2010 Euler math Olympiad in Russia to Eighth graders. The author of the problem is Alexander Shapovalov
Problem: Among 100 coins exactly 4 are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin. How would we find at least one genuine coin using two weighings on a balance scale?
By the way, ten eighth grade students in Russia solved this problem during the competition. :P
Best of Luck! I am sure solving this problem will make you happy :)
Update(26-06-10)
Solution: Posted by Nikhil in comments!
Problem: Among 100 coins exactly 4 are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin. How would we find at least one genuine coin using two weighings on a balance scale?
By the way, ten eighth grade students in Russia solved this problem during the competition. :P
Best of Luck! I am sure solving this problem will make you happy :)
Update(26-06-10)
Solution: Posted by Nikhil in comments!
Notation :: Let G indicate "Genuine" coin, and F indicate "Fake" coin.
ReplyDeletepick 6 coins, and place 3 coins in each pan;
CASE 1::
If pans do not balance each other, then it means that the heavier pan has more genuine coins than the lighter pan.And the heavier pan must have at least 2 Genuine Coins ( since there are only 4 Fake coins).
So, for the next weighing we pick 2 coins from the heavier pan ( at least one of these must be Genuine). And return the heaviest(hence Genuine) of these two coins ( if both coins are of equal weight then it means both are genuine , hence we can return anything).
CASE 2 ::
if pans balance each other then we have following 3 subcases :
GGG GGG
GGF GGF
GFF GFF
Now, we pick 2 coins (say, from left pan). If they balance each other, then return the remaining(3rd coin) from the left pan. If they don't balance each other then return the heavier one.
sorry, solution for case2 is wrong.
ReplyDeleteit will return Fake coin in GGF case.
:( still no solution :(
ReplyDeleteDivide the coins into three sets of 33,33 and 34 coins
ReplyDeleteFor the first weigh, use the two sets of 33 coins.
Assume, one set is heavier. Then that set can have atmost one fake. So take any two coins from this set. If equal, pick any as the real one and otherwise the heavier one is real.
Now assume the two sets of 33 coins weigh equal. We have 3 possibilities. These sets have either 0,1,2 fake coins each.
Pick one coin(C) from one set of the 33 coins(call this set A) and add it into the other set of 33 coins(call this B), and weigh these 34 coins with the original set of 34.
Case 1 - Equal : This is only possible if A and B had 1 fake coin each and C is also fake, in which case every coin in A is real.
Case 2 - B+C is heavier : Possible if A and B have either 0 or 1 fake each. In either case, C must be real.
Case 3 - B+C is lighter : Possible only if A and B have 2 fakes each, in which case every coin from the original set of 34 is real.
Hence, we can always find atleast one real coin.
Consider A, B, original34 has one fake coin each.
Delete1) C= genuine; Then it belongs to case1- but not all coins in A are genuine.
2) C= fake; then it belongs case3- but A and B hav only 1 fake coin.
correct me if i am wrong.
@Nikhil.. Seems correct.. Thanx a lot for the correct solution :)
ReplyDeleteWhat about this:
ReplyDeletePick 5 coins
Weighing1: Weigh 2 on either side and keep 1 aside.
i) If balanced, then two cases
a- FF = FF; G
b- GG = GG; F/G
Weighing2: Replace the fifth coin in any of the pan and observe which side turns heavier(a)/lighter(b)/nochange(b).
ii) If not balanced,
a: FF<GG; F/G
b: FF<FG; F/G
c: FG<GG; F/G
Weighing2: Weigh the heavier side, heavier among them will be genuine coin.
@gyani.. not a correct solution..
ReplyDeleteFor the correct solution, refer Nikhil's comment
Extension: What is the maximum number of genuine coins that can be found in two weighings?
ReplyDelete