You have an odd number of tokens whose weights are known whole numbers, and they don't all have the same weight. Show that there's a token you can remove so that the remaining tokens can't be split into two equal-size sets that have the same total weight.
Mathier bonus questions:
The weights are instead positive rational numbers.
The weights are instead positive real numbers.
Show that this doesn't necessary hold for an Abelian group, where weights are non-identity elements that are summed with the group operation.
Answer
To split it in two equal sets, the total must be even. If you start with an even total, just remove an odd weight, the total becomes odd and can't be split in two equal sets any more. If you start with an odd total, remove an even weight.
If all weights are even or all are odd, you'll need to do the following: Write down the weights in binary. Ignore the least significant bits that are equal among the weights. The operation is equivalent to subtracting a constant value of all weights and divide all weights by the same power of 2. Neither operation affects the balance since there are the same number of weights on both side. After this operation you are guaranteed to have even and odd weights and you can then apply the initial method above. Note that you don't actually change the weights, you just change the scale to measure them.
If you have rationals, you can multiply all weights by the smallest multiple of their denominators. You then have all integer weights.
No comments:
Post a Comment