# Different Ball Puzzle

You are working in a ball factory, where balls of weight 1U, 2U, 3U ... 8U are made in 8 sections. One day, you are given 1023 black balls , all (except one special ball) from section 1, meaning weight = 1U (1U = 100 gram, but that is not really relevant) and you have a balancing scale, which shows whether left-is-more (<) or both-are-equal (=) or right-is-more (>). You also have one green ball of weight 1U.

All balls have the same size, look the same (except your own green ball) and feel same. All balls were made here, and you have to find which section that special ball (whose weight may be 2U or 3U or ... 8U) came from.

Everytime you use the balancing scale, you lose some brownie points (1 brownie point = 4 maroonie points, but that is totally irrelevant here), hence you want to find the answer with the least number of weightings.

Can you prove that your solution uses the least number of weightings ?

• Well, we know the least number of weighings required is two. May 31 '15 at 18:47
• There are 7 possibilities for the answer (2...8) and two weighings produces 3*3 = 9 possibilities, so there are possibly enough to cover all cases. May 31 '15 at 18:49
• But you don't know which one is the fake ball! May 31 '15 at 18:50
• @leoll2 The question only states that you find which section the special ball came from, not that you find out which one it its. (Also, it is definitely not fake as it is made in the same factory as all the others!) May 31 '15 at 18:55

You appear to need 3 weighings.

Split your 1023 balls into 3 equal groups of 341. Compare 2 of these, and you know which group the heavier ball is in. Call the heavier group H and one of the normal groups N

Compare H with N + 4 balls. Balancing means it came from section 5, otherwise you know whether it came from 2-4 or 6-8. If it comes from one of these ranges, test against the midpoint (3 or 7) to find where in the range it lies. i.e. test H vs N+2 or H vs N+6. You're done!

Proof that 3 weighings are required: We need to distinguish between 7 different possibilities, which requires $log_27 = 2.8$ bits of information. A weighing can give us $log_23 = 1.58$ bits, which appears to make 2 sufficient. Unfortunately, a weighing when we don't know which side has the heavier ball only provides $log_22 = 1$ bits of information about the weight of the ball (Either the ball weighs exactly the right amount to balance the pans, or it does not). Since we start with no knowledge of where the ball is, our first weighing gets us only 1 bit about the weight of the ball, and we still require 1.8 bits - too much for the 1.58 bit maximum from a balanced weighing with knowledge of where the heavy ball is.

Here is a slightly different argument why 2 weighings are insufficient.

Suppose that your first weighing is $x$ balls against $y$ (doesn't matter if any are green), where $x\le y$.

If the oddball is on the $y$ ball side, then the scale will certainly tip towards $y$. This happens no matter what the oddball weighs, so you learn nothing about its weight in this case.

Thus, it is possible to be left with 7 possible scenarios after your first weighing; in those cases, one additional weighing is not enough.