Middle weight puzzle

Question

There are 100 white and 101 black balls. All the balls have different weights. Balls of the same colour look the same. White balls are numbered from lighter to heavier (from 1 to 100). The same is true for black balls (they are numbered from 1 to 101).

What is the minimal number of weightings on a balance scale to find the ball with the middle weight? (That is, the ball which will have the number 101 if all the balls would be sorted and numbered from lighter to heavier.)

Additional explanations:
1. On a balance scale you can compare X balls on one arm to X balls on another arm and tell whether they are lighter, heavier or equal in relation to each other.
2. Since the balls are numbered, you don't have to compare balls of the same colour to each other using the scale as you know the result already.

I know that there is a solution with 8 weightings (though I do not know it). I am especially interested in the proof of minimality, since I want to be sure that 8 (or any other number) is the minimum.

Answer 1

Proof of minimality

8 is the minimum, with the following claims:

1. In the worst case, the result of comparison can only be one of the two possibilities (left heavier or right heavier), since equality might not be present and hence we can't rely on that.
2. Therefore one weighting gives 1 bit of information.
3. There are 201 possible outcomes (each ball is a candidate of the median), which can't be encoded in 7 bits (7 bits give at most 128 possible outcomes)
4. Therefore the minimum possible number of weightings is 8.
5. Now it's left for us to prove that there is a solution with 8 weightings.

The 8 weightings

Per Manne almost gets it correct, it's just that things get trickier after the sixth weighting.

So, assuming the same thing as what Per Manne has said (using left sack to store balls which are certainly lighter than the middle ball, and right sack to store those which are heavier), the procedure to find the $(k+1)$-th ball for $k$ white balls ($w_1, w_2, \ldots, w_k$) and $k'$ black balls ($b_1, b_2, \ldots, b_{k'}$), where $k'$ is either $k$ or $k+1$, is as follows.

1. Let $m = \lceil\frac{k+1}{2}\rceil$ and $n = \lceil\frac{k'+1}{2}\rceil$
2. Compare $w_m$ with $b_n$
3. 1. If $w_m > b_n$ then put $b_1, b_2, \ldots, b_{n-1}$ on left sack and $w_m, w_{m+1}, \ldots, w_{k}$ on right sack
   2. If $w_m < b_n$ then put $w_1, w_2, \ldots, w_{m-1}$ on left sack and $b_n, w_{n+1}, \ldots, b_{k'}$ on right sack
4. Rename the balls, repeat to step 1 until we have 4 balls left (follow Per Manne's answer for more details) - you can actually continue this procedure until you get the result; the following steps are only for clarity.
5. At 4 balls at two balls each (we have done 6 weightings up to this point), we have these 6 possible combinations:
   1. $w_1, w_2, b_1, b_2$
   2. $w_1, b_1, w_2, b_2$
   3. $b_1, w_1, w_2, b_2$
   4. $w_1, b_1, b_2, w_2$
   5. $b_1, w_1, b_2, w_2$
   6. $b_1, b_2, w_1, w_2$
6. Note that at this time we have one more ball in right sack compared to left sack, so we are looking for the third element here.
7. Compare $w_2$ with $b_2$ (actually you would do this also if you follow step 1-4 above, this is just for clearer explanation)
   1. If $w_2 > b_2$ then we have either of the case (4), (5), or (6)
   2. If $w_2 < b_2$ then we have either of the case (1), (2), or (3)
8. At both case, we have three possibilities left. Since the two cases are analogous, we take the first three (1), (2), and (3).
9. Compare $w_2$ and $b_1$.
   1. If $w_2 > b_1$ then the third element is $w_2$
   2. If $w_2 < b_1$ then the third element is $b_1$
10. Done

Note that after step 5 (that is, after 6 weightings), we only do two more weightings (step 6 and step 8), totaling to 8 weightings.

Therefore 8 is the minimum.

Answer 2

Edit: The first version contained a silly mistake (after the sixth weighing), which justhalf has pointed out. I have corrected the solution, as well as the general comment at the end.

Number the balls W1, W2, ..., W100 and B1, B2, ..., B101 in order of increasing weight. Bring out one table and two empty sacks. Put all the balls on the table in two ordered rows, white and black. Put one sack on the left side and one on the right side of the table. After each weighing, we will put all balls that we know are lighter than the middle ball in the left sack, and all balls that we know are heavier than the middle ball in the right sack. When we are done, there should be 100 balls in either sack and one ball remaining on the table.

We will always compare one white ball against one black ball, and we will pick each ball from the middle of its row. There will be an odd/even theme here, but let's just start and see what happens.

We begin by comparing W50 and B51. (The choice W51 and B51 gives similar results.) There are two possibilities.

(1) If W50 > B51 then the 51 black balls B1,...,B51 go into the left sack and the 50 white balls W51,...,W100 go into the right sack.

(2) If W50 < B51 then the 50 white balls W1,...,W50 go into the left sack and the 50 black balls B52,...,B101 go into the right sack.

The worst case is (2), so we will focus on that. (In case (1), it is possible to leave B51 on the table and get the same situation as in case (2), if desired.) Rename the balls W1,...,W50 and B1,...,B51, and compare W25 with B26. The worst case is when W25 < B26, then W1,...,W25 go into the left sack and B27,...,B51 go into the right sack. We have 75 balls in each sack, and 25 white and 26 black balls on the table. (Note that this time it is the larger of these two numbers which is even!)

Again, we rename the balls W1,...,W25 and B1,...,B26, and we compare W13 with B14. The worst case is when W13 < B14, then W1,...,W12 go into the left sack and B14,...,B26 go into the right sack. We now have 87 balls in the left sack, 88 balls in the right sack, and 13 white and 13 black balls on the table.

Rename tha balls W1,...,W13 and B1,...,B13, and compare W7 with B7. In either case, seven balls go into the left sack and six into the right sack. We have 94 balls in either sack, and 6 balls of one color (say white) and 7 balls of the other color (say black) on the table.

After the next weighing (the fifth) we will in the worst case have 97 balls in each sack, and 3 white and 4 black balls on the table.

After the sixth weighing we will in the worst case have 98 balls in the left sack, 99 balls in the right sack, and 2 balls of each color on the table.

Rename the balls W1, W2 and B1, B2. Compare W2 with B2. If W2 < B2 then put W1 in the left sack and B2 in the right sack. If W2 > B2 then put B1 in the left sack and W2 in the right sack. We are left with only two balls on the table, and in the eight and last weighing we compare them against each other.

Some general considerations:

With this method, if there are 2k white balls and 2k+1 black balls on the table, with equally many balls in each sack, one will get k white balls and k+1 black balls on the table after one weighing (as always in the worst case). We can write this as $(2k,2k+1)\mapsto (k,k+1)$. Similarly, one can consider the other possibilities for even and odd numbers of balls, and get the following four possibilities for each weighing:

$$(2k,2k+1)\mapsto(k,k+1), \qquad (2k+1,2k+2)\mapsto(k+1,k+1),$$ $$(2k+1,2k+1)\mapsto(k,k+1), \qquad (2k,2k)\mapsto (k,k).$$

(If the number of white and black balls on the table is equal, then one sack has one ball more than the other, otherwise the sacks have the same number of balls.)