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.
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.)
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.
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.
