wu :: forums
« wu :: forums - Set of 2n-1 integers »

Welcome, Guest. Please Login or Register.
Dec 7th, 2019, 2:47pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Eigenray, SMQ, william wu, Icarus, towr, Grimbal)
   Set of 2n-1 integers
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Set of 2n-1 integers  (Read 6217 times)
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Set of 2n-1 integers  
« on: Dec 23rd, 2005, 10:39am »
Quote Quote Modify 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: male
Posts: 2084
Re: Set of 2n-1 integers  
« Reply #1 on: Dec 23rd, 2005, 2:03pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Set of 2n-1 integers  
« Reply #2 on: Dec 23rd, 2005, 5:13pm »
Quote Quote Modify 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: male
Posts: 2084
Re: Set of 2n-1 integers  
« Reply #3 on: Dec 23rd, 2005, 8:05pm »
Quote Quote Modify 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: male
Posts: 2276
Re: Set of 2n-1 integers  
« Reply #4 on: Dec 24th, 2005, 5:37am »
Quote Quote Modify 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: male
Posts: 1321
Re: Set of 2n-1 integers  
« Reply #5 on: Dec 24th, 2005, 10:25am »
Quote Quote Modify 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: male
Posts: 2276
Re: Set of 2n-1 integers  
« Reply #6 on: Dec 25th, 2005, 4:50am »
Quote Quote Modify 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: male
Posts: 405
Re: Set of 2n-1 integers  
« Reply #7 on: Feb 28th, 2006, 3:22pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Set of 2n-1 integers  
« Reply #8 on: Feb 28th, 2006, 3:42pm »
Quote Quote Modify 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: male
Posts: 1948
Re: Set of 2n-1 integers  
« Reply #9 on: Feb 22nd, 2008, 9:50am »
Quote Quote Modify 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: male
Posts: 1948
Re: Set of 2n-1 integers  
« Reply #10 on: Feb 22nd, 2008, 3:38pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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