Beeminder Forum

A Booty Division Theorem

Here’s one from a Beeminder user that I’ve made thoroughly ungooglable:

You and your pirate buddy have 21 vaguely amorphous gold coins you want to divvy up. It turns out that if any one of the 21 coins is missing it’s possible to find a division of the other 20 into two piles of 10 with each pile having the exact same weight. Prove that all 21 coins have identical weight.

If no one objects, I can give a hint/suggestion soon…

No hints yet! Still thinking about this one

1 Like

I gotta say the word “proof” scares me a bit among you stats nerds, having studied math in uni. Let’s give this a try anyways.

If one coin has a different weight, we can only find a split of that coin is taken out, otherwise, there is an imbalance of 9c + x != 10c. Now letˈs imagine we have 19 coins and x and y balance (with the edge case of x==y), then it only balances if we take out a coin of the 19, if we take out either x or y, there is an imbalance. So the magic is in the word “any”. We have to be able to take out any coin and find a balance.

Let’s work it from the end.

A coin taken from the pile of coins has to balance out whether it is in the set of piles or not, this has to hold for every coin, considering we have to be able to remove any coin. Any combination of unequally weighted coins will unbalance by replacing a coin in the stable state by another coin, unless all coins are of the same weight.

If we do not have the 10 vs 10 coin constraint, this does not hold anymore, as we can possibly balance a coin with two others and switch it around if the coin were replaced.

Not sure if this counts as a solution. But it’s definitely a try to make sense of it :smiley:

1 Like

I can prove it with number theory given the additional assumption that the coins each weigh an integral amount, but I haven’t yet been able to expand the proof to the general case.

If the coins have rational weights, we can just rescale to a unit of measure where the weights are integers, so the proof can apply there too.

Under the assumption that all coins have a (positive) integer weight:

First let’s prove that the weights of all the coins must have the same parity (odd or even.)

Let A and B be a pair of coins. The division into two equal piles (of equal weight) of ten coins each when coin A is removed has each pile weighing (X - A)/2, and when B is removed it’s (X - B)/2. Both these are the sum of 10 integers, and so both are integers themselves. Thus X - A and X - B are both even numbers, so (X - A) - (X - B) = B - A is an even number. As the difference in weight between A and B is even, A and B must have the same parity.

We found that all the differences in weights between pairs of coins are even. But are any of those differences equal to 2 mod 4? No, and for much the same reason. For any two coins weighing A and B, (X - A)/2 and (X - B)/2 are both the sum of ten integers of the same parity, and so are both even (the sum of any ten odd numbers is even, and so is the sum of any ten even numbers.) So X - A and X - B are each equal to 0 mod 4, and so their difference, (X - A) - (X - B) = B - A is also equal to 0 mod 4.

So all pairs of coins must be a multiple of 4 apart in weight. We can continue up the powers of two in this way. By induction:
If for a certain n, the difference in weight between any two coins is equal to 0 mod 2^n, then by the same logic as above, for any two coins A and B, the piles of ten coins whose weights are (X - A)/2 and (X - B)/2, being the sum of ten numbers which are equal mod 2^n, are equal to 0 mod 2^(n+1) [Edit: this part is not correct as written, see here for an explanation.], and so (X - A) - (X - B) = B - A is also equal to 0 mod 2^(n+1).

Thus by induction, all differences in weight between pairs of coins must be equal to 0 mod 2^n for all positive n. (Equivalently, for all n the weights of all coins must be equal mod 2^n.)

The differences in weight between any given pair of coins obviously can’t be more than X (the total weight of all the coins.) So we just need to choose an n such that 2^n > X, and we then know that all differences in weight are natural numbers less than 2^n which are equal to zero mod 2^n, which means that they are all zero.

Having proved that all weight differences between pairs of coins are zero, all the coins are of the same weight.

Q.E.D.

2 Likes

@mufflon, I think you’ve proved it for the case that at least 20 of the coins all weigh the same and it’s definitely progress on making sense of it!

For an almost fully general proof, I think @zzq has nailed it. I think I have a version of that parity argument that’s simpler. Either way, I am very impressed. I did not come up with the idea for that on my own.

I also spent a long time trying to extend the proof to the case of real-valued weights and believe I finally did it and that it’s not actually too hard in retrospect.

I plan to post my write-up of the solution in a couple more days!

Definitely not sure if I’m smart enough to get this.

But if neither an odd nor an even amount of coins can be of different weight, the only remaining amount of coins that satisfies the problem is 0 difference in coins. But this is probably not formal enough.

1 Like

