wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Set of 2n-1 integers
        
(Message started by: Eigenray on Dec 23^rd, 2005, 10:39am)

Title: Set of 2n-1 integers
Post by Eigenray on Dec 23^rd, 2005, 10:39am

Show that any set of 2n-1 integers always has a subset of size n, the sum of whose elements is divisible by n.

Title: Re: Set of 2n-1 integers
Post by SMQ on Dec 23^rd, 2005, 2:03pm

Well, I don't know how much this actually helps, but here's an inductive proof for composite n:

Let k, 1 < k < n be a divisor of n. Choose any 2n/k - 1 integers from the set. There exists subset of n/k integers whose sum is a multiple of n/k. Remove those n/k integers from consideration and pick any other 2n/k - 1 integers. Continuing like this it is possible to pick 2k - 1 non-overlapping sets of integers each of which sums to a multiple of n/k. But, considering the sums of those 2k - 1 sets, there exists a set of k sets whose sum is a multiple of k. The set of all n integers in those k sets of n/k integers is a multiple of both n/k and k, and therefore a multiple of k*n/k = n.

--SMQ

Title: Re: Set of 2n-1 integers
Post by Icarus on Dec 23^rd, 2005, 5:13pm

on 12/23/05 at 14:03:41, SMQ wrote:

... is a multiple of both n/k and k, and therefore a multiple of k*n/k = n.

if k is relatively prime to n. The proof is still good except for powers of primes, provided it can be shown that the powers of primes also work.

Title: Re: Set of 2n-1 integers
Post by SMQ on Dec 23^rd, 2005, 8:05pm

OK, after choosing non-overlapping subsets, rather than considering the set of the sums of the subsets, consider the set of the sums of the subsets each divided by n/k. Clearly this is still a set of 2k - 1 integers and so must itself contain at least one subset of size k whose sum is a multiple of k. Thus, even for prime powers, the set consisting of all members of those k subsets will contain independent factors of n/k and k, and therefore be a multiple of n.

But without a proof for prime n, there's still no base case for the induction for composite n...

--SMQ

Title: Re: Set of 2n-1 integers
Post by Barukh on Dec 24^th, 2005, 5:37am

The proof for the prime n may be as follows.

Assume to the contrary that for k = 1, …, C(2n-1, n), S_k > 0, where S_k is the sum of k-th subset of n numbers, modulo n. Then, by Fermat’s theorem, S_k^n-1 = 1. Therefore,
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S_k^n-1 = C(2n-1, n).
The r.h.s. equals 1 modulo n (why?). In the l.h.s. every of 2n-1 numbers appears C(2n-2, n-1) times, which is 0 modulo n (why?). A contradiction.

Title: Re: Set of 2n-1 integers
Post by Aryabhatta on Dec 24^th, 2005, 10:25am

I have seen a proof (I think due to Noga Alon) for the prime number case which uses the Chevalley-Warning Theorem (http://en.wikipedia.org/wiki/Chevalley-Warning_theorem)

Title: Re: Set of 2n-1 integers
Post by Barukh on Dec 25^th, 2005, 4:50am

I think the following side problem is relevant here:

Given natural numbers n, m and a prime p, let s = floor(n/p), t = floor(m/p). Prove that

C(n, m) = C(s, t)C(n mod p, m mod p) mod p.

Title: Re: Set of 2n-1 integers
Post by ecoist on Feb 28^th, 2006, 3:22pm

How does this problem differ from the pigeonhole problem:

Given any set of n integers, there exists a subset whose elements sum to a multiple of n.

The comments I read suggest that the 2n-1 problem is harder than the above problem, which has a short and sweet solution. Am I missing something?

Title: Re: Set of 2n-1 integers
Post by Icarus on Feb 28^th, 2006, 3:42pm

Yes - that the set has to have exactly n elements.

For example, consider your result applied to the following sets {1, 2}, {1, 3}. The subset adding to an even number for the first is {2}, while the subset adding to an even number for the second is {1, 3}.

In Eigenray's problem, all the subsets must have exactly n elements.

Title: Re: Set of 2n-1 integers
Post by Eigenray on Feb 22^nd, 2008, 9:50am

on 12/24/05 at 05:37:29, Barukh wrote:

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S_k^n-1 = C(2n-1, n).
The r.h.s. equals 1 modulo n (why?). In the l.h.s. every of 2n-1 numbers appears C(2n-2, n-1) times, which is 0 modulo n (why?).

Hmm... did I think this was obvious 2 years ago? Anyway, we can show by induction that

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_S (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifS)^r = 0 mod p,

where the outer sum is over all k-subsets S of (p+k-1) elements, and r < k, for k=1,...,p.

We can also use the version of Chevalley Warning for simultaneous solutions [link=http://planetmath.org/encyclopedia/ChevalleyWarningTheorem.html]here[/link]. Hint: [hide]We have to make 2p-1 independent choices that satisfy 2 conditions[/hide].

Title: Re: Set of 2n-1 integers
Post by Eigenray on Feb 22^nd, 2008, 3:38pm

I think Barukh's argument generalizes to show:

Suppose p|k, C(n, k) is not divisible by p, and p | (n+1)C(n-p, k-p). Then for any n integers, there is a subset of size exactly k whose sum is divisible by p.

The idea is that p | C(n-t, k-t) for 0<t<p, but not for t=0.

Actually, the above phrasing is stupid, because if the result holds for some n it obviously holds for any larger n. Therefore TFAE:

A) Every set of n integers has a subset of size k whose sum is divisible by p
B) p | k and n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif k+p-1.