7
$\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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 1, 1, 1, 1, 3?​ $\endgroup$
    – Lopsy
    Commented Jan 15, 2015 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
    Commented Jan 15, 2015 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
    Commented Jan 15, 2015 at 6:07
  • $\begingroup$ @EFrog That's fine, the claim is there will be at least one such choice of token. $\endgroup$
    – xnor
    Commented Jan 15, 2015 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
    Commented Jan 15, 2015 at 9:35

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I fixed the problem by adding the condition that the split must put the same number of weights on each side. $\endgroup$
    – xnor
    Commented Jan 15, 2015 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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jan 15, 2015 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
    Commented Jan 15, 2015 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
    Commented Jan 15, 2015 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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