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.

|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 2^{10} = 1,024 subsets of the 10 integers, but there can be only

Let

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.

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

Copyright © 1996-2018 Alexander Bogomolny64671098 |