perplexus.info :: Just Math : Find a subset

Find a subset (Posted on 2005-08-24)

Given N integers a₁, a₂, ... a_N 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 b₁=a₁, b₂=a₁+a₂, ... up to b_N=a₁+a₂+...+a_N. Let c_i=b_i mod N.
If some c_i=0, then a₁+a₂+...+a_i is a solution.
On the other hand, if no c_i=0, at least two of the c_i values must be the same, since there are just (N-1) possible nonzero values. If c_i=c_j, then a_i+1+a_i+2+...+a_j is a solution.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
A particular case	Old Original Oskar!	2005-09-01 16:24:59
re: Solution	Tristan	2005-08-26 09:22:15
Solution	Tan Kiat Chuan	2005-08-26 04:20:11
No Subject	Josh70679	2005-08-24 22:19:51
re: what is a subset?	Old Original Oskar!	2005-08-24 19:09:05
what is a subset?	Percy	2005-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 (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info