Given a balance scale that is sure to break after X weighings, find an equation for the largest number of coins N, from which you can determine a fake coin that has the wrong weight if
A: You know whether the fake is lighter or heavier
B: You do not know whether the fake is lighter or heavier
(Assume only one of the N coins is fake)
(In reply to
solution to B by pleasance)
I think you can look at it this way.
For each weighing, there are 3 possible outcomes, i.e. balanced, heavier or lighter. Thus, for X weighings, the total number of unique results would be 3^X out of which one is balance-balance-balance, which occurs when we exclude the coin totally frmo our weighings. Thus, removing this case would give a total of 3^X-1 possibilities.
Now, since there are N coins, and each of them could be either heavier or lighter, thus, the total number of different cases is 2N that need to be mapped to these 3^X-1 possibilities.
Thus, this gives us the inequality 2N <= 3^X-1 or rather,
N<= (3^X-1)/2
For the case where we know whether the coin is heavier or lighter, there are only N cases as opposed to 2N. Thus, the inequality would become
N <= 3^X
since, in this case, even a balance-balance-balance result would tell us which coin is it and thus excluding it totally from our weighings is alright.
re: solution to B
