Jump to content
BrainDen.com - Brain Teasers
  • 0

An Arbitrary sum?



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.

Edited by BMAD
Link to comment
Share on other sites

3 answers to this question

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


Edited by vinay.singh84
Link to comment
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
a_i > n >= b_i for i = k+1, ..., n.
|a_i - b_i| = b_i - a_i for i=1, ..., k
|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
s_i = -1 for i=1, ..., n
s_i = +1 for i=n+1, ..., 2n.
S = -1-2-...-n + (n+1)+(n+2)+...+(n+n) = -(1+2+...+n) + n*n + (1+2+...+n) = n*n.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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


  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Create New...