lotus

previous page: 85 arithmetic/pell.p
  
page up: Puzzles FAQ
  
next page: 87 arithmetic/sum.of.cubes.p

86 arithmetic/subset.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

86 arithmetic/subset.p


Prove that all sets of n integers contain a subset whose sum is divisible by n.

arithmetic/subset.s

Consider the set of remainders of the partial sums a(1) + ... + a(i).
Since there are n such sums, either one has remainder zero (and we're
thru) or 2 coincide, say the i'th and j'th. In this case, a(i+1) +
... + a(j) is divisible by n. (note this is a stronger result since
the subsequence constructed is of *adjacent* terms.) Consider a(1)
(mod n), a(1)+a(2) (mod n), ..., a(1)+...+a(n) (mod n). Either at
some point we have a(1)+...+a(m) = 0 (mod n) or else by the pigeonhole
principle some value (mod n) will have been duplicated. We win either
way.

 

Continue to:













TOP
previous page: 85 arithmetic/pell.p
  
page up: Puzzles FAQ
  
next page: 87 arithmetic/sum.of.cubes.p