Montreal Math ClubMathematics students in Montreal - Étudiants de mathématiques à Montréal

 Montreal Math Club :: Mathematics :: Problem Solving :: Solved problems Share |

# [SOLVED] 2n+1 integers

AuthorMessage

Posts : 184
Join date : 2009-09-15
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

Descartes

Posts : 100
Join date : 2009-11-05
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" ?

Posts : 184
Join date : 2009-09-15
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.

Euclid

Posts : 49
Join date : 2009-11-06
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 j-th step , the walk cannot go back to any of the previous positions because then we will have a sub-walk 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

Posts : 184
Join date : 2009-09-15
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...

Descartes

Posts : 100
Join date : 2009-11-05
Age : 35
Location : Right behind you

 Subject: Re: [SOLVED] 2n+1 integers   Fri Nov 27, 2009 2:56 am

Posts : 184
Join date : 2009-09-15
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...

Posts : 184
Join date : 2009-09-15
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?

Descartes

Posts : 100
Join date : 2009-11-05
Age : 35
Location : Right behind you

 Subject: Re: [SOLVED] 2n+1 integers   Sun Nov 29, 2009 6:10 pm yes

Posts : 184
Join date : 2009-09-15
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.

Descartes

Posts : 100
Join date : 2009-11-05
Age : 35
Location : Right behind you

 Subject: Re: [SOLVED] 2n+1 integers   Sun Nov 29, 2009 7:04 pm I can't believe that I couldn't see that

Posts : 184
Join date : 2009-09-15
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.

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

 [SOLVED] 2n+1 integers
 Page 1 of 1
 Similar topics
» GCL & COMPANY LAW CASES SOLVED!!!!!!!
» Boilermate runs continually after initial problem solved
» solved scanner

Permissions in this forum:You cannot reply to topics in this forum
 Jump to: Select a forum||--Math Club|   |--Mathematical Sundays|   |--Suggestions|   |--Introduce yourself|   |--Mathematics|   |--Problem Solving|   |   |--Solved problems|   |   |   |--Calculus and Analysis|   |--Combinatorics|   |--Geometry|   |--Number Theory|   |--Probabilities and statistics|   |--Set theory and Topology|   |--Online Resources|   |--Chit chat    |--The Water Cooler    |--Mathematical poems