Jump to content
BrainDen.com - Brain Teasers
  • 0

An Arbitrary sum?


BMAD    62

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

Share this post

Link to post
Share on other sites

3 answers to this question

  • 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

Share this post

Link to post
Share on other sites
  • 0
witzar    18

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.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.