home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9566 < prev    next >
Encoding:
Internet Message Format  |  1992-07-26  |  1.8 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!uakari.primate.wisc.edu!usenet.coe.montana.edu!ogicse!das-news.harvard.edu!husc-news.harvard.edu!tara!fry
  2. From: fry@tara.harvard.edu (David Fry)
  3. Newsgroups: sci.math
  4. Subject: Re: A Divisibility Problem
  5. Message-ID: <1992Jul27.005128.14212@husc3.harvard.edu>
  6. Date: 27 Jul 92 04:51:28 GMT
  7. References: <9207270341.AA10422@.euclid.uoregon.edu.>
  8. Organization: Harvard Math Department
  9. Lines: 32
  10. Nntp-Posting-Host: tara.harvard.edu
  11.  
  12. In article <9207270341.AA10422@.euclid.uoregon.edu.> s42234@DUCVAX.AUBURN.EDU (M Johnson) writes:
  13. >
  14. >HI, I encountered a problem relating to the divisibility of a sum of integers
  15. >as follows, and I wonder whether the following is true:
  16. >
  17. >Given  N > 1  positive integers, it is always possible to find a subset of
  18. >of the set of N positive integers such that its sum is divisible by N.
  19. >
  20. >
  21. >Is this true? Thanks for your answer.
  22.  
  23. I hope this isn't a homework problem, but...
  24.  
  25. This is true.  Imagine adding the numbers up one by one, and writing
  26. down, after adding each number, the remainder left over when you divide 
  27. the running sum by N.
  28.  
  29. 1) If you ever get a remainder of 0, then you've found a subset that
  30. is divisible by N.  Suppose that this never happens.
  31.  
  32. 2) If you ever write down a remainder that you've written down before,
  33. then you must have in the meantime added a subset that is divisible
  34. by N.  Suppose that this never happens.
  35.  
  36. Then, when you finish, you must have written down N distinct remainders
  37. (numbers between 0 and N-1), none of which is 0.  This is impossible,
  38. so one of 1) or 2) must have happened.
  39.  
  40. David Fry                                  fry@math.harvard.EDU
  41. Division of Applied Sciences               fry@huma1.bitnet
  42. Harvard University                      ...!harvard!huma1!fry
  43. Cambridge, MA  02138            
  44.