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.


Related material
Read more...

  • Six integers out of 10: Pigeonhole Principle
  • Pigeonhole Principle (Same sum)
  • Pigeonhole in a Matrix
  • Pigeonhole in Calendar
  • A nice puzzle modeled on the Petersen graph
  • Proizvolov's identity in a game format
  • Pigeonhole with Disjoint Intervals
  • All antichains
  • Euclid via Pigeonhole
  • Light Bulbs in a Circle (an Interactive Gizmo)
  • Seven integers under 127 and their Ratios

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

    Copyright © 1996-2018 Alexander Bogomolny

    71862871