Author |
Topic: Set of 2n-1 integers (Read 8587 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Set of 2n-1 integers
« on: Dec 23rd, 2005, 10:39am » |
 Quote  Modify
|
Show that any set of 2n-1 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 2n-1 integers
« Reply #1 on: Dec 23rd, 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 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
|
|
IP Logged |
--SMQ
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Set of 2n-1 integers
« Reply #2 on: Dec 23rd, 2005, 5:13pm » |
Quote Modify
|
on Dec 23rd, 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 2n-1 integers
« Reply #3 on: Dec 23rd, 2005, 8:05pm » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Set of 2n-1 integers
« Reply #4 on: Dec 24th, 2005, 5:37am » |
Quote Modify
|
The proof for the prime n may be as follows.
Assume to the contrary that for k = 1, …, C(2n-1, n), Sk > 0, where Sk is the sum of k-th subset of n numbers, modulo n. Then, by Fermat’s theorem, Skn-1 = 1. Therefore,
 Skn-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.
|
| « Last Edit: Dec 25th, 2005, 8:31pm by Icarus » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Set of 2n-1 integers
« Reply #5 on: Dec 24th, 2005, 10:25am » |
Quote Modify
|
I have seen a proof (I think due to Noga Alon) for the prime number case which uses the Chevalley-Warning Theorem
|
| « Last Edit: Dec 24th, 2005, 10:25am by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Set of 2n-1 integers
« Reply #6 on: Dec 25th, 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 2n-1 integers
« Reply #7 on: Feb 28th, 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 2n-1 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 2n-1 integers
« Reply #8 on: Feb 28th, 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 2n-1 integers
« Reply #9 on: Feb 22nd, 2008, 9:50am » |
Quote Modify
|
on Dec 24th, 2005, 5:37am, Barukh wrote: Skn-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
S (S)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 here. Hint: We have to make 2p-1 independent choices that satisfy 2 conditions.
|
| « Last Edit: Feb 22nd, 2008, 9:51am by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Set of 2n-1 integers
« Reply #10 on: Feb 22nd, 2008, 3:38pm » |
Quote Modify
|
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  k+p-1.
|
| « Last Edit: Feb 22nd, 2008, 3:45pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print