Question:
There are 9 coins. Out of which one is odd one i.e weight is less or more. How
many iterations of weighing are required to find odd coin?
Answer:
It is always possible to find odd coin in 3 weighings and to tell whether the odd
coin is heavier or lighter.
1. Take 8 coins and weigh 4 against 4.
o If both are not equal, goto step 2
o If both are equal, goto step 3
2. One of these 8 coins is the odd one. Name the coins on heavier side of
the scale as H1, H2, H3 and H4. Similarly, name the coins on the lighter
side of the scale as L1, L2, L3 and L4. Either one of H's is heavier or one
of L's is lighter. Weigh (H1, H2, L1) against (H3, H4, X) where X is one
coin remaining in intial weighing.
o If both are equal, one of L2, L3, L4 is lighter. Weigh L2 against L3.
If both are equal, L4 is the odd coin and is lighter.
If L2 is light, L2 is the odd coin and is lighter.
If L3 is light, L3 is the odd coin and is lighter.
o If (H1, H2, L1) is heavier side on the scale, either H1 or H2 is
heavier. Weight H1 against H2
If both are equal, there is some error.
If H1 is heavy, H1 is the odd coin and is heavier.
If H2 is heavy, H2 is the odd coin and is heavier.
o If (H3, H4, X) is heavier side on the scale, either H3 or H4 is
heavier or L1 is lighter. Weight H3 against H4
If both are equal, L1 is the odd coin and is lighter.
If H3 is heavy, H3 is the odd coin and is heavier.
If H4 is heavy, H4 is the odd coin and is heavier.
3. The remaining coin X is the odd one. Weigh X against the anyone coin
used in initial weighing.
o If both are equal, there is some error.
o If X is heavy, X is the odd coin and is heavier.
o If X is light, X is the odd coin and is lighter.
0 Comments:
Post a Comment
comment