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. chera10:05 PM, October 11, 2010

    This comment has been removed by a blog administrator.

    ReplyDelete
  2. Pratik Poddar10:25 AM, October 12, 2010

    @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. Pratik Poddar10:31 AM, October 12, 2010

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

    ReplyDelete
  4. The Sherminator1:01 PM, October 13, 2010

    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

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

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