Liar scale (another sets of coin problem with a twist)
You just got a new weighing scale and a set of 8 coins. You were told that one of the coin is heavier than the rest, but since all coins look and feel the same, you need to balance them to find out which one is the heavier coin by balancing them on your scale.
Your scale is digitized. When weighing two sets of coin, it will show an arrow toward the heavier side on a small monitor in the middle of the pans. When the pans weigh equally, it will show = mark.
However, before you bought the scale, someone inserted a malicious program into the scale. The scale is now capable of lying, i.e. showing wrong output on it's monitor. But the scale cannot make two consecutive lies. It can say truths however many times it wants.
You only know about it afterward, and now you have your set of coin to think about. How many weighings do you need to narrow the coins to two possible suspects of heavier coin?
(Inspired by IMO 2013 problem)
The answer is 5.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
In this case, we need to have two consecutive weighing to arrive at any conclusion. Note that for every balancing, we can have unconfirmed result about which is a possible suspect and which is not. For example, if the left pan is heavier, then every coin on the left pan is possible suspect. If the balance is equal, then every coin not balanced is possible suspect.
We can give a score to each coin during every balancing. For example, suspected coin gets 0 while unsuspected coin gets 1. After two balancing, all coins will have (0,0), (1,0), (0,1) or (1,1). Note that both coins with (1,0) or (0,1) are still suspects because the scale can lie once in those two consecutive balancing. So the remaining suspects are those with (0,0), (1,0) and (0,1). Note that the only confirmed result is that the heavier coin is not in the group with (1,1). So instead of balancing to find the heavier coin, we actually need to balance to exclude the normal coin.
In every balancing, we have three groups: pan A coins, pan B coins, and unbalanced coins. There are three possible result:
In a way, the balancing is like selecting the group which doesn't receive additional 1 score. But we also need to consider the fact that balancing result from two turn before now is expired and that the 1 score which is useful to us is the 1 score from two consecutive balancing. So getting a 0 is like resetting the score previously gained.
We need to maximize the amount of 1 score that is useful to us. We can define the coins that receive 1 in the latest balancing but not consecutively as single 1 coins . While the coins already gaining consecutive 1 score as consecutive 1 coins . Since we need to consider all possibilities, we'll just assume that our lack is very bad, and the weighing scale will choose the group with the highest score to reset it's scores (i.e. getting 0 scores so that the previously gained score becomes unusable). To prevent that, we need to evenly distribute the scores between pan A, pan B, and unbalanced group.
Starting from 8 suspects, none of them have score yet. If all of them gain 1 score, total score becomes 8. Ceiling of 8/3 is 3, so in optimal weighing, the total score would increase by 8-3 = 5. We can achieve that by distributing coins such that two groups will have 3 coins and one group has 2 coins. For example, pan A= 3 coins, pan B= 3 coins, and unbalanced= 2 coins If pan A is heavier, pan B and unbalanced group will receive 1 scores (5 coins becomes single 1 coins ) . The same thing happens when pan B is heavier. If pan A balances with panB, then coins in pan A and pan B receive 1 scores (6 coins becomes single 1 coins ). It was the possibility unlikely to happen because of our bad luck.
Now we have 8 suspects and 5 single 1 coins . If all of them receives 1 score, the total score will become 13. Because of our bad luck, the group which has it's score reset should has 5 scores (after each coin gets 1 more score). The total score should be 8. We can achieve this for example by dividing the group into: pan A (1 coin + 2 single 1 coins ), pan B (1 coin+ 2 single 1 coins ), unbalanced (1 coin + 1 single 1 coin ) After weighing, we'd likely get at least 3 consecutive 1 coins and 2 single 1 coins . We can now exclude the 3 consecutive 1 coins .
We now have 5 suspects with 2 of them are single 1 coins . If each coin gets 1 more score, we can get 7 scores. If we can balance it optimally, the group with it's score reset should have 3 scores (after assumption that each has gained 1 more score). We can do this for example by dividing: pan A (1 single 1 coin + 1 coin), pan B (1 single 1 coin + 1 coin), unbalanced (1 coin). After balancing, with our bad luck, we'd at least get 1 consecutive 1 coin + 2 single 1 coins .
We now have 4 suspects and 2 single 1 coins . Total score if each receives 1 score is 6. We can achieve optimal scoring by dividing the pan into: panA (1 single 1 coin ), pan B (1 single 1 coin ), unbalanced (2 unscored coin).
Now we have 3 suspects and 2 of them are single 1 coins . We only need 1 more balancing