NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/math/9589

Text File | 1992-07-28 | 1.6 KB | 33 lines

Newsgroups: sci.math
Path: sparky!uunet!news.univie.ac.at!news.tu-graz.ac.at!iaik.tu-graz.ac.at!hhassler
From: [e-mail] (Hannes Hassler)
Subject: Re: A Divisibility Problem
Message-ID: <[e-mail]>
Sender: [e-mail] (USENET News System)
Nntp-Posting-Host: fiaikds01.tu-graz.ac.at
Organization: Technical University of Graz, Austria
Date: Tue, 28 Jul 92 11:57:47 GMT
Lines: 21

In article <9207270341.AA10422@.euclid.uoregon.edu.> M.Johnson writes:
>
>I wonder whether the following is true:
>     Given  N > 1  positive integers, it is always possible to find a subset
      of the set of N positive integers such that its sum is divisible by N.
>Is this true? Thanks for your answer.

(1) The claim (trivially) holds if you allow the empty set as subset.
(2) Otherwise, you may argue as follows:  Let a_1,a_2,...,a_N be an enumeration
    of the set, and define S_i := a_1+a_2+...+a_i, for 1<=i<=N.  If all sums S_i
    are different values modulo N, one of them is zero and we are done.  If two
    of the sums are equal, say S_j=S_k modulo N, then their difference is zero
    modulo N and also corresponds to some nonempty subset.  (qed)
(3) A more interesting result is the following:  Given a set of 2n integers, one
    can always choose a subset S of cardinality n and with sum divisible by n.
    The proof of this is left to the reader as an exercise.

*******************************************************************************
Hannes Hassler
*******************************************************************************