6
$\begingroup$

I have 36 identical coins of which four, all weighing the same, are known to be fake. Fake coins are either all heavier than genuine coins, or all lighter.

At most how many weighings on a balance scale do I need to determine whether fake coins are heavier or lighter than genuine coins.

$\endgroup$
3
  • 1
    $\begingroup$ Spoiler: A version of puzzle with 1 fake coin in 12 identical coins. youtu.be/tE2dZLDJSjA $\endgroup$
    – I'm Nobody
    Oct 11, 2022 at 5:55
  • 1
    $\begingroup$ Should it be "at least"? $\endgroup$
    – holydragon
    Oct 11, 2022 at 8:47
  • 3
    $\begingroup$ @holydragon I guess that wording ambiguity is always present in these kinds of questions where we try to minimize the maximum. If we use "at least", it can mean this number of weighings is necessary, but maybe not sufficient. By using "at most", it's trying to get at "by the time we reach this number of weighing, we can already determine". See, for example, the complexity of wording I used just to get this point across in this puzzle $\endgroup$
    – justhalf
    Oct 11, 2022 at 9:29

3 Answers 3

2
$\begingroup$

For success in 5 weightings:
first measurement: 1..18 vs 19..36
second measurement: 1..9 vs 10..18

case 1: if =,= then 1..9 has one false coin
measure 1..3 vs 4..6 and 1..3 vs 7..9
If <,< =,> or >,= then the false coins are lighter
If >,> =,< or <,= then the false coins are heavier

case 2: if =,> then 1..9 has 2 heavy coins or 10-18 2 light coins
measure 1..3 vs 4..6 and 1..3 vs 7..9
If =,= then the false coins are lighter
else the false coins are heavier

case 3: if >,= then 1..9 (as wel as 10..18) has 2 heavy coins or 0 light coins
measure 1..4 vs 5..8 and 1..2 vs 3..4
If =,= then the false coins are lighter
else the false coins are heavier

case 4 if >,>
(here 1..9 has at least 2 heavy coins, or no light coins)
measure 1..4 vs 5..8; if equal, measure 1..2 vs 3..4; if equal again, measure 1 vs 2
all equal : light else: heavy

In most cases, four weightings are enough, but I can't get rid of the fifth (in case 4), and I do not see a better strategy. (Note that all other cases are symmetric to (one of) the mentioned ones, and thus can be sone as fast.)

$\endgroup$
3
$\begingroup$

Somewhat based off the previous answer but I think we can do better than $8$ weightings.

$6$ tries in worst case

Number coins from $1$ to $36$ and denote the coins $\;i, i+1, \dots , j\;$ as $[i,j]$.

First let us compare $[1,1]$ with $[2,2]$. If they are not equal, then clearly exactly one of the two coins must be a fake. In that case, our next comparisons will be as follows:
$[1, 2]$ vs $[3, 4]$
$[1, 2]$ vs $[5, 6]$
$[1, 2]$ vs $[7, 8]$
$[1, 2]$ vs $[9, 10]$

If we get equal weights for some group, then that group contains exactly $1$ fake as well. Otherwise the possibilities for that group are either both fakes or both real. Since we have exactly $4$ fakes in total so the "both fakes" group can only occur once. Similarly if we get the equal verdict twice, then there won't be any "both fakes" group.

Thus if we get a non-equal verdict at least twice, then we know which groups contains "both real" and we have our answer in $5$ weightings.

Now what if $1$ and $2$ have equal weights? So either both are real or both are fake. Then we compare $[1,2]$ with $[3,4]$. If they are not equal, we do the following comparisions:
$[1,4]$ vs $[5,8]$
$[1,4]$ vs $[9,12]$
$[1,4]$ vs $[13,16]$
$[1,4]$ vs $[17,20]$

Since $[1,4]$ contains either $1$, $2$ or $3$ fakes, so using similar logic again we can find a group with $4$ real coins by looking at the majority non-equal verdict.

If $[1,2]$ had equal weight as $[3,4]$, then the group $[1,4]$ contains either 4 fakes or 4 reals. We then compare $[1,4]$ with $[5,8]$. If they are not equal, then:

Compare $[5,8]$ with $[9,12]$. If they are not equal, then there must be at least 1 fake coin over here indicating $[1,4]$ are all reals.
If previous comparison resulted in equal weights, either all coins in $[5,12]$ are real (indicating $[1,4]$ being all fake) or there are at least 2 fake coins in $[5,12]$.
Then compare $[5,12]$ with $[13,20]$. If not equal then $[1,4]$ are all reals, otherwise there must be at least 4 fake coins in $[5,20]$ or none at all.
Finally we compare $[5,20]$ with $[21,36]$. If they are equal again, then as $8$ fake coins is not a possibility, so $[5,36]$ must be all real coins meaning $[1,4]$ is all fake.

Now the final case where $[1,4]$ was also equal with $[5,8]$, this means $[1,8]$ are all real coins. We can keep doubling now to find a group with fake coins and we have our answer.

