Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Sep 4, 2011

Arrange in a Sequence

Source:
Asked to me by Amol Sahasrabudhe (IITB 2004 Alumnus, Worked at Morgan Stanley Quant Division, Deutsche Bank)

Problem:
You are given 2n numbers ( 1 to n and 1 to n ). You have to arrange these numbers in a sequence such that between any two i`s , there exists exactly i-1 numbers. Is it possible for all n? If no, what are the values of n for which this is possible?

Disclaimer:
I have not been able to solve it. Sudhanshu Tungare (IITB 2008 EE Alumnus, Morgan Stanley) claims to have a solution. Cheers!

Update (November 1, 2011):
Part solution posted by Nishant Totla (CSE IITB Senior Undergraduate), Richie and Sarat in comments! Complete solution posted by Siddhant Agarwal (EE IITB Alumnus, CMI Grad student) in comments! Thanks a ton.

7 comments:

  1. It is easy to show that such sequences cannot exist for every n. Essentially, it can be shown that a necessary condition is n ≡ 0,1 (mod 4).

    Here is a proof for this:
    Suppose the number i (0<i<n+1) occurs at positions xi and yi (xi<yi). Then the condition is that yi-xi = i.

    From hereon, S denotes summation from i=1 to n.
    So we have Syi - Sxi = Si = n(n+1)/2

    But, we also have Syi + Sxi = 2n(2n+1)/2, as the yi and xi are positions in the sequence. Adding the two equations, we have 2.Syi = n(5n+3)/2.

    Which gives Syi = n(5n+3)/4. Since Syi is an integer, so must be the RHS. This can happen only when n ≡ 0,1 (mod 4).

    ReplyDelete
  2. Building upon Nishant's work, I complete the proof by showing that there exists a sequence for number of the form n=4k,4k+1.

    I will present an algorithm to construct the sequence. It will be clear to see that the sequence is properly defined and satisfies the conditions.

    _ will represent unfilled elements in the sequence.
    Sample case n=12,13 (for demonstration)

    Case1: n=4k. (sample n=12)

    Step1: Take all even numbers. Nest them together.
    12,10,..,2,_,2,..,12,_,_,_,...,_

    Step2: Put the biggest odd in the middle and put the other biggest odd number in the proper place on the right hand side.

    12,10,..,2,11,2,..,12,_,_,..,_,11,_,..,_

    Step3: We can as well now forget abt the even numbers. So we have

    _,_,_,_,11,_,_,_,_,_,_

    Now put the odd number which "fits" in the leftmost place such that its conjugate is just after the biggest odd number. In this case

    5,_,_,_,11,5,_,_,_,_,_,_

    Step4: Nest in the other odd numbers from the left

    5,9,7,3,11,5,3,_,_,7,9

    Step5: Put the 1's

    5,9,7,3,11,5,3,1,1,7,9

    DONE! (you can check that this works for all n=4k)

    Case2: n=4k+1
    for n=1 we have 1,1
    for n=5 we have 5,1,1,3,4,5,3,2,4,2

    So now assume n>=9 (Sample n=13)
    This algo is almost the same as the previous algo.

    Step1: Nest even numbers

    12,10,..,2,_,2,..,12,_,_,_,...,_

    Step2: Put biggest odd in the middle

    12,10,..,2,13,2,..,12,_,_,..,_,13,_,..,_

    Step3: We can as well now forget abt the even numbers. So we have

    _,_,_,_,_,_,13,_,_,_,_,_,_

    Now put the odd number which "fits" in the rightmost place such that its conjugate is just after the biggest odd number. In this case

    _,_,_,_,_,_,13,5,_,_,_,_,5

    Step4: Nest in the other odd numbers from the right

    11,9,7,_,_,3,13,5,3,7,9,11,5

    Step5: Put the 1's

    11,9,7,1,1,3,13,5,3,7,9,11,5

    DONE! (you can check that this works for all n=4k+1 with n>=9)

    QED

    ReplyDelete
  3. impressive sequence construction by siddhant. its elegant and also looks simple now.

    ReplyDelete
  4. Hi,

    Another easy proof of the necessary condition.For an arrangement let f_i = no of nos between the i's , let g_i = | f_i - (i-1) |. We seek an arrangement when Sum g_i = 0; Let S = Sum g_i.

    Any arrangement can be formed from 112233..nn by series of swappings. On the other hand any single swapping changes S by an even no. So an arrangement is possible only if S_0 = even. but S_0 = sigma i from 1 to n-1 = n(n-1)/2 . So this has to be even. so n =0,1 (mod 4).

    ReplyDelete
  5. I was reading through Richie's solution and wanted to share a solution which is a little different from his.

    Let f_i be the function as defined by Richie. So sum i from 1 to n f_i=n(n-1)/2 = S(say).

    When you consider any two numbers x, y, their relative arrangment in the sequence in one of the following ways:
    1) ..x...y...x...y...
    2) ..y...x...y...x...
    3) ..y...x...x...y...
    4) ..x...y...y...x...
    5) ..x...x...y...y...
    6) ..y...y...x...x...

    Lets look at the summation S in a different way. We take a pair of numbers and see how that pair contributes to S.

    lets define a function g() as the contribution to S due to the relative arrangement of the number x, y. In each of the above 6 cases the value of g will be:
    1) 2
    2) 2
    3) 2
    4) 2
    5) 0
    6) 0

    Each of the nC2(n choose 2) pairs will contribute either 0 or 2 to S. Let 'm' be the number of pairs whose contribution is 2.
    so 2m=S=n(n-1)/2
    m = n(n-1)/4 which implies n is of the form 4k or 4k+1

    Hope its a correct solution

    ReplyDelete
  6. Solution for the necessity part by Nishant Totla, Richie, Sarat are all correct. Thanks. You all basically have a combinatorial argument to count a function in two different way and since some parameters are integers, you get a constraint on n.

    Solution for the construction part by Siddhant Agarwal is awesome! Thanks a lot. I was not able to reach even close.

    ReplyDelete