Arrange in a Sequence

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

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?

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.


  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).

  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.

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


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


    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


    Step4: Nest in the other odd numbers from the left


    Step5: Put the 1's


    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


    Step2: Put biggest odd in the middle


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


    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


    Step4: Nest in the other odd numbers from the right


    Step5: Put the 1's


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


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

  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).

  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

  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.


Post a Comment

Popular posts from this blog

Asking a girl out

Coins Puzzle

Consecutive Heads