Informal is ok by me, this being just for fun. But I think I’m not smart enough to be convinced by your proof yet. I think I’d need it more spelled out how we can be sure that an even (or odd) number of coins can’t be different weights, and what that means exactly – like each of the coins in the some subset is a distinct weight and different from the ones outside that subset, which are all identical?

heh. Ok let’s cut the not smart enough stuff.

Each coin must replace each coin in the set of coins and a permutation of the remaining coins must exist that is stable. With the constraint of 10:10 splits, taking any coin and replacing it with the holdout coin means that we have to find a new stable permutation. Considering that every coin must be replaceable by the holdout coin and a permutation has to be possible, we can look at two cases:

There is equilibrium with 19c and two other coins. If these two coins are the same weight but not c, there is only equilibrium if both coins are in the piles on opposing sides. If one of the non-c coins is held out, equilibrium is not possible. This holds for any even number on non-c coins.

The next case is considering that we have three non-c coins, equilibrium can only exist, if these coins are themselves in equilibrium and one of the coins is held out. This holds for any odd number.

Ironically, these cases are actually the same: 3c and 18 non-c coins is the same as 18c and 3 non-c.

If these c coins are different weights, they still have to balance, regardless of the replacement, since the held out coin has to replace any other coin and a permutation has to be possible.

Since neither even nor odd replacements of another weight work, it follows that all coins must be of the same weight.

Had to figure out the spoiler :sweat_smile:

Here’s my writeup of a solution! It’s quite similar to @zzq’s solution for the case of integer weights.

The first thing to notice is that it doesn’t matter whether the weights are given in ounces or metric tons or anything else. Let’s pick nanograms so we can express all of them as integers! Ok, this is math, not reality, so even expressing the weights as numbers of atoms need not yield whole numbers. But if we prove it’s true when we round the weights to the nearest nanogram then we’re basically there. We’ll come back to the non-integer weights question.

Terminology

Call a set of coins panpartitionable if, for every coin in the set, when you remove it there exists a partitioning into two equal-sized subsets of equal total weight. (Only odd-numbered sets of coins can be panpartitionable since you need the number of coins to be even when you remove one.) Next term: A set of coins is homogeneous if they all have identical weight.

So we’re proving that if a set of coins is panpartitionable then it’s homogeneous.

The case of integer weights

Changing the weight units is just saying we can multiply all the weights by any number. We can also add or subtract the same number from all the weights. Any two piles of coins that weigh the same will still weigh the same if every coin has a constant added to it. And two piles that don’t weigh the same still won’t. Neither panpartitionability nor homogeneity changes when we translate and scale the weights.

We’ll take advantage of that by first subtracting the weight of the lightest coin from all the coins. Of course if all the weights are the same then doing that makes them all weigh zero! So assume they’re not all the same and we’ll try to find a contradiction.

After adjusting the weights so the lightest one weighs zero, and assuming they don’t all weigh zero, suppose that all the weights are even. Then we can divide them all by 2. If they’re still all even, do it again until at least one is odd.

Interlude: A review of adding even and odd numbers

  1. An even number plus or minus an even number must be even.
  2. An even number plus or minus an odd number is odd.
  3. An odd number plus or minus an odd number is even.

(In other words, adding or subtracting an odd number toggles the oddness; adding or subtracting an even number doesn’t.)

Now we’ll show that the total weight of all the coins must be even… and also odd.

The first step: notice that if you remove any coin then the remaining total weight must be even. Why? Because if it’s odd then you can’t put the coins in two equal-weight piles. Whatever the weight of one pile, w, two of those piles must weigh 2w, which is even. (Twice any integer is even.)

Great, so remove the zero-weight coin. The remaining weight, which is to say the total weight, must be even.

Now remove an odd-weighted coin (the one that must exist unless all the weights are zero). The remaining weight must be even so add that odd number back and the total weight must be odd!

That’s our contradiction so our assumption that not all the coins weighed the same was wrong.

The case of rational weights

If the weights are all rational then just multiply them all by their least common denominator to make them all be integers. Done.

The case of irrational weights

By the density of the rationals in the reals, if a weight isn’t rational we can pick a rational weight arbitrarily close to it. In less mathy terms: If the coins don’t each weigh a whole number of grams we can round up to the next higher number of grams and be off by less than a gram. And we can go ever finer – milligrams, micrograms, nanograms, picograms – and be off by as little as we like.

Back to the mathy version, we can pick an arbitrarily small positive epsilon and add amounts strictly less than epsilon to each coin to make them rational. Imagine augmenting all the coins with those tiny amounts.

