Author 
Topic: Set of 2n1 integers (Read 6031 times) 

Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Set of 2n1 integers
« on: Dec 23^{rd}, 2005, 10:39am » 
Quote Modify

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


IP Logged 



SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084


Re: Set of 2n1 integers
« Reply #1 on: Dec 23^{rd}, 2005, 2:03pm » 
Quote Modify

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


IP Logged 
SMQ



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Set of 2n1 integers
« Reply #2 on: Dec 23^{rd}, 2005, 5:13pm » 
Quote Modify

on Dec 23^{rd}, 2005, 2:03pm, 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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084


Re: Set of 2n1 integers
« Reply #3 on: Dec 23^{rd}, 2005, 8:05pm » 
Quote Modify

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


IP Logged 
SMQ



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Set of 2n1 integers
« Reply #4 on: Dec 24^{th}, 2005, 5:37am » 
Quote Modify

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, S_{k}^{n1} = C(2n1, n). 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.

« Last Edit: Dec 25^{th}, 2005, 8:31pm by Icarus » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Set of 2n1 integers
« Reply #5 on: Dec 24^{th}, 2005, 10:25am » 
Quote Modify

I have seen a proof (I think due to Noga Alon) for the prime number case which uses the ChevalleyWarning Theorem

« Last Edit: Dec 24^{th}, 2005, 10:25am by Aryabhatta » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Set of 2n1 integers
« Reply #6 on: Dec 25^{th}, 2005, 4:50am » 
Quote Modify

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.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Set of 2n1 integers
« Reply #7 on: Feb 28^{th}, 2006, 3:22pm » 
Quote Modify

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?


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Set of 2n1 integers
« Reply #8 on: Feb 28^{th}, 2006, 3:42pm » 
Quote Modify

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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Set of 2n1 integers
« Reply #9 on: Feb 22^{nd}, 2008, 9:50am » 
Quote Modify

on Dec 24^{th}, 2005, 5:37am, Barukh wrote: S_{k}^{n1} = C(2n1, n). 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?). 
 Hmm... did I think this was obvious 2 years ago? Anyway, we can show by induction that _{S} (S)^{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 here. Hint: We have to make 2p1 independent choices that satisfy 2 conditions.

« Last Edit: Feb 22^{nd}, 2008, 9:51am by Eigenray » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Set of 2n1 integers
« Reply #10 on: Feb 22^{nd}, 2008, 3:38pm » 
Quote Modify

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 k+p1.

« Last Edit: Feb 22^{nd}, 2008, 3:45pm by Eigenray » 
IP Logged 



