Coin Balancing

Source: Asked to me by Vivek Jha (Senior Undergraduate, EE, IITB)

Problem: Among 10 given coins, some may be real and some may be fake. All real coins weigh the same. All fake coins weigh the same, but have a different weight than real coins. Can you prove or disprove that all ten coins weigh the same in three weighings on a balance scale?

BTW, List of previously asked Coin related puzzles on the blog:
Russian Coins
Coin Weighing Problem
Another Coin Problem
Coins Puzzle
Consecutive Heads
Five Thieves and Bounty

Update (Oct 12, 2010)
Solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments! Reposted by me removing typo.

Comments

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. @chera.. great solution.. thanks a lot.. How did u come up with this?
    :) Just a minor typo in Step 1 though..

    Solution copied again:

    Divide the 10 coins into 4 groups A, B, C and D respectively having 3,1,2, and 4 coins respectively.

    Now do following;

    step 1 : compare A with B + C.

    step2 : compare A + B with D.

    step 3 : compare A + C with B + D.

    claim is that the three steps yield balanced weights if and only if all weights are equal.

    Proof:
    If part is trivial.
    We concentrate on iff part. Suppose all the 3 steps yield balanced weights. Let a,b,c and d denote the number of fake coins in A,B,C and D respectively. Then we have following 3 equations :
    a=b+c, a+b=d and a+c= b+d

    which simplifies to a=3b,c=2b and d=4b. As we have 10 coins in total, a+b+c+d=10b <= 10. hence b=0 or b=1. Thus either no coin is fake or all coins are fake. In either case, all weights are same.

    ReplyDelete
  3. removed chera's post as the typo could confuse readers.. Chera's solution copy-pasted in my comment.. Thanks..

    ReplyDelete
  4. An analogous solution:
    Let the balls with a larger number (>=5) be represented by A. The other balls are represented by B. To prove or disprove A=10 in 3 weighings.

    1st Weighing: Divide the 10 balls into two equal groups and weigh them.

    If they are equal, then the possible scenarios are:
    (5A,0B) = (5A,0B)
    (4A,1B) = (4A,1B)
    (3A,2B) = (3A,2B)

    If they are unequal, A is not equal to 10 (disproved).

    2nd weighing: Take all the five balls from one of the panes (say left). Take one of the balls from the other pane (keep track of the ball you pick). Divide the six balls into two groups of three each and weigh them.

    If they are equal, then the possible scenarios are:
    (3A,0B) = (3A,0B). The remaining balls are (4A,0B). The ball picked was A. => Case1
    (2A,1B) = (2A,1B). The remaining balls are (4A,0B). The ball picked was B. => Case2
    (2A,1B) = (2A,1B). The remaining balls are (2A,2B). The ball picked was A. => Case3

    If they are unequal, A is not equal to 10 (disproved).

    3rd weighing: Take the picked ball and all the three balls from the pane which did not have the picked ball. Weigh these four balls against the remaining four balls (the balls not weighed in the 2nd weighing).

    Looking at the three cases from 2nd weighing:
    Case1: The weighing machine will be balanced.
    Case2: (2A,2B) is weighed against (4A,0B) => imbalance (disproved).
    Case3: (3A,1B) is weighed against (2A,2B) => imbalance (disproved).

    Hence, A=10 iff the two sets of balls in all three weighings are equal :)

    ReplyDelete

Post a Comment