Back to Coins
I loved coin puzzles, but after several research projects related to those shiny discs, I got tired of them. The fatigue was temporary, as confirmed by the following Facebook puzzle that reignited my interest.
Share:Puzzle. There are 30 coins in a circle that look the same. However, 20 of them are fake, and the rest are real. Fake coins weigh the same, and real coins weigh the same but heavier than fake ones. You need to find as many fake coins as possible using a balance scale once, given that the fake coins are positioned consecutively. What is your strategy?
Leo B.:
Does the “in a circle” clause have any useful purpose?
14 December 2023, 12:03 pmtanyakh:
Thenk you Leo. I forgot to mention that the fake coins are positioned consecutively. I added the clause now.
14 December 2023, 12:40 pmLeo B.:
What does satisfy “as many as possible” better: 10 if we’re lucky, or always 6?
14 December 2023, 3:47 pmlvps1000vm:
I can find two solutions: one for worst case scenario and another for average expectation.
There’s a strategy that always finds a coin. Best, worst and average are one coin.
For the best average expectation, another that finds five coins with probability 12/30 and zero with probability 18/30. Worst case is zero but average is two coins.(Equals another the finds six coins with probability 10/30)
I can also devise a strategy that gets you the jackpot of all ten coins with probability 2/30.
14 December 2023, 8:14 pmLazar Ilic:
You are forgetful. My first idea was to brute force with computer assisted search. Then I noted that the best result under the restriction that we weigh 1 coin versus 1 coin would be comparing without loss of generality the coin at position 1 with the coin at position 11. If they weigh the same then we can deduce that positions 1 through 11 are fake. If 11 is lighter then we deduce that positions 11 through 21 are fake. Thus we may ensure identifying 11 of the fake coins.
15 December 2023, 9:21 amLazar Ilic:
I am forgetful too sometimes. And slow. There are 3 possible outcomes of the weighing and 30 potential rotation locations for the coins. Thus by the Pigeonhole Principle there is an outcome which is mapped in to by >= 10 of the possible locations. But then the maximum size of the ensured fake coins set is the intersection of the 10 different length-20 range intervals which has maximum size 11 if and only if those were all consecutive as in our previously given construction.
16 December 2023, 4:34 am