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

About these ads

Tags: , ,

6 Responses to “Puzzle : A number game”

  1. Jagadish Says:

    What if both A[i] and B[i] are from [1,n]?

    • Saurabh Joshi Says:

      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.

  2. Srinivas Vivek Says:

    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:

      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.

  3. Srinivas Vivek Says:

    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.

  4. Arshdeep Singh Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 51 other followers

%d bloggers like this: