MHB Arrange Numbers for Complete Squares Puzzle

[Amer]

Arrange the numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
such that the summation of each two successive numbers is a complete square easy interesting question

 

[MarkFL]

Spoiler

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

 

[Nono713]

I can think of a backtracking algorithm to solve this relatively efficiently given any input set. Might code it up tomorrow. Does anyone have a way to attack this analytically (again, for any input set, not just consecutive integers, and return any solution sequence - or none if there are none). An argument for the associated decision problem would be interesting to see too.

 

[chisigma]

I can think of a backtracking algorithm to solve this relatively efficiently given any input set. Might code it up tomorrow. Does anyone have a way to attack this analytically (again, for any input set, not just consecutive integers, and return any solution sequence - or none if there are none). An argument for the associated decision problem would be interesting to see too.

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$

 

[Barioth]

I solved it too using

Spoiler

a matrix (I named my matrix A) with $$A_ab=1 if a+b=perfect square$$

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!

 

[Nono713]

I solved it too using

Spoiler

a matrix (I named my matrix A) with $$A_ab=1 if a+b=perfect square$$

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!

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.

 

[Nono713]

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 :p (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)

 

[Amer]

if we have three numbers in the given set that just has one mate from the set ( i mean by the mate, the summation of the two mates is a complete square ) then we can't order them

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 can't order it since 10,9,8 has one mate