Puzzle : A number game

Well,

This is comparatively a simple puzzle with a nice observation. Given to me by tejas, who in turn, faced it in an entrance exam of CMI.

Problem : You are given integers from 1…2n. You are supposed to divide it in two sub sequence A and B such that, A and B both are of the same size n. A is monotonically increasing and B is monotonically decreasing. Prove that,

for any two such sequences $\sum _{i=1} ^n | A[i] - B[i] | = n^2$ .

Solution : A very simple observation and you have the solution. Let, $\sum _{i=n+1} ^{2n} i - \sum _{i=1} ^n i=n^2$ . So here is what you do. The moment you observe that A[i] > B[i] for some i, you swap the elements. So the element at A[i] is now in B[i] and vice versa. Thus, you can make sure that set A has all and only elements from 1…n and B has all and only elements from n+1….2n. Note, that the difference is taken over the absolute value, hence swapping does not change it. Now we know that difference between summation of elements of B and A is $n^2$ .

Neat, isn’t it?

–Saurabh Joshi

Tags: math, puzzle, theorem

This entry was posted on February 24, 2011 at 7:21 am and is filed under math, puzzle, theorem. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

6 Responses to “Puzzle : A number game”

Jagadish Says:
February 25, 2011 at 1:02 pm | Reply
What if both A[i] and B[i] are from [1,n]?
- Saurabh Joshi Says:
  February 25, 2011 at 1:29 pm | Reply
  This will not happen. Note that initially, A is arranged in monotonically increasing sequence and B is arranged in monotonically decreasing sequence. Both A[i] and B[i] falling within 1..n means follows.
  At least i elements from A is from 1…n and at least n-i+1 elements from B ( remember that B[i] is also from 1..n hence B[i]B[i+1]…B[n] = n-i+1 elements ) is also from 1…n. Making total of n+1 element falling within 1…n. A contradiction, hence it will never be the case that A[i] and B[i] both will fall within 1…n.
Srinivas Vivek Says:
March 7, 2011 at 5:43 am | Reply
I believe there is a flaw in the solution. Consider the following example for n=6.

Sequence A = 1, 3, 5, 6, 7, 11
Sequence B = 12, 10, 9, 8, 4, 2
Sequence A-B = -11, -7, -4, -2, 3, 9.

As suggested, we must swap 4 and 7 to get the new sequence

Sequence A’ = 1, 3, 4, 5, 6, 11
Sequence B’ = 12, 10, 9, 8, 7, 2
Sequence A’-B’ = -11, -7, -5, -3, -1, 9.

Note that the sequences A-B and A’-B’ do not just differ only in the signs.

When we again repeat the process, we get a new sequence A”-B” whose corresponding terms again do not differ just in signs (in fact it is a permuation of sequence A’-B’).

Sequence A” = 1, 2, 3, 4, 5, 6
Sequence B” = 12, 11, 10, 9, 8, 7
Sequence A”-B” = -11, -9, -7, -5, -3, -1.

It may be noted that when we swap elements, there is a possibility of rearrangement of terms. Hence the “difference” sequence can be potentially different.
- Saurabh Joshi Says:
  March 7, 2011 at 6:05 am | Reply
  Well,
  I think you did not get the problem right. For each term A[i]-B[i] we take the absolute value.
  Also, note that only original sequences will be monotonically increasing and decreasing, not the one’s after we swap them
  
  Taking your example,
  A = 1,3,5,6,7,11
  B = 12,10,9,8,4,2
  ———————-
  |B-A| = 11,7,4,2,3,9
  
  We swap 4 and 7
  A’ = 1,3,5,6,4,11
  B’ = 12,10,9,8,7,2
  ———————-
  |B’-A’| = 11,7,4,2,3,9
  
  similarly, when we swap 9 and 2
  A”=1,2,5,5,6,2
  B” = 12,10,9,8,7,11
  ———————–
  |B”-A”| = 11,7,4,2,3,9
  
  Given two set ( not sequence) An = 1…n and Bn = n+1..2n.
  Difference between them ( permuting An and Bn in any order) |An-Bn| is always n^2.
  
  The swapping was just to show that, the sum of differences in any monotonically increasing A and monotonically decreasing B will be same as |An-Bn| = n^2.
  
  Even in your comment, note the following. You need to take absolute value of each term.
  
  so initially 11+7+4+2+3+9 = 36
  after the swapping ( according to your writing only ), 11+7+5+3+1+9 = 36.
  
  We are only interested in sum of absolute value of the differences.
Srinivas Vivek Says:
March 7, 2011 at 8:54 am | Reply
I think the solution is fine.

I was aware of the fact that we are interested only in the absolute difference of the two sequences. But, it was not clear to me whether or not you are rearranging the sequences after the swap. Now I know that indeed you are not rearranging them.
Arshdeep Singh Says:
September 15, 2011 at 5:39 pm | Reply
Nice that I came across your blog. :). This is a well known result called Proizvolov’s Identity.
Arshdeep, a guy with a lot of interest in math.

Me, Myself and Mathematics