# A Booty Division Theorem

**URL:** <https://forum.beeminder.com/t/a-booty-division-theorem/5492>\
**Category:** Buzzles\
**Created:** [June 26, 2019, 8:30am UTC](https://forum.beeminder.com/t/a-booty-division-theorem/5492 "2019-06-26T08:30:47Z")\
**Posts on this page:** 1\
**Showing post:** 12

<div class="post-metadata">

**Author:** ![zzq](https://sea1.discourse-cdn.com/flex019/user_avatar/forum.beeminder.com/zzq/32/6471_2.png) [@zzq](https://forum.beeminder.com/u/zzq)\
**Post date:** [July 13, 2019, 12:46pm UTC](https://forum.beeminder.com/t/a-booty-division-theorem/5492/12 "2019-07-13T12:46:06Z")

</div>

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:

> [@zzq](#):
>
> 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).

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

---

_[View the full topic](https://forum.beeminder.com/t/a-booty-division-theorem/5492)._