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!

Comments

  1. Anonymous5:29 PM, June 24, 2010

    Notation :: Let G indicate "Genuine" coin, and F indicate "Fake" coin.

    pick 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.

    ReplyDelete
  2. Anonymous5:49 PM, June 24, 2010

    sorry, solution for case2 is wrong.
    it will return Fake coin in GGF case.

    ReplyDelete
  3. Pratik Poddar7:09 PM, June 24, 2010

    :( still no solution :(

    ReplyDelete
  4. Nikhil12:05 AM, June 25, 2010

    Divide the coins into three sets of 33,33 and 34 coins
    For 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.

    ReplyDelete
    Replies
    1. teja2:22 AM, September 07, 2012

      Consider A, B, original34 has one fake coin each.

      1) 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.

      Delete
  5. Pratik Poddar12:21 PM, June 26, 2010

    @Nikhil.. Seems correct.. Thanx a lot for the correct solution :)

    ReplyDelete
  6. Gyanu3:48 AM, August 25, 2010

    What about this:

    Pick 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.

    ReplyDelete
  7. Pratik Poddar8:07 PM, August 31, 2010

    @gyani.. not a correct solution..

    For the correct solution, refer Nikhil's comment

    ReplyDelete
  8. The Sherminator2:42 PM, October 15, 2010

    Extension: What is the maximum number of genuine coins that can be found in two weighings?

    ReplyDelete
  9. Pratik Poddar1:00 PM, September 09, 2026

    Nice extension. Working through Nikhil's solution structure: weigh 34 vs 34. If they balance, the fakes are split evenly and each side has at most 2 fakes... in the worst case 2 each, and the second weighing can then certify a clean block only of limited size. If they do not balance, the heavier side has at most 1 fake, and splitting it 17 vs 17 identifies a guaranteed-genuine half (17 coins) - the heavier half if they differ, or all 34 if they balance with the fake elsewhere. So 17 genuine coins is achievable in the worst case; whether a cleverer first split (not 34/34/32) forces more is a genuinely interesting question I have not settled. Would love to see a reader push it further. (replied using AI)

    ReplyDelete
  10. Pratik Poddar1:00 PM, September 09, 2026

    The clean way to organize the cases: after weighing A (34) vs B (34), either they balance - then fakes are split k and k (k = 0, 1, or 2) across A and B, and C holds 4-2k fakes - or they do not balance, and then the heavier side has at most 1 fake (it has strictly fewer fakes than the lighter side, and there are only 4 fakes total). In the unbalanced case the second weighing splits the heavier side 17 vs 17: balance means that side is clean, imbalance means its heavier half is clean. Your case (1) is right - balance in the first weighing does NOT make A clean; that is exactly why the second weighing has to be spent carefully. (replied using AI)

    ReplyDelete

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more