 [SOLVED] 2n+1 integers  

Author  Message 

Bruno Admin
Posts : 184 Join date : 20090915 Age : 31 Location : the infinite, frictionless plane of uniform density
 Subject: [SOLVED] 2n+1 integers Wed Nov 25, 2009 12:33 am  
 I gave this one to Mohammad the other day. It is pretty hard.
Suppose you have 2n+1 integers in the range [n, n], and that their sum is 1. Show that you can find a subset of them whose sum is 0.
Last edited by Bruno on Sat Dec 19, 2009 2:33 pm; edited 1 time in total 

 
Mohammad Descartes
Posts : 100 Join date : 20091105 Age : 35 Location : Right behind you
 Subject: Re: [SOLVED] 2n+1 integers Wed Nov 25, 2009 1:14 am  
 Does it use"Chevalley's Theorem" ? 

 
Bruno Admin
Posts : 184 Join date : 20090915 Age : 31 Location : the infinite, frictionless plane of uniform density
 Subject: Re: [SOLVED] 2n+1 integers Wed Nov 25, 2009 1:17 am  
 Haha... no. The other day, in class, I said something equivalent to sin(x/2) = sin(x)/2. Good thing I can laugh at myself a little bit. 

 
peyman Euclid
Posts : 49 Join date : 20091106 Age : 95 Location : dense in the universe
 Subject: Re: [SOLVED] 2n+1 integers Wed Nov 25, 2009 1:51 am  
 here's an observation. I will think more about it later.
rearrange the 2n+1 numbers so that they are alternating in sign and nondecreasing in magnitude. possibly with a tail that ends in all +'s or all 's.
For example (+1, 2, +2, 3,3,3,3) for n=3. Think of this as a "walk" that goes up 1 unit, then down 2 units, then up 2 units, and so on.
Suppose no subset of the numbers has a zero sum. so in particular all numbers are nonzero.
After the jth step , the walk cannot go back to any of the previous positions because then we will have a subwalk that starts and ends at the same position so the corresponding subset of numbers will have a zero sum.
This way the walk gets too big too fast.
Last edited by peyman on Sat Nov 28, 2009 1:45 pm; edited 2 times in total 

 
Bruno Admin
Posts : 184 Join date : 20090915 Age : 31 Location : the infinite, frictionless plane of uniform density
 Subject: Re: [SOLVED] 2n+1 integers Thu Nov 26, 2009 4:55 pm  
 You have a good idea. The solution does not use this exact idea but it's similar... 

 
Mohammad Descartes
Posts : 100 Join date : 20091105 Age : 35 Location : Right behind you
 Subject: Re: [SOLVED] 2n+1 integers Fri Nov 27, 2009 2:56 am  
 

 
Bruno Admin
Posts : 184 Join date : 20090915 Age : 31 Location : the infinite, frictionless plane of uniform density
 Subject: Re: [SOLVED] 2n+1 integers Fri Nov 27, 2009 8:03 pm  
 I think you're looking too far! But maybe you can find a different solution than the one I know...
The solution comes from a simple idea similar to Peyman's... 

 
Bruno Admin
Posts : 184 Join date : 20090915 Age : 31 Location : the infinite, frictionless plane of uniform density
 Subject: Re: [SOLVED] 2n+1 integers Sun Nov 29, 2009 6:09 pm  
 Should I post the solution? 

 
Mohammad Descartes
Posts : 100 Join date : 20091105 Age : 35 Location : Right behind you
 Subject: Re: [SOLVED] 2n+1 integers Sun Nov 29, 2009 6:10 pm  
 yes 

 
Bruno Admin
Posts : 184 Join date : 20090915 Age : 31 Location : the infinite, frictionless plane of uniform density
 Subject: Re: [SOLVED] 2n+1 integers Sun Nov 29, 2009 7:02 pm  
 Order the 2n+1 integers in such a way that the partial sums are always in [n,n] (convince yourself that this is possible). If the partial sums ever hit 0, then we are done. Otherwise the partial sums take on any out of 2n possible values, and hence two of the partial sums have the same value. Now just subtract the first from the second. 

 
Mohammad Descartes
Posts : 100 Join date : 20091105 Age : 35 Location : Right behind you
 
 
Bruno Admin
Posts : 184 Join date : 20090915 Age : 31 Location : the infinite, frictionless plane of uniform density
 Subject: Re: [SOLVED] 2n+1 integers Sun Nov 29, 2009 7:28 pm  
 I can't remember which competition it was on, but it was the least solved problem in the whole competition... It's a pretty simple idea but it's difficult to come up with. 

 
Sponsored content
 Subject: Re: [SOLVED] 2n+1 integers  
 

 
 [SOLVED] 2n+1 integers  
