4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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; decision tree

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is correct - the bound can be significantly improved. $\endgroup$ – user591814 Dec 9 '18 at 11:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.