A Random Scale
Suppose we have 3n identical-looking coins. One of the coins is fake and lighter than the other coins which all are real. We also have a random scale. That is a scale that at each weighing behaves randomly. Find the fake coin in the smallest number of weighings. Oops! That won’t work! It is impossible to find the fake coin. The scale can consistently misbehave in such a way as to blame a specific real coin for being fake.
Let’s try something else. Suppose we have two scales: one normal and one random. Find the fake coin.
What am I thinking? The normal scale can point to one coin and the random scale can point to another coin and we are in a “she said, he said” situation which we can’t resolve.
Now, in my final try, I’ll make it right. We actually have three scales, one of which is random. So here we go, with thanks to my son Sergei for giving me this puzzle:
Puzzle. We have 3n identical-looking coins. One of the coins is fake and lighter than the other coins, which all are real. We also have three scales: two normal and one random. Find the fake coin in the smallest total number of weighings.
Let’s start with this strategy: repeat every weighing on all three scales and have a majority vote. At least two of the scales will agree, thus pointing to the true result. This way we can use a divide-into-three-equal-groups strategy for one scale to find the fake coin. It will require 3n weighings.
Can we do better? Of course, we can. We can repeat every weighing on two scales. If they agree we do not need the third scale. If they do not agree, one of the scales is random and lying, and we can repeat the weighing on the third scale to “out” the random scale. After we identify one normal scale, the process goes faster. In the worst case we will need 2n + 1 weighings.
Can we do even better? Yes, we can. I will leave it to the readers to find a beautiful solution that is asymptotically better than the previous one.
Update on Dec 24, 2016. The total number of coins should be 32n, not 3n. We are looking at the worst case scenario, when the random scale is adversarial.
Share:
Konstantin:
3^{2n} coins in (3n+1) weighings.
23 December 2016, 4:50 amnone:
Problem is not strictly formulated.
23 December 2016, 10:26 pmIs a scale actually random in a probabilistic sense and “asymptotically better” means involving terms like expectation?
Or does the solution you mentioned give a worst-case estimate for any sequence of results from that scale?
For example, we can choose the pair on each step. If each weighting is truly random, the probability of not discovering faulty scales till the last step goes to 0 very fast. Are you expecting an answer like this?
Dai:
Good problem!
12 January 2017, 8:11 pmweesh:
I’ve found a “new” version of the counterfeit coin problem where the odd coin is either heavier or lighter, but you don’t know which.
31 January 2017, 12:22 pmFormulating a puzzle with an unknown oddball coin AND and unknown oddball scale seems amusing.