Are you interested in a fun math problem? Take a look!
Show that if we have 2009 integers, either one of them is divisible by 2009 or there is a group of these numbers that when you add them up you get a number that is divisible by 2009.
No, this is not homework. Just for fun…
Observing members:
0
Composing members:
0
32 Answers
That’s not fun. It makes my head hurt.
Math and fun. That doesn’t register in my little mind.
I’m just interested to see who can answer this…
Would they have to be unique in the set?
otherwise, wouldn’t this be false if you
a) filled the set with zeros?
b) filled it will (almost) equal parts 1 and -1?
@funkdaddy There is no need for them to be distinct (if that is what you mean).
a) If they are all zero then obviously their sum is zero and zero is divisible by any number, including 2009.
b) It is still possible to show the statement is true even in this case.
Let An={A1,A2,...An}
Let n=2009
Let A=2009
Thus, A2009={20091,20092,...20092009}
A2009 / 2009 = ={11,12,...12009}
Therefore,
All integers are divisible by 2009.
*************************************
Let An={A1,A2,...An}
Let n=2009
Let A=2009
Thus, A2009={20091,20092,...20092009}
SUM[{11,12,...12009}] = 2009*2009 or 2009^2
2009^2 = 4036081
4036081 / 2009 = 2009
Therefore,
The sum of all the integers is divisible by 2009
@blastfamy I am not sure I am following your logic. You need to show no matter what A1, ..., A2009 are there is a sum of them that is divisible by 2009.
How come “all” integers are divisible by 2009?!!! Is this supposed to be a joke?
so, my set is 1000 -1s and 1009 1s, how would any subset add up to a number divisible by 2009? I must be off on my terms and I apologize if I’m just dense. It has been a while but now I’m interested in what I’m missing.
@funkdaddy Simple. Add one -1 and one 1. You get zero and zero is divisible by 2009!
What you are missing is probably the fact that zero is divisible by 2009 (among all other integers). That is because 0 = 2009×0.
No need to apologize.
@BonusQuestion
{A 1, A 2, ..., A n } = The set of integers A, n times. Thus, if A = 2009, then A 2009 = {2009,2009,2009,...2009) where the last integer in the set is the 2009th term.
Then SUM[A 2009 ] = 2009*2009
(2009*2009)/2009 = 2009
this should clear up any misunderstandings about my answer
@bonus ahhh, thank you… the logic makes sense now, as for proving it formally, no idea…
@blastfamy the numbers don’t have to be the same throughout…
@blastfamy OK. You only gave an example of a set of numbers that are divisible by 2009. But how about other sets? You need to show no matter what this set is there is always a few of these numbers that add up to a multiple of 2009.
My brain might have exploded just looking at this thread! I am deeply impressed and humbled by all of you that know what is going on!
@BonusQuestion – well, thinking it through we can assume that if we can’t find a set that some part doesn’t add up to zero or 2009 in a set where the integers all have an absolute value of 2009 or less individually, then it really doesn’t matter how much larger you make the numbers, you’re essentially just increasing (or decreasing) by some multiple of 2009, correct?
So, put another way, whether I use 3 or 2012, or 4021 really doesn’t matter since they would all have an “actual impact” (my own made up technical term) of 3… the same with negative integers…
So we can’t use two numbers with the same absolute value, since we automatically create a subset that adds up to zero, so our dream set would essentially be something that alternates the sign while increasing the integer (1, -2, 3, -4….) but since the set is so large you end up with the last few values being (... -2006, 2007, -2008, 2009) so we have to directly include 2009 in the set, if we push the set one down the number line, we have to include zero. If we just jump over zero and 2009, then we include 2010 add 1 and -2 to get 2009 again. If we add -2010 instead then we can just add 1 and get -2009.
How to write that up in mathematical notation is beyond me.
@funkdaddy You are in the right track. You need to basically look at the remainders of these numbers when divided by 2009.
But you need to also be careful that there might be some of these numbers that have the same remainders. (i.e. some of these numbers might repeat.) So, you can’t assume that they are +/-1, +/-2, +/-3, +/-4, etc. You might have several 1’s or 2’s, etc.
My head hurts even more now. XD
Gotcha, and that’s why you need 2009 integers, otherwise (if the set was smaller) you could use any number of 1’s up to 2008 (or any number of 2008’s) to “avoid” 2009 (and its multiples)...
In my example the set could be one more than half that size I believe… I was wondering why it had to be so big. But I guess that’s off topic and a whole ‘nother story.
Thanks for the problem… as I said earlier it has been a while. Will you post how someone would actually supply a solution concisely for something like this once everyone has had their fun? Do you somehow show the boundaries and go from there?
I will post a solution in a day or so. There might be others who want to think about that. :)
Addendum: @funkdaddy You are right about the fact that we need 2009 numbers. Otherwise take 2008 ones, any sum of these numbers would be positive but less than 2009, hence not divisible by 2009.
Is the number 2009 chosen arbitrarily? I’m starting to suspect that if you have a set of N integers either one of them is divisible by N or there is a sum of a subset of them that is divisible by N.
Suppose I choose a number X1. When I divide it by N I get a remainder R1. For the first number R1 can’t equal zero. Now I choose a second number X2. Now R2 plus R1 can’t equal N or X1+X2 will be divisible by N. I choose a third number X3. No combination of R1-R3 can add up to N. Because all remainders will be less than N, having N numbers less than N will force you to eventually have some combination that will add up to N.
Hmm, I think so anyway. It’s late and I’m going to bed, I’ll have to look at this again in the morning.
@phoenyx No, 2009 is not arbitrary. It is the number of the current year! lol!
You are right. It is true for any N.
It gone be an periodic number.Right.[By pi3,16}
I should think that for any arbitrarily selected group of numbers, the selector can choose to populate the set specifically with numbers that either are or aren’t divisible by 2009.
@Blastfamy elected to do the former, right?
—
arbitrary : based on or subject to individual discretion or preference or sometimes impulse or caprice
so, yes, 2009 is indeed an arbitrary number in this case.
@robmandu True. But the question asks us to show the statement is true no matter what numbers we select.
What phoneyx meant by “arbitrary” was this: “Is this statement true if we replace 2009 by any other positive integer or is this true only for 2009?”
For this specific question the answer is yes, 2009 is indeed an arbitrary positive integer. Meaning that the same statement is true if you replace 2009 by any other positive integer. But this needs a proof and is not obvious.
Cute problem. Let me have a crack at it:
Assume none of the numbers is divisible by 2009, and consider their remainders when divided by 2009 (we say we look at the numbers “mod 2009” in the lingo). Take a random first number from your set. It has some remainder associated to it between 1 and 2008, inclusive (not 0, since it’s not divisible by 2009). Now add random numbers to it one by one from your set, and consider the remainder associated to each sum. By the time you get to your last number, you’ll have hit 2009 different remainders between 0 and 2009. If you hit 0, then you have a collection whose sum is divisible by 2009. If not, then you have the same remainder occurring twice (since if you have 2009 numbers between 1 and 2008, there must be at least two that overlap, by the so called Pigeonhole Principle).
But if the same remainder appears twice, that means that the numbers you added between the first and second occurrence are divisible by 2009, because adding them doesn’t affect the remainder when divided by 2009! And I believe that finishes the proof.
Well, I owed you one. Though I think you did me one better by answering my problem. :)
Number the numbers as n1 to n2009.
Form the sums
n1
n1 + n2,
n1 + n2 + n3,
n1 + n2 + n3 + n4,
and so on.
If one of the sums is divisible by 2009 then we are finished. If all the sums have different remainders when divided by 2009 then one of them must be divisible by 2009, since there are only 2009 possible remainders and we would be done.
Therefore suppose that two of the sums have the same remainder when divided by 2009, say n1+...n6 and n1 +... + n55. The only way that these two sums can have the same remainder is if n7 + ... + n55 is divisible by 2009. The same idea can be applied to any two sums with the same remainder.
QED or whatever
Looking back, I think @finkelitis gave the same proof, but when he says “add random numbers to it one by one,” it seemed to me at first that he was only forming sums of two different numbers, but reading further I am pretty sure that that was not what he intended.
I like math and things like that but this does make my li’l’ ol’ head swim!
Answer this question 
This question is in the General Section. Responses must be helpful and on-topic.
Composing members:
0
