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.

Comments

  1. Anonymous6:11 PM, September 04, 2011

    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. sid4:40 PM, September 06, 2011

    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. chera9:56 AM, September 08, 2011

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

    ReplyDelete
  4. Richie12:49 PM, September 11, 2011

    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. Sarat11:58 PM, October 05, 2011

    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. Pratik Poddar2:41 PM, November 01, 2011

    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

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more