There are $5$ rupees on Arnav's table. He knows that exactly $2$ of the rupees are counterfeit. One of these $2$ coins is lighter than a normal (non-counterfeit) rupee, and one of these $2$ coins is heavier than a normal rupee. Arnav conveniently has a balance scale next to him, and he would like to identify both fake coins, and determine which one of the fake coins is heavier and which one is lighter. What is the minimum number of weighings that Arnav needs to do so?
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
There are only 3 comparisons needed. There are 20 (=5*4) permutations of the coins (5 positions where the first counterfeit coin can be, and then only 4 positions where the other counterfeit can be located). The following image depicts those permutations (N=normal, H=heavier, L=lighter) on its left side. There are of course multiple possibilities how to solve this problem in 3 steps. The most easiest is comparing (1.) coin# 1 to coin #2 and (2.) coin#3 to coin #4; dependent on the outcome of the first comparison we then need to do different comparisons; if the outcome of (1.) was that both are equal, we need to compare one of the two to the last coin. For example: (3.) coin #1 to coin #5. If the outcome of (1.) was not equal, we can e.g. compare: (3.) coin #4 to coin #5. Having done the 3 measurements this way, we can then deduct which of the coins must be of which kind;
$\begingroup$
$\endgroup$
1
Here's a solution in at most:
$6$
Reasoning:
Weigh any two coins. If they are the same, we have $3$ coins left, L, N and H. It will take $3$ further weighings to identify which is which.
If they are not the same, we know we have either LN, LH or HN. Leave these to the side, and remember which was heavier. From the remaining coins we know we have at least $2$ normal coins. Weigh any two from this set, if the same, we have a set of $3$, LNH, and we continue as before.
If different, we need $2$ further weighings to identify the fake coin, and repeat as in the first step. This is the worst case scenario, and takes a total of $6$ weighings, using our memory of a previous weighing.
-
$\begingroup$ This is correct - the bound can be significantly improved. $\endgroup$ Dec 9, 2018 at 11:57
$\begingroup$
$\endgroup$
Here is a short text version
- Compare A to B, and C to D.
- If A=B, they are real. Compare one to E. If E is real, then C and D are fake, and they've been compared, telling you which is heavy and which is light. If E is heavy, then C or D is light and the other is real, and they've been compared, telling you which is which. If E is light, same idea.
- If C=D, they are real. Compare one to E. Same idea.
- If neither, E is real. Compare E to any other. Say A is lighter than B and C is lighter than D. Either: A and D are real, B is heavy, and C is light; or, B and C are real, A is light, and D is heavy. Comparing E to any one of these tells you which.
answered Jan 28, 2019 at 1:24