5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 1, 1, 1, 1, 3?​ $\endgroup$ – Lopsy Jan 15 '15 at 0:38
  • $\begingroup$ @Lopsy Whoops, I forgot the condition that you must partition into two equal-size sets. Thanks for catching that. $\endgroup$ – xnor Jan 15 '15 at 0:45
  • $\begingroup$ I'm confused. If I have tokens that weigh 2, 3, 4 and I remove any one of them, the remaining two tokens can't be split into equal-sized groups of the same weight... $\endgroup$ – EFrog Jan 15 '15 at 6:07
  • $\begingroup$ @EFrog That's fine, the claim is there will be at least one such choice of token. $\endgroup$ – xnor Jan 15 '15 at 6:11
  • 1
    $\begingroup$ Essentially the same problem (with real number weights) in Math.SE, answered: math.stackexchange.com/questions/1002267/… Comments include perhaps a simpler answer to the integer case. $\endgroup$ – JiK Jan 15 '15 at 9:35
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I fixed the problem by adding the condition that the split must put the same number of weights on each side. $\endgroup$ – xnor Jan 15 '15 at 0:50
6
$\begingroup$

Consider an arbitrary system of non-negative integer weights.

Repeat

  1. If all weights are even, then divide each weight by 2.

  2. If all weighst are odd, then subtract 1 from each weight.

until (at least one weight is even and at least one weight is odd)

Then remove one weight (odd or even) so that the sum of the remaining weights is odd.

$\endgroup$
  • $\begingroup$ 3, 5, 7, 9, 11. According to your rules, I should subtract 1 from each to make 2, 4, 6, 8, 10. Now all are even so divide by 2. 1, 2, 3, 4, 5. If I remove the 5 weight, I can divide the remaining weights equally (2 and 3, 1 and 4). $\endgroup$ – EFrog Jan 15 '15 at 11:00
  • 2
    $\begingroup$ @EFrog Then remove one weight (odd or even) so that the sum of the remaining weights is odd. it works for at least of them, but not necessarily for every one (in your case you could remove any even-weighted token). $\endgroup$ – Cthulhu Jan 15 '15 at 11:25
  • $\begingroup$ @EFrog: But the claim is that you can remove some element so that the remaining tokens can't be split into two equal-size sets that have the same total weight. In your example, we would remove 4 (so that the sum of the remaining elements 1, 2, 3, 5 is odd). $\endgroup$ – Gamow Jan 15 '15 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.