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

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

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

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.

ReplyDeleteI 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

Very elegant!

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

ReplyDeleteHi,

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

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

ReplyDeleteLet 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

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.

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