The rational-valued augmented coins may not be panpartitionable but they are epsilon-panpartitionable. Namely, for any missing coin, however the original real-valued coins were partitioned, those same piles of now-augmented coins weigh within epsilon of each other. (Or within n/2 times epsilon if every coin in one pile was maximally augmented and every coin in the other was minimally augmented. But we can just start with an epsilon that’s n times smaller and, voila, the piles are within epsilon.)

Since those piles weigh within epsilon of each other for every positive epsilon, they must weigh the same. If they didn’t weigh the same then that would mean there was some positive delta that’s the difference between the piles’ weights. Pick epsilon smaller than that and we’d have a contradiction. (To spell out the contradiction: the difference in the piles’ weights is some positive number delta, but also strictly less than delta.)

So that means the rational-valued augmented coins are panpartitionable, which means they’re homogeneous. If the augmented coins are homogeneous then the irrationally-weighted coins are within epsilon of each other. (Recall that the tiny augmentations are all less than epsilon.)

And since they’re within epsilon for every positive epsilon, they must be homogeneous. Otherwise, similar to above, we could take epsilon to be smaller than the smallest difference between two of them and we’d have a contradiction.

So that’s it. Any real-valued coins that are panpartitionable must be homogeneous. Q.E.D.

2 Likes

Reading this write up made me realize something quite important about my solution.

You see, I too initially started my proof by pointing out that the property in question (what @dreev called panpartitionability) is invariant under affine transformations (multiplying by and/or adding the same amount of weight to each coin.) This seemed like the obvious place to start.

Then I wrote my proof, and when I got to the end I realized that I hadn’t actually used this invariance at all in my proof. As I didn’t need it, and went back and edited it out.

Unfortunately, I did need it. Without that, my proof has a fatal (but fixable) flaw. Can you spot it? It’s this line:

This is clearly and utterly wrong. Why would it be true? Take, for instance, the set of numbers 1 1 1 1 1 1 1 1 1 5 (nine ones and a five.) That’s a set of ten numbers that are all equal mod 2^2 (that is, mod 4), whose sum is 14, which is not equal to 0 mod 2^3 (that is, mod 8.).

Of course, what I was thinking when I wrote that was that an affine transformation can easily solve that problem. It can! But I didn’t write that down, and so I ended up thinking that I didn’t use the invariance property, which I then erased.

If, up front, we subtract the weight of the smallest coin from all the coins (as @dreev does in his solution), then at least one coin weighs 0, which is of course equal to 0 mod 2^n for all n, so those ten numbers (at least one of which is the zero) which are all equal mod 2^n are actually all equal to zero mod 2^n, and so their sum is too.

This fixes my proof perfectly well. That said, @dreev’s proof is that bit simpler and more direct, because instead of climbing the tower of powers of two, it cuts to the chase and divides by a high enough power of two upfront.

(Also, the proof for the case of irrational weights is very clever, and neatly extends the solution to the general case of the real numbers.)

2 Likes

Here is an entirely different solution

It uses linear algebra. Also the term “coins” is replaced by “elephants” and solution is for general odd n # of elephants/coins (n=21 for original problem):
https://etherpad.net/p/azas_elephant

1 Like

A comment on @dreev’s solution

For the step “The case of irrational weights”, we can make use of the linear-algebraic (LA) solution posted above (https://etherpad.net/p/azas_elephant). In the LA solution, we formulate the problem as Ax=0, where A is a matrix of rational numbers (integers in fact) and x is the vector of weights.
Any x satisfying Ax=0 is said to be in the null space. Now, suppose we know the problem is solvable assuming rational weights but we’re not sure when irrational weights are allowed. First, to be precise, we consider the vector space (https://en.wikipedia.org/wiki/Vector_space) of 21-dimensional vectors with rational components over the field (https://en.wikipedia.org/wiki/Field_(mathematics)) of rational numbers (i.e. scalars are rational). Call this vector space V_rational. We know that in this vector space, A is rank 20 (since it has only multiples of the vector of all 1s in the null space). Now determinants and elementary row operations on A only involve rational numbers. Thus, it follows easily that A is rank 20 under a new vector space V_real, of 21-dimensional vectors with real components over the field of real numbers (i.e. scalars are real). That implies all solutions (elements in null space) are real multiples of the vector of all 1s. QED

2 Likes

@mufflon, I read your solution but had a few questions/concerns. In the case of 19 equal of weight c coins and 2 coins of weight d <> c, you say that equilibrium is not possible and that the argument extends to any even number of coins weighted d. While true, what is the actual argument proving that (did I miss it?)? Also aren’t we missing other cases like the case of 2 coins of distinct weights d1 <> d2 both not equal to c?

1 Like