Welcome to our community

Be a part of something great, join today!

Nice Puzzle

Amer

Active member
Mar 1, 2012
275
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

Administrator
Staff member
Feb 24, 2012
13,775
8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
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

Well-known member
Feb 13, 2012
1,704
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

Member
Jan 17, 2013
52
I solved it too using

a matrix (I named my matrix A) with \(\displaystyle 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!
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
I solved it too using

a matrix (I named my matrix A) with \(\displaystyle 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.
 

Bacterius

Well-known member
MHB Math Helper
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 :confused:

...

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)
 
Last edited:

Amer

Active member
Mar 1, 2012
275
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 cant 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 cant order it since 10,9,8 has one mate