

Title: Set of 2n1 integers Post by Eigenray on Dec 23^{rd}, 2005, 10:39am Show that any set of 2n1 integers always has a subset of size n, the sum of whose elements is divisible by n. 

Title: Re: Set of 2n1 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 nonoverlapping 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 2n1 integers Post by Icarus on Dec 23^{rd}, 2005, 5:13pm on 12/23/05 at 14:03:41, SMQ wrote:
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 2n1 integers Post by SMQ on Dec 23^{rd}, 2005, 8:05pm OK, after choosing nonoverlapping 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 2n1 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(2n1, n), S_{k} > 0, where S_{k} is the sum of kth subset of n numbers, modulo n. Then, by Fermat’s theorem, S_{k}^{n1} = 1. Therefore, The r.h.s. equals 1 modulo n (why?). In the l.h.s. every of 2n1 numbers appears C(2n2, n1) times, which is 0 modulo n (why?). A contradiction. 

Title: Re: Set of 2n1 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 ChevalleyWarning Theorem (http://en.wikipedia.org/wiki/ChevalleyWarning_theorem) 

Title: Re: Set of 2n1 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 

Title: Re: Set of 2n1 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 2n1 problem is harder than the above problem, which has a short and sweet solution. Am I missing something? 

Title: Re: Set of 2n1 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 2n1 integers Post by Eigenray on Feb 22^{nd}, 2008, 9:50am on 12/24/05 at 05:37:29, Barukh wrote:
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 ksubsets S of (p+k1) 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 2p1 independent choices that satisfy 2 conditions[/hide]. 

Title: Re: Set of 2n1 integers Post by Eigenray on Feb 22^{nd}, 2008, 3:38pm I think Barukh's argument generalizes to show: Suppose pk, C(n, k) is not divisible by p, and p  (n+1)C(np, kp). 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(nt, kt) 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+p1. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 