Chameleon Coins
We all have played with problems in which we had real coins and fake (counterfeit) coins. For this post I assume that the fake coins are always lighter than the real coins. My coauthor Konstantin Knop invented a new type of a coin: a chameleon coin. This coin can mimic a fake or a real coin. It can also choose independently which coin to mimic for each weighing on a balance scale.
You cannot find the chameleon coin in a mix with real coins if it does not want to be found, because it can consistently behave as a real coin. Let’s add classic fake coins to the mix, the ones that are lighter. Still the task of identifying the chameleons using a balance scale cannot be achieved: the chameleons can pretend to be fake coins. We can’t identify the fake coins either, as the chameleons can mess things us up by consistently pretending to be fake.
What we can do is to find a small number of coins some of which are guaranteed to be fake. Consider the simplest setup, when we have one fake coin and one chameleon in our mix of N coins. That is we have N − 2 real coins. Our task now is to find TWO coins, one of which has to be fake. As usual we want to do it in the smallest number of weighings that guarantees that we’ll find the two coins. Let me give you a fun problem to solve:
Puzzle. The total number of coins is four. And as above we have one chameleon and one classic fake. In two weighings find two coins so that one of them is guaranteed to be fake.
If you want to learn more, we just wrote a paper titled Chameleon Coins.
Share:
Felix:
Let A, B, C, D be the four coins.
21 January 2017, 10:54 pmFirst, weigh A+B against C+D. If one side is lighter, then the side is guaranteed to have the fake coin. If not, then we know the chameleon was behaving as a fake coin, and it’s not on the same side as the fake coin.
Then, weigh A against B. We know at least one of them is real. If one side is lighter, then we have found the fake coin. Otherwise, the other has to be the chameleon, and we know the fake coin is either C or D.