Little Balls
A friend of mine who plays go a lot found this on her go server. Mathematicians post stuff there, she said, and, being mathematicians, they post problems, not answers.
"You have a collection of 11 balls with the property that if you remove any one of the balls, the other 10 can be split into two groups of 5 that have the same weight. If you assume that all the balls have rational weight, there is a cute proof that they all must weigh the same. Can you find a proof? Can you find a way to extend the result to the general case where the balls have real weights?"
Solving the implied system of 11 equations in 11 unknowns is fairly trivial and gives a proof, but it isn’t “cute” by any stretch. I have been unable to come up with either a cute proof, or a proof, cute or otherwise, which depends on the unknowns being rational.
Does anyone see what I missed?
"You have a collection of 11 balls with the property that if you remove any one of the balls, the other 10 can be split into two groups of 5 that have the same weight. If you assume that all the balls have rational weight, there is a cute proof that they all must weigh the same. Can you find a proof? Can you find a way to extend the result to the general case where the balls have real weights?"
Solving the implied system of 11 equations in 11 unknowns is fairly trivial and gives a proof, but it isn’t “cute” by any stretch. I have been unable to come up with either a cute proof, or a proof, cute or otherwise, which depends on the unknowns being rational.
Does anyone see what I missed?
Yeah, the rational part.
ReplyDeleteHmm as I was reading it I thought, "Huh? They must all be the same weight then..." even before I got to the problem part.
ReplyDeleteSo either I am more of a genius than I realized, or I am skipping a step in my head.
I will ponder for a few more moments but right now I have to catch up on my email accounts... There might be an offshore drilling emergency requiring my attention.
Wabulon,
ReplyDeleteI have to run to the store. I still "see" that it has to be that way, but I'm having trouble pinning down the proof, partly because my son just got back in town and he is climbing all over me.
I think you should be able to do it pretty easily with a proof by contradiction.
I will think about it in the car ride...
OK Wabulon it is taking a ridiculously long time for me to try to do this for the case of 11, so let me do it for 5 and then you can see if it extends. (And yes, feel free to say, "Ha ha, Bob couldn't solve his problem of little balls.")
ReplyDeleteOn a piece of paper draw two columns of two balls each, and then put the fifth ball by itself below them. Label the bottom ball L, denoting that it is the lightest ball of the 5.
Now we know that it must be possible to arrange the other four balls such that the two columns weight the same. Without loss of generality, we will put the second lightest ball into the right column. (It might be tied in weight with the lightest ball.)
CASE 1: Both the balls in the right column are L.
====In this case we're obviously done, because then the two balls in the left column must also weigh L.
CASE 2: Only one of the balls in the right column is L.
====For convenience, label the bottom-right ball L. Then label the top-right ball H1, the bottom-left ball H2, and the top-left ball H3. These are not sorted, by the way; it just means 3 different balls that are all at least as heavy as L.
Now, suppose I swap my bottom ball L with H2. This might make the columns no longer the same weight, because H2 might be greater than L. But we know that I must be able to do some swapping to restore the equality (by assumption).
CASE 2a. I don't need to do any further swapping; the two columns are still the same.
=====In this case, L=H2, and so now we are looking at three Ls with an H3 in the top left and an H1 in the top right. Then do one more swap of the bottom L with either H3 or H1, and then it's obvious they all equal L.
CASE 2b. After the initial swap of L for H2, the left column is lighter than the right, and so I need to do a further swap between the columns to restore balance.
=====You can quickly rule this case out as impossible. Swapping H3 for H1 doesn't help, because it just reverses the imbalance. And if we swap one of the Hs with one of the Ls, then the only way those two columns can be equal is if they all weigh L. But that contradicts our assumption that initially there was an imbalance.
Case 3. The L ball is strictly the lightest.
======Shoot, I am getting bogged down in all the subcases on this one. I'll do part of it at least:
Number the four balls from H1 to H4, where you know that each is strictly heavier than L. Without loss of generality, say H1 is the 2nd lightest ball (might be tied for second with others), and put it in right column.
Now swap L with a ball from the left column. If no further swaps are needed--i.e. if left and right columns are still the same weight--then that means L must have equaled the weight of the ball you swapped out, but that contradicts our assumption in this case.
So, that means you need one more swap to restore the balance. But this is the part where I'm getting bogged down. I can't see how to force that all must weigh L.
=================
Anyway, I think something like this would work for the case of 11 balls, but it would be a much bigger pain. Presumably this is not the "cute" proof that exists.
When I had my immediate flash of intuition that said they must be the same, I was thinking along these lines of swapping the balls, and I quickly kept painting myself into a corner, by switching which ball I pulled out (and then had to be able to swap balls to restore balance). But like I said, I might have been skipping some steps, since I obviously didn't run through all these subcases, I kinda just thought, "This can't work, unless they all weigh the same."
So I cannot give myself credit for guessing the answer, much like Fermat couldn't possibly have done the modern proof of his last theorem on his deathbed in his head.
Bob. nice work. The problem seems to have had an effect on you similar to its effect on me: I couldn't let go of it, and my thoughts seemed to verge on a solution, but never got there. And, no, your approach seems no more likely to end up "cute" than my actual proof (which I take it is the way an AI problem-solving algorithm would have gone about it). We shall no doubt keep trying.
ReplyDeleteGene, bless his crooked little heart, suggested that we simply cheat.
ReplyDeleteGoogle ("11 balls" rational "same weight") yielded:
www.reddit.com/r/math/comments/6c12h/lets_have_a_problem_solving_marathon_post_a/c03h7n4
“Let’s have a problem solving marathon: post a problem and its difficulty level;…”
Submitted 13 March 2008
-----------
It suffices to prove this statement when the ball weights are assumed to be positive integers, as we can just multiply through by denominators.
Suppose that some example exists with the balls not all the same weight. Take an example with minimum total weight W. Say the weights are w1, w2... w_11. Note that they are positive integers, and not all identical, so W>=12.
Considering the condition (mod 2), we find that the sum of any 10 of the weights must be even. Hence any two weights must be congruent (mod 2).
Case a) Every wi is even. Then w1/2, w_2/2,... is another set of differing weights with the same property, but total weight W/2, contradicting the minimality of our example.
Case b) Every wi is odd. Then (w1 + 1)/2, (w_2 + 1)/2, ... is another set of differing weights with the same property, and total weight (W+11)/2 = (W-1+12)/2 <= (W-1+W)/2 = W - 1/2 < W, a contradiction.
We conclude that no such example can exist.
-----------
This follows essentially my line of reasoning; mine petered out when I failed to “take an example with minimum total weight W.” Bob was correct in intuiting proof by contradiction!
"Yeah, the rational part."
ReplyDeleteYou're trying too hard, Sydney.