All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Find a subset (Posted on 2005-08-24) Difficulty: 3 of 5
Given N integers a1, a2, ... aN prove there exists a (non empty) subset whose sum is a multiple of N. (Allow repeated numbers in both the original set and its subsets.)

  Submitted by Federico Kereki    
No Rating
Solution: (Hide)
Consider the numbers b1=a1, b2=a1+a2, ... up to bN=a1+a2+...+aN. Let ci=bi mod N.

If some ci=0, then a1+a2+...+ai is a solution.

On the other hand, if no ci=0, at least two of the ci values must be the same, since there are just (N-1) possible nonzero values. If ci=cj, then ai+1+ai+2+...+aj is a solution.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Some ThoughtsA particular caseOld Original Oskar!2005-09-01 16:24:59
re: SolutionTristan2005-08-26 09:22:15
SolutionSolutionTan Kiat Chuan2005-08-26 04:20:11
Some ThoughtsNo SubjectJosh706792005-08-24 22:19:51
Some Thoughtsre: what is a subset?Old Original Oskar!2005-08-24 19:09:05
Questionwhat is a subset?Percy2005-08-24 18:30:13
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information