- Thread starter
- #1

- Thread starter Amer
- Start date

- Thread starter
- #1

- Admin
- #2

- Jan 26, 2012

- 644

- Feb 13, 2012

- 1,704

If n=2 k + 1 is a perfect square and the set is 1,2,..., 2k then is...

2 K + 1 = 2k-1 + 2 = 2 k -2 + 3 + ... = k+1 + k = n (1)

Of course however that is a very particular case...

Kind regards

$\chi$ $\sigma$

- Jan 17, 2013

- 52

It's pretty much done once you have the matrix, you see that 8 as the be the first (or last) number.

I ended with the same solution as MarkFL, and I was wondering if there is always a solution for n large enough?

and if that solution(if it exist) was unique?

I know that for this case with n =15 the solution is unique.

I'll take a look at it tomorow (right now I need to hit the bed) if someone find something before I do let me know!

- Jan 26, 2012

- 644

There are actually two solutions for n = 15, forward and reverse (obviously). There are no others. Solutions are not guaranteed to exist. There are none for n = 16, for instance (checked myself). Curiously there apparently are solutions for n = 30 and n = 60 (unsure, I'll check later). I have been working on two versions of an algorithm but they always end up having exponential complexity, because I can't find a good algorithm. I might post my drafts once I come back from comp labs.

It's pretty much done once you have the matrix, you see that 8 as the be the first (or last) number.

I ended with the same solution as MarkFL, and I was wondering if there is always a solution for n large enough?

and if that solution(if it exist) was unique?

I know that for this case with n =15 the solution is unique.

I'll take a look at it tomorow (right now I need to hit the bed) if someone find something before I do let me know!

- Jan 26, 2012

- 644

Actually my bad, I wrote the above in a hurry. n = 16 actually has solutions, namely:

(8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16)

(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8)

n = 17 has the following solutions:

(17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16)

(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17)

n = 18 to n = 22 have no solutions.

n = 23 has the following solutions:

(22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 14, 11, 5, 20, 16, 9, 7, 18)

(18, 7, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9)

(2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9, 7, 18)

(9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 7, 18)

(18, 7, 9, 16, 20, 5, 11, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22)

(18, 7, 9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2)

There will always be an even number of solutions, obviously.

Looks mysterious

...

An observation is that for n close to 15, the solutions tend to reuse the existing solution for n = 15 in some way (here 16 is added at the end, and after that 17 is added at the beginning), which I guess makes sense heuristically. The pattern breaks down for n = 23 though, there are bits of the original solution e.g. (8, 1, 15) but overall it changes quite a bit.

This is actually an interesting and deep problem. I wonder if it's NP-complete (probably not, if we limit ourselves to inputs of the form {1, 2, 3, ..., n} there should be an efficient way to find solutions. wouldn't surprise me if the full generalization is NP-complete though)

(8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16)

(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8)

n = 17 has the following solutions:

(17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16)

(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17)

n = 18 to n = 22 have no solutions.

n = 23 has the following solutions:

(22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 14, 11, 5, 20, 16, 9, 7, 18)

(18, 7, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9)

(2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9, 7, 18)

(9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 7, 18)

(18, 7, 9, 16, 20, 5, 11, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22)

(18, 7, 9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2)

There will always be an even number of solutions, obviously.

Looks mysterious

...

An observation is that for n close to 15, the solutions tend to reuse the existing solution for n = 15 in some way (here 16 is added at the end, and after that 17 is added at the beginning), which I guess makes sense heuristically. The pattern breaks down for n = 23 though, there are bits of the original solution e.g. (8, 1, 15) but overall it changes quite a bit.

This is actually an interesting and deep problem. I wonder if it's NP-complete (probably not, if we limit ourselves to inputs of the form {1, 2, 3, ..., n} there should be an efficient way to find solutions. wouldn't surprise me if the full generalization is NP-complete though)

Last edited:

- Thread starter
- #8

in our set 1,2,3,...,15

we have two such numbers which will be at the ends of the arrangement 9,8

for example 1,2,3,4,...,10

we cant order it since 10,9,8 has one mate