Montreal Math Club

Mathematics students in Montreal - Étudiants de mathématiques à Montréal
 
HomeHome  CalendarCalendar  FAQFAQ  SearchSearch  MemberlistMemberlist  UsergroupsUsergroups  RegisterRegister  Log in  

Share | 
 

 [SOLVED] 2n+1 integers

Go down 
AuthorMessage
Bruno
Admin
avatar

Posts : 184
Join date : 2009-09-15
Age : 31
Location : the infinite, frictionless plane of uniform density

PostSubject: [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
Back to top Go down
View user profile http://mathclub.justforum.net
Mohammad
Descartes
Descartes
avatar

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

PostSubject: Re: [SOLVED] 2n+1 integers   Wed Nov 25, 2009 1:14 am

Does it use"Chevalley's Theorem" ?
Back to top Go down
View user profile
Bruno
Admin
avatar

Posts : 184
Join date : 2009-09-15
Age : 31
Location : the infinite, frictionless plane of uniform density

PostSubject: 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. Laughing
Back to top Go down
View user profile http://mathclub.justforum.net
peyman
Euclid
Euclid
avatar

Posts : 49
Join date : 2009-11-06
Age : 94
Location : dense in the universe

PostSubject: 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
Back to top Go down
View user profile
Bruno
Admin
avatar

Posts : 184
Join date : 2009-09-15
Age : 31
Location : the infinite, frictionless plane of uniform density

PostSubject: 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... tongue
Back to top Go down
View user profile http://mathclub.justforum.net
Mohammad
Descartes
Descartes
avatar

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

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

Back to top Go down
View user profile
Bruno
Admin
avatar

Posts : 184
Join date : 2009-09-15
Age : 31
Location : the infinite, frictionless plane of uniform density

PostSubject: 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...
Back to top Go down
View user profile http://mathclub.justforum.net
Bruno
Admin
avatar

Posts : 184
Join date : 2009-09-15
Age : 31
Location : the infinite, frictionless plane of uniform density

PostSubject: Re: [SOLVED] 2n+1 integers   Sun Nov 29, 2009 6:09 pm

Should I post the solution?
Back to top Go down
View user profile http://mathclub.justforum.net
Mohammad
Descartes
Descartes
avatar

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

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

yes Exclamation
Back to top Go down
View user profile
Bruno
Admin
avatar

Posts : 184
Join date : 2009-09-15
Age : 31
Location : the infinite, frictionless plane of uniform density

PostSubject: 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. jocolor
Back to top Go down
View user profile http://mathclub.justforum.net
Mohammad
Descartes
Descartes
avatar

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

PostSubject: Re: [SOLVED] 2n+1 integers   Sun Nov 29, 2009 7:04 pm

lol! I can't believe that I couldn't see that bounce
Back to top Go down
View user profile
Bruno
Admin
avatar

Posts : 184
Join date : 2009-09-15
Age : 31
Location : the infinite, frictionless plane of uniform density

PostSubject: 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. scratch
Back to top Go down
View user profile http://mathclub.justforum.net
Sponsored content




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

Back to top Go down
 
[SOLVED] 2n+1 integers
Back to top 
Page 1 of 1
 Similar topics
-
» GCL & COMPANY LAW CASES SOLVED!!!!!!!
» Boilermate runs continually after initial problem solved
» solved scanner
» CS Executive Module I solved answers

Permissions in this forum:You cannot reply to topics in this forum
Montreal Math Club :: Mathematics :: Problem Solving :: Solved problems-
Jump to: