Minimum Value
Number Theory
Level
5
Let there be a set of N natural numbers 1,2,3,4...N. We are allowed to insert + or − sign in front of each number and add all the resultant numbers. The minimum non-negative value obtained is denoted as D(N).
Find the value of D(1)+D(2)+...+D(19216812112)
The answer is 9608406056.
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.
1 solution
D(N) is either 0 or 1. It's 0 if the sum from 1 to N is divisible by 2, meaning you can always separate the positive and negative numbers into two equal sums. If it isn't divisible by two then you have to separate the positive and negative into sums where the positive sum is 1 greater than the negative sum. Therefore the sum of D(N)s = the number of Ns for which (N^2+N)/4 is not an integer
or
Alternative Explanation: (a): D(n)=0 if n=0 or 3 mod 4 (b): D(n)=1 if n=1 or 2 mod 4
this is because (c): D(n+4) is less or equal to D(n) (because you can always do +(n-3)-(n-2)-(n-1)+n = 0 for the last four numbers)
knowing that D(3)=D(4)=0 we hence have (a)
proving (b) is a bit harder, you may look at the positive sum and the negative sum. Lets say D(n)=PS-NS, we have PS+NS=n(n+1)/2. (sum of numbers from 1 to n)
When n=1 or 2 mod 4, n(n+1)/2 is odd, so PS and NS can't be equal (the sum would be even) hence |PS-NS| is greater or equal to 1. It's 1 thanks to property (c)
So finally, since 19216812112=0 mod 4, answer is 19216812112/2=9608406056. (the sequence is 1 1 0 0 1 1 0 0...)