[seqfan] Re: Puzzle
franktaw at netscape.net
franktaw at netscape.net
Wed Oct 16 07:29:40 CEST 2013
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?
>
More information about the SeqFan
mailing list