4 ms·
It's not out of the box when I apply error correcting codes to a massive range of problems ;) If you like cool problems, here is one I have not found a simple
by SideQuark 4y ago
It's not out of the box when I apply error correcting codes to a massive range of problems ;)
If you like cool problems, here is one I have not found a simple solution for, but I once saw it in a place where a simple solution should exist.
You have an odd number >=3 of items with the property that any time you remove one, there is a way to split the remaining items into two equal count piles of equal weight. Show all items have the same weight.
It's easy for 3 items, A,B,C. Remove C, A balances B, then do A,C, now all equal.
It's easy to check by hand for a few small cases.
I proved it using more advanced stuff from lin alg. But I've never found a simple solution yet.
EDIT: corrected with "equal count piles"
- zem 4y agoI remember that problem from my college linear algebra course! I found a nice simple proof for integers (which was very satisfying!) but afaik you do need heavy linear algebra machinery to generalise it to the reals.
- thaumasiotes 4y ago> I found a nice simple proof for integers (which was very satisfying!) But no such proof can exist because the claim is not true. When you posted your comment, Fetiorin had already given a counterexample.
- SideQuark 4y agoI was pulling the problem from memory. Add the requirement boths sides are same number of items.
- hgsgm 4y agoWhy doesn't the integer proof work on reals?
- zem 4y agoit relied on modular arithmetic
- Fetiorin 4y agoI'm not sure I get the problem. For number 5, I can use items of weights 3 1 1 1 1 and they are not equal. If you remove 3, you get 1+1=1+1 and in case you remove only of 1s, you can split 3 = 1+1+1.
- danbruc 4y agoAnd this generalizes - if n = 2k + 1, 2k times x and once (2k - 1)x can be split into twice kx after removing the single (2k - 1)x or twice (2k - 1)x after removing one x. For k = 1, i.e. n = 3, (2k - 1)x = x. So there is an infinite family of counter examples for all odd n > 3.
- SideQuark 4y agoAh, problem is in memory. Probably also needs two piles of equal number of items :)