[seqfan] Re: Puzzle

[Charles Greathouse]

> Ah, but he said set, not multiset.

Sure, but a set in Z is a multiset in Z/nZ. (To be fair, you essentially
pointed this out.)

> But suppose we restrict S to values from 1 to n. Now maybe it gets
interesting.

Hmm. a(n) is only defined for n > 2. Clearly a(n) <= n/2 + 1 by pairing off
1, n-1; 2, n-2; etc.

Oh good, this is already in the OEIS: A034463.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University


On Wed, Oct 16, 2013 at 1:29 AM, <franktaw at netscape.net> wrote:

> Ah, but he said set, not multiset. Of course, it's still n at that point,
> since you can take 1, n+1, 2n+1, ..., n(n-1) + 1.
>
> But suppose we restrict S to values from 1 to n. Now maybe it gets
> interesting.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: Charles Greathouse <charles.greathouse at case.edu>
>
> 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
> Analyst/Programmer
> 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/
>