1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ I'm not sure what's so 'unintuitive' to you about the given solution... is there a specific step that seems unnatural? $\endgroup$
    – Deusovi
    Commented Jun 19 at 16:31
  • $\begingroup$ @Deusovi , I can understand the solution now that I have read it. It surely won't have struck me to solve it this way. I teach kids in the 7th to 10th grade and they won't have been able to solve it if this was the only method to solve it. So, I seek other methods. $\endgroup$ Commented Jun 19 at 16:34
  • 1
    $\begingroup$ This seems better suited for matheducators.stackexchange.com, though you should outline your goals and what you've considered so far $\endgroup$
    – xnor
    Commented Jun 19 at 20:34
  • $\begingroup$ As a comment, I know the following variant of the problem: $n,k$ being nonnull integers, consider a set of $nk+1$ balls of real-valued weights such that whenever we remove one ball, the remaining balls can be partioned into $k$ subsets of $n$ elements with equal total weights. Then all balls have same weight. But the answer I know requires math that is a bit more advanced. $\endgroup$
    – Plop
    Commented Jun 22 at 10:52
  • 1
    $\begingroup$ I agree that the 7th to 10th grade range is going to have a hard time with this proof, but I also think that the formulation as written is about as close to their grade level as you can expect to get. For them to follow the explanation at all would be pretty surprising to me, for them to come up with it themselves would indicate you have a progidy or a cell phone involved. $\endgroup$
    – kagami
    Commented Jun 23 at 13:04

5 Answers 5

6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

(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.)

$\endgroup$
2
  • 1
    $\begingroup$ How strong of a restriction on the field do you need? The proof can easily be adjusted to work for $\mathbb{Q}$, and I think the result should hold for $\mathbb{R}$ $\endgroup$ Commented Jun 21 at 11:35
  • $\begingroup$ @ralphmerridew The same proof (carefully worded) works fine in any abelian group without odd torsion. But that is not the only restriction - for instance for just 5 balls, the only counterexamples occur with elements of orders 3 or 5. I don't know the full characterization (and found it interesting enough to post it at math.se here: math.stackexchange.com/questions/4935246/…). If you have any insights, let me know :) $\endgroup$ Commented Jun 21 at 11:42
1
$\begingroup$

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...

$\endgroup$
7
  • 1
    $\begingroup$ Your subtraction to reach (14) went wrong. Indeed, something must have gone wrong, since your argument never used thst you can divide by 5. (It must do that at some point, since there is such a solution with all different weights in $\mathbb{Z}/5\mathbb{Z}$.) $\endgroup$ Commented Jun 20 at 21:29
  • $\begingroup$ @TimSeifert Can you explain how it went wrong? And give an example of a solution with all different weights? $\endgroup$ Commented Jun 21 at 15:59
  • 1
    $\begingroup$ The correct subtraction yields c-e=e-d, which is different to yours! For an example, note that Z/5Z only has 5 elements, so there is only one possible example. It is not that hard to check that this actually works :) $\endgroup$ Commented Jun 21 at 16:13
  • 1
    $\begingroup$ @TimSeifert I'm not enough of a mathematician to know what $\mathbb{Z}/5\mathbb{Z}$ means. I see the error in my subtraction now that you pointed it out, but I don't see how there can be any solution with differing weights, based on the proof given in the initial post. That proof seems to work just as well for 5 balls as for 101. I'm hopeful that I can amend my answer to fix the subtraction error and still provide a solution to the problem, but if there truly is a solution with 5 differing weights, then please indicate what it is, so I don't waste my time try to prove something incorrect. $\endgroup$ Commented Jun 27 at 16:48
  • $\begingroup$ I'm sorry that I was not clear. The notation $\mathbb{Z}/5\mathbb{Z}$ refers to the integers "modulo 5" as in en.wikipedia.org/wiki/Modular_arithmetic. That is, we identify all integers that differ by multiples of 5, which leaves us with only 5 groups (parametrized by their possible remainders 0,1,2,3 and 4, say). On these five (so-called) cosets we can then perform all the usual arithmetic operations and obtain a number system that shares many properties with the more usual down-to-earth sets such as $\mathbb{Z}, \mathbb{Q}$ or $\mathbb{R}$. ... $\endgroup$ Commented Jun 27 at 17:18
1
$\begingroup$

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$

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ yes, if all the balls weigh the same the puzzle works. But demonstrating that is easy. The questions asks to prove the other way around: if the puzzle works does this mean the balls all must be the same weight? Why? $\endgroup$ Commented Jun 25 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.