Different Ball Puzzle

Question

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.

How will you go about this ?
Can you prove that your solution uses the least number of weightings ?

Answer 1

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.

Answer 2

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.

Answer 3

Specifically Expected Answer

We require some (around 6) balls which are known to be normal, so atleast 1 weighting is required for getting those normal balls.
For finding the section of the odd ball (which may be from sections 2-8 , 7 possibilities), we require minimum 2 weightings.
So, we require minimum 3 weightings in total.

With this thinking, the process may be:

(1) Make 3 sets ABC with 1023/3=341 balls
(2) Compare A & B, which is W1 : If equal, then remaining C has the odd ball, while if not equal, then A or B has the odd ball. So we have 341 ball in odd set and have many normal balls in other sets.
(3) Now use binary search algorithm to find how much more the odd set weighs. Check (odd set) against (normal set + 4 normal balls) which is W2. Based on result compare (odd set) against (normal set + 2 normal balls) or (odd set) against (normal set + 6 normal balls) which is W3. So with W1 & W2 & W3, we have the required answer.