Prove that all 101 balls have the same weight

Question

In a collection of 101 balls, each ball weighs a whole number of pounds. If any one is removed from the collection, the remaining balls can be divided into two groups of 50 balls each with the total weight of all balls in the first group equal to the total weight of all the balls in the second group. Prove that all of the balls weigh the same.

This problem has been taken from the book, A Moscow Math Circle by Dorichenko and it provides the following solution:

If we subtract the same number of pounds from the weight of each ball, the assumptions of the problem do not change because we can still remove each ball and divide the remaining ones into two groups of 50, each of which weighs the same.

Now choose the lightest ball and subtract its weight from the weight of each of the remaining ball. We will end up with one ball that weighs 0 pounds and another 100 balls. The total weight of the remaining 100 balls is an even number because we can divide them into two groups of equal weight. Is there a ball whose weight is an odd integer? If there were, we could take it out and put in the one weighing 0. Then the total weight of the 100 balls would be odd, and they could not be sorted into two groups of equal weight.

Therefore, each of the balls weighs an even number of pounds. If any of the balls had a nonzero weight we could change the problem again by dividing all the nonzero weights by 2. We can apply the argument above to again conclude that there cannot be a ball whose weight is odd. Divide by 2 again, and so on. We can’t divide the weights by 2 forever. Thus, all of the weights must have been 0, and all of the balls weigh the same.

This question has been asked at 2-3 places on math.stackexchange also and everybody is giving this solution only as the one above. Are there any other methods of solving this?

