Problem:
|
|
There are 2n natural numbers 1,2,...,2n. Pick up any n natural numbers out of those 2n natural numbers and order them like: a1<a2<........<an , and order the remaining n integers like: b1>b2>........>bn . Then prove that |a1-b1|+|a2-b2|+...+|an-bn|=n2 .
|
|
Proof:
Suppose we assign a set of n integers, (1, 2, …. ,n-1, n), to a set of (a1, …, an)
sequentially, and assign another set of n integers,(2n, 2n-1, …, n+2, n+1) to a set of
(b1, …, bn) sequentially, for example, as shown in Figure 1, the sum of the absolutes is given by :
(2n-1) +((2n-1)-2)+… +((n+2)-(n-1))+((n+1)-n)) =
(2n+ (2n-1)+…+(n+2)+(n+1)) – (1+2+…+(n-1)+n) =
n*(2n+(n+1))/2 – n*(n+1)/2 = n2
In general, as shown in Figure 2, inside absolutes, the sign of (ai-bi), (for
i=1,…,n) can change.
What we want to prove is:
“The smaller integer in any absolute is always less than or equal to n.”
If we can prove this statement, the sum of the absolutes is given by:
(a sum of larger integers in absolutes) – ( a sum of smaller integers in absolutes),
which is exactly the same as
(2n+ (2n-1)+…+(n+2)+(n+1)) – (1+2+…+(n-1)+n) =
n*(2n+(n+1))/2 – n*(n+1)/2 = n2 .
To prove the statement, we suppose that both a larger integer and a smaller
integer in an i-th absolute (for i=1,…,n) is larger than n, as shown in Figure 3. Then,
because there must be n integers which are larger than n, (which are n+1, …,2n), in
at least one absolute (we call it j-th absolute here, where j is nor equal to i), both a
larger integer and a smaller integer must be smaller than or equal to n. As you can
see clearly in Figure 3, the existence of two sets of two integers, a set of two
integers which are larger than n, and a set of two integers which are smaller than or
equal to n, contradicts the increasing order of ak and decreasing order of bk, (for
k=1,…,n). Therefore, the statement was proven, and the sum of the absolutes is
always equal to n2. (End of Proof)
Figure 1 Figure 2 Figure 3