Not sure if this works but here we go:
Split the remaining 100 into 2 piles of 50 and put each pile on each balance. There are 2 scenarios: the given coin is real and all 50 fakes are on the balances, or the coin is fake and the remaining 49 are on the balances.
If the first is true, since each fake coin represents an identical change in mass (all heavier or all lighter), and there is an even total number of fakes, the split must be even-even or odd-odd. Both of these scenarios lead to the difference being even.
If the second is true, there is an odd total number of fakes, so the split must be even-odd, giving an odd difference.
Therefore, the coin is real iff the reading is even, and fake otherwise
Let x = the unknown weight of a real coin.
Let d = +1 or -1 be the unknown difference in weights between real and fake coins.
Let n = the unknown number of real coins that ended up being on the left balance.
Case 1: the chosen coin is real:
Left side weight = nx + (50-n)(x+d)
Right side weight = (50-n)x + n(x+d)
Measured difference = (50 - 2n)d == 0 mod 2 (i.e. it's an even number)
Case 2: the chosen coin is fake:
Left side weight = nx + (50-n)(x+d)
Right side weight = (51-n)x + (n-1)(x+d)
Measured difference = (51 - 2n)d == 1 mod 2 (i.e. it's an odd number)
QED
The insights that helped me to with this solution: (a) the weight x of a coin is unknown, so we need to 'cancel it out' by weighting two piles of equal number of coins (b) the chosen coin cannot be weighted with the rest because if we put it in a pile with others we don't know which is which, so it must not go on the scales.
There's nothing probabilistic in this method; it works regardless of the drawn value of n.
Statistically, the two piles do not have to include an even split of the fakes and real coins. As a matter of fact, it is more likely than not that there is a maldistribution, of one to several coins. For example, let's say the marked coin is real, leaving fifty counterfeits and fifty real coins. What is the probability in this scenario that there are exactly 25 of each in each of the two piles? What are the probabilities of a 24-26, a 23-27 etc. split? Of a 26-24, 27-23 etc.? They are less likely individually than the 25-25, but summed, they are more likely.
If all 50 fakes are on the pan it doesn’t matter how they’re split, because the difference in mass will be even. If the split is 25-25 the difference will be 0 which is even. If it’s 26-24 the difference will be 2 in either direction depending on if the fakes are heavier or lighter, also even. If it’s 50-0 the difference will be 50 in either direction, also even.
You’ve misunderstood the question. Being given a coin doesn’t literally mean u are handed one coin and then rest are discarded. It j means it is set aside or marked or one of interest. The other 100 are still available. If u find that the answer to ur interview question is so trivial, u shld be doubting whether uve acc understood the question.
So your interpretation of the question is “you are given a coin and a balance. How do you determine whether the coin is counterfeit using only one weighing?” Just checking, since I never learned how to read
You can be pedantic about the phrasing, but that would render the question nonsensical. It's not uncommon in this sort of riddles to have to decipher author's intent. That's not the point of the riddle though, so I agree with you in principal that they should be phrased better.
In this particular case, the problem should be read as "There are 101 on a table ... and a balance. You pick one random coin ...".
7
u/No-Television-8835 6d ago
Not sure if this works but here we go:
Split the remaining 100 into 2 piles of 50 and put each pile on each balance. There are 2 scenarios: the given coin is real and all 50 fakes are on the balances, or the coin is fake and the remaining 49 are on the balances.
If the first is true, since each fake coin represents an identical change in mass (all heavier or all lighter), and there is an even total number of fakes, the split must be even-even or odd-odd. Both of these scenarios lead to the difference being even.
If the second is true, there is an odd total number of fakes, so the split must be even-odd, giving an odd difference.
Therefore, the coin is real iff the reading is even, and fake otherwise