Given a set A ⊂ {1, 2, ..., 100} of ten integers. Prove that it is possible to select two disjoint non-empty subsets of A, S and T, whose members have the same sum.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

Given a set A ⊂ {1, 2, ..., 100} of ten integers. Prove that it is possible to select two disjoint non-empty subsets of A, S and T, whose members have the same sum.

There are 210 = 1,024 subsets of the 10 integers, but there can be only 901 (= 955 - 55 + 1) possible sums, the number of integers between the minimum and maximum sums of ten distinct integers between 1 and 100. With more subsets than possible sums, there must exist at least one sum that corresponds to at least two subsets. Call two subsets with equal sums S' and T'.

Let C = S' ∩ T'; define S = S' - C, T = T' - C. Then S and T are disjoint, and

sum(S)= sum(S' - C)
 = sum(S') - sum(C)
 = sum(T') - sum(C)
 = sum(T' - C)
 = sum(T).

At the req.puzzles archive site, where the problem and its solution came from, it is shown that 9 integers would suffice.


[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]