BrainDen.com - Brain Teasers

## Question

The first 2n positive integers are arbitrarily divided into two groups of n numbers each. The numbers in the first group are sorted in ascending order: a1 < a2 < ... < an; the numbers in the second group are sorted in descending order: b1 > b2 > ... > bn.

Find, with proof, the value of the sum |a1 − b1| + |a2 − b2| + ... + |an − bn|.

The table below is generated at random, in two stages. Firstly, a value of n in the range 2..20 is chosen at random. Then, n numbers in the range 1..2n are chosen at random. These numbers are sorted to form the sequence ai; the remaining numbers are sorted to form the sequence bi. For each i, the value |ai − bi| is calculated, and the sum is given.

Here are some generated random table . Use the tables to formulate a conjecture about each pair, (ai, bi.) Prove your conjecture, and hence find the value of the sum.

## Recommended Posts

• 0

Pairing the two lists are in reverse order ensures that each number from the lower half is matched with a number from the upper half. That is, each pair will consist of a number (1 to n) and a number (n+1 to 2n).
As the differences are being added the end value will be

SUM(n+1 : 2n) - SUM (1 : n)

((2n/2)(2n+1) - (n/2)(n+1)) - (n/2)(n+1))

(2n/2)(2n+1) - (2)(n)(n+1)/2

(n)(2n+1) - (n)(n+1)

2n2+n - (n2+n)

2n2+n - n2-n

n2

Edited by vinay.singh84
##### Share on other sites

• 0

Suppose {a_1, a_2, ..., a_n} contains k numbers <=n. This means that {b_1, b_2, ..., b_n} contains (n-k) numbers <=n. Sequences (a_i) and (b_i) are sorted ascending/descending, so

a_i <= n < b_i for i =1, ..., k
and
a_i > n >= b_i for i = k+1, ..., n.
Therefore
|a_i - b_i| = b_i - a_i for i=1, ..., k
and
|a_i - b_i| = a_i - b_i for i = k+1, ..., n.
This shows that
S = |a_1 - b_1| + ... + |a_n - b_n| = s_1*1 + s_2*2 + ... + s_{2n}*2n
where
s_i = -1 for i=1, ..., n
and
s_i = +1 for i=n+1, ..., 2n.
Therefore
S = -1-2-...-n + (n+1)+(n+2)+...+(n+n) = -(1+2+...+n) + n*n + (1+2+...+n) = n*n.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.