cotpi 37 - Sum of differences

[cotpi]

For a given even positive integer, we create two lists of
integers such that every positive integer less than or equal to
the given integer belongs to exactly one of the two lists and
both lists contain an equal number of integers. There is a third
list which is initially empty. Then, at every step, we remove
the smallest number from the first list, the largest number from
the second list and insert the positive difference between the
two numbers into the third list.

What do we get if we divide the square of the given even
positive integer by the sum of all the numbers in the third list
when the first list becomes empty?

--
Originally posted at: http://cotpi.com/p/37/
Correct solutions will be archived at the URL mentioned above.

Solutions to 'Grid of binomial coefficients':
http://cotpi.com/p/35/#responses

[Ilan Mayer]

SPOILER

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Let the number be 2*n.

Let the smallest number in the first list be S1.
Let the largest number in the second list be L2.

There are n numbers > n and n numbers <= n, and n numbers in each
list.
If S1 > n, then all numbers in the first list are > n. Then L2 must be
<= n.
If S1 <= n, then at least one number > n is in the second list, so L2
must be > n.
Therefore the first difference is between a number greater than n and
one less than n.

After removing these two numbers there are n-1 numbers > n and n-1
numbers <= n, and n-1 numbers in each list.
The above argument now applies again, so the second difference is
between a number greater than n and one less than n.
This applies similarly to all the steps.

Therefore the sum of differences is equal to the sum from 1 to 2*n -
twice the sum from 1 to n.

This is equal to 1/2*2*n*(2*n+1)-2*1/2*n*(n+1) = 2*n^2+n-n^2-n = n^2,
and so the result of the division is always 4.



Please reply to ilan dot mayer at hotmail dot com

__/\__
\ /
__/\\ //\__ Ilan Mayer
\ /
/__ __\ Toronto, Canada
/__ __\
||

[Willem]

Ilan Mayer wrote:
) Let the number be 2*n.
)
) Let the smallest number in the first list be S1.
) Let the largest number in the second list be L2.
)
) There are n numbers > n and n numbers <= n, and n numbers in each
) list.
) If S1 > n, then all numbers in the first list are > n. Then L2 must be
)<= n.
) If S1 <= n, then at least one number > n is in the second list, so L2
) must be > n.
) Therefore the first difference is between a number greater than n and
) one less than n.
)
) After removing these two numbers there are n-1 numbers > n and n-1
) numbers <= n, and n-1 numbers in each list.
) The above argument now applies again, so the second difference is
) between a number greater than n and one less than n.
) This applies similarly to all the steps.
)
) Therefore the sum of differences is equal to the sum from 1 to 2*n -
) twice the sum from 1 to n.

How do you go from 'each difference is between a number less than n and
a number greater than n' to 'the sum is equal to the sum from 1 to 2*n' ?

It may be true, but I don't see how you can make this conclusion.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[Ed Murphy]

The sum is the sum of e.g.
(x1 - y1)
+ (x2 - y2)
+ (x3 - y3)
...
where (x1, x2, x3, ...) = n distinct values from 1 to n (in some order)
and (y1, y2, y3, ...) = n distinct values from n+1 to 2n (in some order)

Thus, rearranging terms, the sum is equal to
sum(x from n+1 to 2n) - sum(y from 1 to n)
= [sum(x from 1 to 2n) - sum(z from 1 to n)] - sum(y from 1 to n)

[Willem]

Ed Murphy wrote:
) Willem wrote:
)> How do you go from 'each difference is between a number less than n and
)> a number greater than n' to 'the sum is equal to the sum from 1 to 2*n' ?
)>
)> It may be true, but I don't see how you can make this conclusion.
)
) The sum is the sum of e.g.
) (x1 - y1)
) + (x2 - y2)
) + (x3 - y3)
) ...
) where (x1, x2, x3, ...) = n distinct values from 1 to n (in some order)

) and (y1, y2, y3, ...) = n distinct values from n+1 to 2n (in some order)

)

) Thus, rearranging terms, the sum is equal to

) sum(x from n+1 to 2n) - sum(y from 1 to n)

) = [sum(x from 1 to 2n) - sum(z from 1 to n)] - sum(y from 1 to n)

So it's the sum from 1 to 2*n, minus twice the sum from 1 to n.

And if you rearrange it differently, you get a much cleaner answer:
If you rearrange the terms by sorting them and then pairing, you get:
((n+1) - 1)
+ ((n+2) - 2)
+ ((n+3) - 3)
...
+ ((n+n) - n)

Which clearly simplifies to n+n+n+ ... +n, or n*n.