[seqfan] Re: Puzzle

Charles Greathouse charles.greathouse at case.edu
Wed Oct 16 06:23:42 CEST 2013

Well, we must specify that the subset is nonempty else this is uniformly 0.
In that case a(1) = 1, of course, since 1 divides anything. Clearly a(n) >=
n, since you can always choose n-1 1s and not get a sum divisible by n.
Suppose you have n numbers with no nonempty subset summing to 0 mod n. Then
by the pigeonhole principle at least two of k_1, k_1 + k_2, ..., k_1 + k_2
+ ... + k_n are equal mod n. Then simply remove the duplicates and you have
a nonempty subset summing to 0. So a(n) = n.

One of the less-obvious definitions of A000027, I suppose?

Charles Greathouse
Case Western Reserve University

On Wed, Oct 16, 2013 at 12:00 AM, David Wilson <davidwwilson at comcast.net>wrote:

> (I don't know the answer)
> Given integer n, how large must a set S of integers be to guarantee that
> the
> sum of some subset of S is divisible by n?
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list