Posers and Puzzles

Posers and Puzzles

  1. Joined
    04 Jul '04
    23 Nov '04 22:25
    Seems therere quite a few mathappreciative people here.
    So here is quite elegant problem for them.

    Proove that every set ot ten different numbers (chosen from ste {1,2,...,100}) contains two disjoint nonempty subsets of the same sum.

    Good luck,
  2. DonationAcolyte
    Now With Added BA
    04 Jul '02
    27 Nov '04 19:36
    Let A be a subset of {1,2,...,100} of size 10. Then A has 1022 proper subsets (ie ones which aren't A or empty), and given a proper subset, the sum of its elements must be a positive integer, bounded above by 100*9 = 900. So by the pigeon-hole principle we can find distinct proper subsets B and C with Sum(B) = Sum(C)

    B cannot be a subset of C, because if it was, then Sum(C) >= Sum(B) + x for some x>0 in C\B, so Sum(C) > Sum(B); similarly B doesn't contain C. Hence the sets B\C and C\B are nonempty.
    Sum(B\C) = Sum(B) - Sum(BnC) = Sum(C) - Sum(CnB) = Sum(C\B)

    Therefore B\C and C\B are disjoint nonempty subsets of A with the same sum.
  3. Joined
    04 Jul '04
    28 Nov '04 21:37
    Very clean job, Acolyte!