Three-pan balance?

Logic Level 3

You have a unique three-pan balance with which to measure the weight of coins. This balance has three pans, as its name implies. Each pan can be loaded with any number of coins after which you may press a button to turn the balance on. If all three pans have different weights, the scale will indicate to you the pan that has the 2 nd ^\text{nd} heaviest weight (so the pan that is not the heaviest nor lightest). However, if any two pans have the same weight, then the scale will read "ERROR" (because there is no unique 2 nd ^\text{nd} heaviest weight). After that, the balance switches off, and you can unload and reload the pans again for the next use.

In a pile of 64 coins, all but one of them have the same weight; the odd one is heavier. You want to identify this heavier coin in as few button presses (uses of the balance) as possible. With the best strategy, how many button presses do you need in the worst case?

1 7 5 4 2 8 3 6

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.

4 solutions

Ivan Koswara
Jan 11, 2016

If you're familiar with these kinds of problems , you might observe that there are 64 coins, and there are 4 possible outcomes from each balance use, so the answer is log 4 64 = 3 \lceil \log_4 64 \rceil = 3 , no?

Unfortunately, that is wrong. The trick is that it's impossible to have all four outcomes at any given use. Since we don't know exactly how heavy the extra coin is, let's assume it is heavier by a small enough amount that two normal coins are still heavier than the odd coin alone; after all, it's a "worst case". This way, any pan with more coins is always heavier than any pan with less coins.

Now, suppose our comparison has a unique pan with the most number of coins (that is, the other two pans have strictly less coins, each). Then this pan will always be the heaviest, and so will never be the middle one; our comparison will not give all four possible outcomes. The same applies if we have a unique pan with the least number of coins.

What happens if there is no such unique pan with most or least number of coins? Then all three pans will have the same number of coins. Since there is only one odd coin, at least two pans must necessarily not have the odd coin, and thus have the same weight; this way, the outcome is always ERROR.

In all cases, it's impossible to get four outcomes from each balance use. The best we can do is to use three outcomes from each use, giving log 3 64 = 4 \lceil \log_3 64 \rceil = \boxed{4} uses necessary in the worst case. This is obtained by keeping one pan empty (and the other two not empty); now the balance will always tell the lighter of the remaining two pans (or ERROR in case they are equal). The standard strategy finishes this problem.

Moderator note:

Great variant of this problem. Good approach of explaining why we don't have 4 possibilities in each weighing.

Using a number much larger than 64 would help reduce the likelihood of correctly guessing.

Abhra Gupta
Feb 19, 2020

I followed the process like Zahid Hussain's but a bit different.

Let K i K_{i} be the i t h i^{th} coin where i = 1 t o 64 i = 1  to  64 AND Let K i j K'_{i-j} be set of coins from K i t o K j K_{i}  to  K_{j}

Then,

We divide them in Four Groups

K 1 21 K'_{1-21} , K 22 42 K'_{22-42} , K 43 63 K'_{43-63} , K 64 K_{64} = Three Groups of 21 and a single coin.

The 4 Steps of Comparison are described below.

1] For the first comparison, we take K 1 21 K'_{1-21} , K 22 42 K'_{22-42} , K 43 62 K'_{43-62} [ NOTE: We have left alone K 63 K_{63} and K 64 K_{64} ]

2] For the second comparison, we take K 1 7 K'_{1-7} , K 8 14 K'_{8-14} , K 15 20 K'_{15-20} [ NOTE: Considering 8-14 are indicated by the scale. Hence 1-7 would contain the defective coin. We have left alone K 21 K_{21} which will be the defective if ERROR in Scale Occurs ]

3] For the third comparison, we take K 1 2 K'_{1-2} , K 3 4 K'_{3-4} , K 5 K_{5} [ NOTE: Similar Exclusion logic of step 2. Other cases would just swap groups. We have left alone K 6 a n d K 7 K_{6}  and  K_{7} ]        [ NOTE: For ERROR, test among K 6 a n d K 7 K_{6}  and  K_{7} and  K'_{1-2}) The last set used to avoid error.]

4] For the fourth and final comparison, we take K 1 K_{1} , K 2 K_{2} , K 5 7 K'_{5-7} [ NOTE: Similar Exclusion logic of step 2 gives away the Defective Coin]

The left alone coins in the notes section can be compared in a similar fashion like in step 4 and can be done well within the 4 tries. [Also done in Step 3] : K 6 a n d K 7 a n d K 1 2 K_{6}  and  K_{7}  and  K'_{1-2}

Hence Number of Button Presses is = 4

Zahid Hussain
Jun 30, 2019

For this question the pre condition needs to be that the weight of the heavier coin must be less than the weight of two normal coins otherwise there can always be confusion as to the results. Now the actual solution.
1. 21 21 22 Worst scenario error meaning both piles with 21 coins each are equal in weight so the abnormal coin is among the remaining 22 coins. (Had the abnormal coin been double the weight of the normal coin and had it been in one of 21 pile then its weight would have been equal to the 22 pile and still would have given error result)
2. 7 7 8 Again worst scenario; error, so abnormal coin among the 8
3. 3 3 2
a. One of the pile with three coins indicated meaning abnormal coin among the other 3
b. Error result meaning abnormal coin among the 2
4.
a. Place one in one pan another in second pan and the third one along with another one from the pile in the third pan.
If error then the one in the third pan is heavier. If one of the 1st or 2nd pans is indicated then that is the heavier one.
b. Place one in first pan other in the second pan and any other two in the third pan. The one indicated will have the heavier coin.



What if I keep one pan empty in all the steps to avoid the confusion that might arise due to the lack of the precondition you mentioned?

  1. 21 21 0 Worst scenario error meaning both piles with 21 coins each are equal in weight so the abnormal coin is among the left out 22 coins.
  2. 7 7 0 Again worst scenario; error, so abnormal coin among the 8
  3. 3 3 0

a. One of the piles with three coins indicated meaning abnormal coin among the other 3

b. Error result meaning abnormal coin among the 2

4. a. Place one in one pan another in second pan and the third one empty.

If error then the the third coin is heavier. If one of the 1st or 2nd pans is indicated then that is the heavier one.

b. Place one in first pan other in the second pan and the third one empty. The one indicated will have the heavier coin.

Praveen Kumar - 1 year, 9 months ago
Ankur Tripathi
Feb 29, 2016

first divide 21 coins in three of these pan and weight it , it detect either 2nd bal or error let it be error it mean all the 21 coins are equally likely i.e. equal of weight then minimum possible button press is 1 And if we select other case 2nd bal then we can detect one of the 2 pan having a coin which is different one let it be heavier then we select this pan of 21 coins and divide it into all the three pan equally 7,7,7 and weight it then it definitely detect 1 pan is heaviest of them and vice versa (divide 2,2,2 ) in all three pan if it equal then rest of 1 is odd other wise then the heavier 1 so worst case 4

Your weighings are all incorrect. If you have the same number of coins on all pans, the result is always error. The balance tells the middle one, not the heaviest one.

Ivan Koswara - 5 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...