Such as another way of proving it by contradiction (something on the lines of: let's assume that there are 2 balls with different weights) or any other intuitive method.

I teach 7th-10th graders and I don't think that any of them would have been able to solve the question, if this was the only method. So, wondering if there's another, more intuitive method, which would strike these students.

Answer 1

If you are teaching young people, I would probably start with a much smaller example that almost works.

Imagine you have balls weighing 1, 2, 3, 4, and 5lbs. In total they weigh 15 lb. If I remove the 5, I need to divide the remaining 10 lbs of balls into 2 groups of 5, and I can: 1 and 4, and 2 and 3. Cool! What if I remove the 3 instead? I need 12 lbs or 2 groups of 6. 2 and 4 with 1 and 5 works. And if I remove the 1 instead? I need 14 lbs, 2 groups of 7. 2 and 5 with 3 and 4 works.

At this point it seems like this seemingly impossible condition on the group is plenty possible. Maybe there are infinite solutions!

But try removing 2. Now you need to split 13 pounds of balls into 2 equal groups, when all the balls have integer weights. Oh. That's going to be a problem.

This can lead you into talking about parity. If the total is odd, and you take out an odd one, you're dividing an even total and that is at least possible. But if you take out an even one, now you need to divide an odd number and that's impossible. So if the total is odd, there can't be any even numbers. By the same logic, if the total is even, there can't be any odd numbers.

Now you're in a place to go into the logic you laid out in your question. I might start by pointing out that you can subtract 1 from all of them (as long as none are 0 to start with) meaning that "all odd" and "all even" are kind of the same rule. Once people are comfortable with that, the "subtract the weight of the lightest one" may even occur to someone. Then, since all the numbers are even, and 0/2 is still 0, you can suggest dividing all the weights by 2. People might wonder why you're doing that, but will follow you.

Once you get them to understand that after you've divided by 2 they still all have to be even, you are super close to them realizing only 0 can keep being divided by 2 forever and stay even. And that's what the proof you provided says. Then you need to work your way back out to show you've proven all the balls have to have the same weight.

Answer 2

(This is more of an extended comment rather than a full answer.)

As far as I can see, the notion of parity is crucial for this puzzle to work. This can be seen by generalizing a bit: Instead of 101 balls, the puzzle just as well works for any odd number of balls (even though $1$ and $3$ are pretty trivial anyway). More interestingly, we can drop the requirement that the weights should be integers and can instead allow them to take values in any other number system $A$ (which may reasonably be any abelian group in this context).

Now, if $A$ has a notion of $2$-valuation like the integers (or the rationals, for that matter), the cited argument goes through as usual. But if there is no such valuation, the puzzle can actually stop working! As a concrete counterexample, consider the case of $5$ balls with weights a complete set of elements of $A=\mathbb{Z}/5\mathbb{Z}$. Now, I have not undertaken to find a counterexample with $101$ balls but I'm quite confident that a similar thing will work in general, as soon as there are at least $5$ balls. (Edit: Actually, it is not hard to see that any odd number of balls ($\geq 5$) with weights from $\mathbb{Z}/3\mathbb{Z}$ will have a nonconstant solution - just take a single $0$ and an even split of $1$'s and $2$'s and then fiddle a bit.)

All this is to say that the properties of $\mathbb{Z}$ used in the proof are really essential. (But of course, this does not necessarily imply that no simpler argument exists. Just that any valid argument somehow has to leverage the difference between $\mathbb{Z}$ and any number system without a $2$-valuation.)

Answer 3

Maybe it would be helpful to look at the answer as a system of equations?

Consider a scaled-down problem with only 5 total balls. Call the balls' weights $a$, $b$, $c$, $d$, and $e$.

Assume the balls have unique weights.

If you remove ball $a$, you split the other balls into two equal groups (without loss of generality, since you can freely exchange labels and balls at this point):

$$(1)\quad b+c = d+e$$

Then, if you replace ball $a$ and remove ball $b$, you have the following possible equations:

$$(2)\quad a + c = d + e\\ (3)\quad a + d = c + e\\ (4)\quad a + e = c + d\\ $$

(2) can't be true, because $a$ and $b$ have different weights, and this just replaces $a$ from (1) with $b$.

(3) and (4) are essentially equivalent, since we haven't made any distinction between $d$ and $e$ as of yet. So we can just pick either one.

So now we have two equations: $$(1)\quad b+c = d+e\\ (3)\quad a+d = c+e$$

We continue on by replacing ball $b$ and removing ball $c$. The possible ways of splitting the remaining balls are:

$$(5)\quad a+b = d+e\\ (6)\quad a+d = b+e\\ (7)\quad a+e = b+d$$

Once again, we can invalidate (5) because it is just (1) with $a$ replacing $c$. If all values are unique, they can't both be valid.
Similarly, we can invalidate (6) because it is just (3) with $b$ replacing $c$.

Now we have 3 valid equations: $$(1)\quad b+c = d+e\\ (3)\quad a+d = c+e\\ (7)\quad a+e = b+d$$

Continuing on, we replace $c$ and remove $d$.

The possible equations for the remaining balls are: $$(8)\quad a+b = c+e\\ (9)\quad a+c = b+e\\ (10)\quad a+e = b+c$$

Now we can eliminate (8) because of its conflict with (3), and we can eliminate (10) because of its conflict with (7).
(9) is the only valid equation remaining.

Now we have: $$(1)\quad b+c = d+e\\ (3)\quad a+d = c+e\\ (7)\quad a+e = b+d\\ (9)\quad a+c = b+e$$

One final time, we replace ball $d$ and remove ball $e$. Our possible splits are now:

$$(11)\quad a+b = c+d\\ (12)\quad a+c = b+d\\ (13)\quad a+d = b+c$$

(12) is invalid because of its conflict with (7), and (13) is invalid because of its conflict with (3), leaving (11) as the only possible valid equation.

We now have five equations in five variables:

$$(1)\quad b+c = d+e\\ (3)\quad a+d = c+e\\ (7)\quad a+e = b+d\\ (9)\quad a+c = b+e\\ (11)\quad a+b = c+d$$

Subtract (9) from (7):

$$ \begin{split} (7)\quad a+e &= b+d\\ - (9)\quad a+c &= b+e\\ \hline (14)\quad c+e &= d+e \end{split} $$

From (14), it is obvious that $c = d$. This invalidates the initial assumption that all the balls have different weights. If two balls (assume $c$ and $d$ WOLOG) have the same weight, then if we remove any other ball (say $a$), we know the two remaining balls $b$ and $e$ must either have the same weight, or must sum to $2c$ (=$2d$).

This means that $a$ must be the same as $b$, since if we swap $a$ and $b$, we still need $a$ and $e$ to match with $c$ and $d$ as above. The same is true if we swap $a$ and $e$.

Thus $a=b=e$ and $c=d$. But if that is true, and we remove $c$, we need a fourth number to make 2 equal pairs where 3 of the numbers are equivalent. Obviously, the only way to do that is if that fourth number is also equivalent, so $d=a$ (and $b$ and $c$). And $c=d$, so $$a=b=c=d=e$$ and all the balls have the same weight.

This logic can be extended to a system of 101 variables in 101 equations, thus proving the original problem, although I wouldn't suggest trying it by hand...

Answer 4

Here is an attempt to explain the provided solution more simply. The structure of the problem depends highly on odd-even (parity) arguments, but this provides a new way of looking at it, that is arguably more interesting and easier to understand.

It uses binary representation of numbers, which I never saw much use for in high school, but can be very useful for problems like this.

(Joke: The problem is even easier in binary since $101$ balls lead to a system with only five unknowns.)

---

The binary numbers used below are written with digits in reversed order (better reflecting the 2-adic representation).

As an example, $16$ (decimal representation) is represented in (reversed) binary as

00001

and the number $1001$ (base ten) is

1001011111

(i.e. $1+\square+\square+8+\square+32+64+128+256+512 $)

It doesn't hurt to add some more zeros (just like changing $234_{10}$ to $000234_{10}$), and represent the number as

10010111110000000000000000000000000000000...

We add the zeros on the right because we have flipped the representation, and put the least significant digit on the left.

---

Consider now the $101$ balls, and consider their weights.

The problem remains the same if the weight of the lightest ball is subtracted from each ball, so we do that. There is now one ball with weight $0$ (the lightest one).

We want to prove that all the balls have the same weight. We will prove this by contradiction.

We begin by assuming we have at least one non-zero weight value, and we write all the values under each other in "alphabetic order", (increasing if read as a left-to-right represention), for instance:

0000000000000000000000000000000000000000000000000000
0000000000000000000000010001101010000000000000000011
0000000000000000101001110101001110110100000000000000
0000000000000000110010111101000000000000000000000000
0000000000000000111011111101011100010100001000001000

(and so on, if there are more such numbers).

We fill in enough zeros on the right of each number (as discussed above) to match the largest number (without affecting the values of the numbers).

Now we find the first column that is not all '0's. We call that the critical column. (Note that such a column must exist, or else all of our numbers are identical.)

We count the total number of 1s in the critical column.

Then we decide which ball to remove from the set.

• If there are an odd number of 1s, we remove the first entry (which has a 0 in the critical column, because our first entry is all 0s).

• If there are an even number of 1s, we remove the last entry (which has a 1 in the critical column, because we arranged the numbers in "increasing alphabetical order", and we picked a column that was not all 0s).

In either case, we are left with an even number of balls which have in total an odd number of 1s in the critical column. Now we try to divide them in two groups of same total weight.

• One group will have an odd number of 1s in the critical column, so its sum will also have a 1 in the critical column.

• The other group will have an even number of 1s in the critical column, so its sum will have the 0 in the critical column.

(Remember, the critical column is the least-significant digit that is non-zero, so there are no carries that could affect the sum.)

Thus the sums of the two groups cannot be the same (they have different binary representations), and our assumption that we have any non-zero weight values is incorrect.

So all the balls must have 0 weight, which means they are all the same weight as the lightest ball.

$\square$

Answer 5

If we first suppose that your initial number of pounds for each ball is the same, the total weight of all 101 balls is equal to: 101 * w, w being the weight that each individual ball matches. If your next move is to remove one ball from the stack, then the weight of the remaining balls is: 101w - 1w, which is the same as: 100w. If you then separate the group of balls into two pairs, containing the same number of balls, each group weights: 100w/2, which is equal to: 50w. Because 50w is equal to 50*w (the weight from the other group) due to your statement (that one group weights the same as the other), then the theory that all balls have the same weight holds. Therefore, proving that each of your 101 balls possibly weights the same, according to your experimentations.