$\endgroup$
2
  • 2
    $\begingroup$ For the [1,2] inequal case, you only need 4 more weightings I guess? As you said, if we have 2 equals (and at most 3 equals), then the inequal one would be both real. So at most one equal, and you just need 3 more weightings to determine majority. This doesn't change the worst case, though. Overall seems correct. +1 $\endgroup$
    – justhalf
    Oct 11, 2022 at 13:38
  • $\begingroup$ @justhalf you're right. updated. $\endgroup$ Oct 11, 2022 at 13:46
0
$\begingroup$

IDENTIFYING ALL FAKE COINS :

We can number the coins $1...36$ , then choose 4 out of these. That is $36\times35\times34\times33$ Possibilities, but the order is not important, hence we have to Divide by $1\times2\times3\times4$, which gives us:

$$3\times35\times17\times33$$

These 4 Coins can be either heavier or lighter , hence 2 Cases.

Hence Total Possibilities : $2\times3\times35\times17\times33$

Each Weighting give 3 Possibilities : left heavy or right heavy or both Equal.

When we have $N$ Weightings , we have $3^N$ Possibilities.

$$3^N \approx 2\times3\times35\times17\times33 $$

We get N = 11 which is the theoretical Necessity.

$3^{11} = 177147$
$2\times3\times35\times17\times33 = 117810$

IDENTIFYING WHETHER FAKE COINS ARE HEAVIER OR LIGHTER :

We can get this in fewer Weightings because we want to extract lesser information.

Number the Coins $1...36$

STARTING STAGE :
Compare 1 with 2.
If Equal, Compare 1+2 with 3+4.
If Equal, Compare 1+2+3+4 with 5+6+7+8.
If Equal, we have 8 Coins which are genuine.

ENDING STAGE :
Compare these 8 with the other 8. We will get heavier (Answer) or lighter (Answer) or Equal (unknown).

When unknown : We can then put these 16 against other 16 to get the Answer.

If still Equal, then the last 4 are the fake Coins. We can Check with 4 genuine Coins to get the Answer.

We have used 6 Weightings in Worst Case.

If we had InEqual Weightings in STARTING STAGE itself, then we have a set of Coins (having maybe 2 or 4 or 8 Coins) where at least 1 is a fake Coin.

The ENDING STAGE will change in this Situation.

We may have the Set (with X = 2 or 4 or 8 Coins) containing at least 1 fake Coin.

Take X=2 Case :
Compare the lighter Coin with 3 , 4 , 5 , 6 , 7 , 8 , 9 : If all Equal , then the heavier Coin was the fake.
If lighter Coin is always lighter , then that is the fake Coin. Other wise , we can make a Pile with heavier Coins & a Pile with lighter Coins. Which ever Pile has more than 4 Coins is genuine.

We have used 8 Weightings in Worst Case.

Take X=4 Case :

Take X=8 Case :

Hence We can get the Answer in 6 Weightings in Worst Case.

While trying to update that , I got a new Solution which , I figure , is easier :

Compare 1 & 2 : If InEqual , we put these into heavier Pile & lighter Pile.
Compare lighter Coin with 3 & put in Correct Pile.
Compare lighter Coin with 4 & put in Correct Pile.
Compare lighter Coin with 5 & put in Correct Pile.

(X) If all Equal till now , we have 5 genuine Coins. Compare with 5 others to get the Answer. If Equal , these are also genuine , hence put these together. Compare with 10 other Coins. If Equal , these are also genuine , hence put these together to get 20 genuine Coins. Compare with 16 of these with the other 16 to get the Answer.

Worst Case : 7 Weightings.

(Y) If not all Equal till now , at this Point , we will have a Pile with 1..4 heavier Coins & a Pile with 4..1 lighter Coins , with 5 Coins in total.

Compare Some lighter Coin with 6 , 7 , 8 , 9. Put each Coin into the Correct Pile. We will have a Pile with at least 5 Coins, with the other Pile having at most 4 Coins.

The larger Pile is genuine , the other is fake.

Worst Case : 8 Weightings.

$\endgroup$
4
  • 3
    $\begingroup$ I don't understand this: "If we had InEqual Weightings in STARTING STAGE itself, then we have a set of Coins (having maybe 2 or 4 or 8 Coins) where half are fake Coins." What if 1 and 2 are equal, and 1&2 and 3&4 are equal, but then 1234 are not equal to 5678. You could have 1234 genuine and 5678 could have any non-zero number of fake coins. For example coin 5 could be the only fake coin among them. $\endgroup$ Oct 11, 2022 at 11:09
  • $\begingroup$ To add to Jaap's concern, how do we get the set of genuine coins to compare to in the alternate ENDING STAGE? $\endgroup$
    – justhalf
    Oct 11, 2022 at 11:26
  • 1
    $\begingroup$ Oh , I got that mistake , @JaapScherphuis , It is actually "Containing at least 1 fake Coin" , I will edit it shortly. $\endgroup$
    – Prem
    Oct 11, 2022 at 11:31
  • $\begingroup$ When we have at least 1 fake Coin , we can make groups out of the remaining Coins , such that at least 1 group has all genuine Coins , @justhalf , But I will edit it shortly. $\endgroup$
    – Prem
    Oct 11, 2022 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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