I have N + 1 numbers. If I sum any N of them, the sum is divisible by N .
If one of the numbers is divisible by N , must all of the other numbers also be divisible by N ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Nice solution, but you're still using moduli: when you say that the sum is 0 you mean modulo N, so the "intimidating notation" is only implicit.
Log in to reply
Implicit intimidation is always better than explicit for a novice.
Nice solution
Log in to reply
99i94 oo 4k6m4 99i94We are68 kmini668 kill ik kill 'll ooo ji9
Nice and easy to follow
Am I reading this wrong. Take 1, 2, 3, 4, 5, 6. Let N=5. Add the first 5 digits which is 15 and is therefore divisible by N. The remaing 5 digits are not divisible by 5 so in my opinion the answer is No.
Log in to reply
But in your example not all 5 digit combos are divisible by 5
Let's suppose the numbers are a 1 , a 2 , . . . , a N , a N + 1 and without loss of generality let's say that the one divisible by N is a N + 1 . According to the problem, the sum of all the numbers except for a N + 1 is divisible by N so we have ∑ i = 1 N a i ≡ 0 m o d N . But we also have, in general, for all k = 1 , 2 , 3 , . . . , N that ∑ i = 1 N + 1 a i − a k ≡ 0 m o d N . But if a N + 1 ≡ 0 m o d N this means that ∑ i = 1 N a i − a k ≡ 0 m o d N and as we already showed ∑ i = 1 N a i ≡ 0 m o d N this means − a k ≡ 0 m o d N ⟹ a k ≡ 0 m o d N .
If we look at the problem again then we see , he said I sum any N numbers not except which is divisible by N. So , if we have numbers as (0,1,2,3,4.......N) because there is no restriction on selection of numbers. Now , Sum of N numbers (1,2,3......N) is divisible by N and also individual N is divisible by N but the other numbers are not divisible by N.
So , I don't understand why the answer is "yes". It should be "No".
If i have done something wrong then please reply.
Log in to reply
Alright lets look at your numbers ( 0 , 1 , 2 , 3 , … , N ) . The question states that N must divide all sums with N terms from the original list of numbers. Is that true with your list? i.e. is it true that N divides 0 + 2 + 3 + ⋯ + N ?
Log in to reply
Thank you very much for your clear and simple argument.
Thank you, that helped. I also didn't noticed this specification in the statement and came up with a silly (& fake) counter-example.
9hours mi imi86a 64hours 99i94
If one number is divisible by N , and the sum of the other N numbers is divisible by N , then the sum of all N + 1 numbers—let's call this S —must also be divisible by N . Taking all N + 1 possible groups of N numbers and subtracting them from S , you are left with each individual number. And since S and groups of N are divisible by N , each number must be divisible by N .
Assume the opposite, that is if, if one of the numbers is divisible by N , then there exists one number that is not divisible by N . Let a be the number divisible by N , b be the number not divisible by N , and M be the sum of all the numbers except for a and b . Then M + a is divisible by N and M + b is divisible by N because they are the sum of N numbers. However, if M + a is divisible by N and a is divisible by N , then M is also divisible by N (since the difference of two values divisible by the same number must also be divisible by that same number), and if M + b is divisible by N and M is divisible by N , then b is divisible by N (by the same reasoning). So we have that b is not divisible by N and that b is divisible by N , which is a contradiction, so our original assumption must be false, which means that yes , if one of the numbers is divisible by N , then all of the other numbers must also be divisible by N .
It follows immediately from the first condition that each member of the set is equivalent to S mod N, where S is the sum of all members.
Therefore, if one member is 0 mod N, then S is 0 mod N and so is every other member.
Suppose that a j is a multiple of N .
Let k ∈ { 1 , … , N + 1 } . Then the sum of all N + 1 numbers may be written as ⎝ ⎛ i = j ∑ a i ⎠ ⎞ + a j = ⎝ ⎛ i = k ∑ a i ⎠ ⎞ + a k ; The first and third terms are sums of N numbers from the sequence, and therefore multiples of N . The second term is a multiple of N by assumption. Therefore, the fourth term a k is also a multiple of N .
This is my favorite solution here. Thanks for posting! +1
W ow We are leaving
Suppose on contrry that We have a number (say x) that is not divisible by N. But the sum is divisible by N, so there exist atleast one number (other then x, say t) such that, there sum is divisible by N. Now if we see the sum of all terms except 't', is not divisible by N, because x is not divisible by N. (A contrdiction). Hence the proof..
The N numbers is divisible by N and the N+1st number is also divisble by N. If you want to add N+1st number in the group but still maintain the group's divisibility by N, you must exclude a number in such group which is also divisible by N. Since the property of the resulting group must be divisible by N even excluding one of them, all of them must be divisible by N.
Here was my thought process: If you could pick any n from the list of n+1, switching in any (n+1) st element in the sum implies that the difference between the element swapped out and the one swapped in must be divisible by n (true for any difference). If one element is divisible by n, it can be the one swapped out and, since the difference is divisible by n, so must every other element be divisible by n.
If there are N+1 number,sum of N number is divisible by N and only one number is multiple of N (let it be 'a').
Let's take the 'a' and rest N-1 number. Sum of a and N-1 numbers is multiple of N, this means sum of N-1 number is multiple of N.
Let's take another case, take all number taken in previous case except 'a'. Add remaining number to those N-1 number, then it sum is also divisible by divisible by N, N-1 number are already divisible by N, so remaining one must be also divisible by, which means it is multiple of N.
In N+1number expect 'a', there are N number remaining, we can make N combination of N-1 numbers and all.case above will.be valid for every combination, and in every case a multiple of N will come and by using all combination we will get N numbers multiple of N, by taking a we will get N+1 number multiple of N. All number are multiple of N
Problem Loading...
Note Loading...
Set Loading...
Lets do all the working modulo N, and see if we can avoid any intimidating notation!
We are told that one of the numbers equals zero.
Isolate it and consider the sum of the other N numbers.
By the stated conditions this sum is zero.
Now swap in the isolated number and swap out any one of the numbers in the sum thus forming a new sum of N numbers.
By the stated conditions this new sum is also zero.
So the swapped out number must equal the swapped in number. In other words the swapped out number is also zero.
We could choose any number to swap out of the sum, and so we see that all the numbers are zero.
In other words, revoking our decision to work modulo N, all the numbers must be divisible by N.