Problem

[Roberto Tauraso]

This goes in the direction of a similar problem involving primes
that you can find in JIS:
http://www.cs.uwaterloo.ca/journals/JIS/green.html
Do you think that your greedy algorithn is actually
a proof by induction?
The problem with squares is connected with a much harder
conjecture: there exists a square loop (circular permutation
of the numbers 1 to n such that the sum of any two consecutive
numbers is a square) for every n>=32 (see A071984).
Of course for even n the loop gives also a pairing.

Roberto Tauraso

On Sun, 22 Jan 2006, Richard Guy wrote:

> I believe that the following greedy algorithm
> works for all sufficiently large  n (>31?)
>
> Take largest odd square < 4n
>
> e.g. n=101, 361=202+159=...=181+180,
>
> reducing the problem to  2n=158
>
> n = 79:  289=158+131=...=145+144
> n = 65:  225=130+95=...=113+112
> n = 47:  169=94+75=...=85+84
> n = 37:  121=74+47=...=61+60
> n = 23:   81=46+35=...=41+40
> n = 17:   49=34+15=...=25+24
> n = 7:    25=14+11=13+12
> n = 5  can't be done, but  n = 7
> can be a different way (see below)
>
> I don't think that there are any descents
> much worse than
>
> 94, 86, 58, 54, 30, 10? and
> 93, 87, 57, 55, 29, 11?
>
> and presumably 29 and 30 can be done
> a different way.
>
> Here's a particularly happy one:
>
> 100, 80, 64, 48, 36, 24, 16, 8, 4.
>
> R.
>
> On Sun, 22 Jan 2006, Roberto Tauraso wrote:
>
> > Here there are some matchings:
> > n=4:
> > 8-1 7-2 6-3 5-4
> > n=7:
> > 14-2 13-3 12-4  11-5 10-6 9-7
> > 8-1
> > n=8:
> > 16-9 15-10 14-11 13-12
> > 8-1 7-2 6-3 5-4
> > n=9:
> > 18-7 17-8 16-9
> > 15-1 14-2 13-3 12-4 11-5 10-6
> > n=12:
> > 24-1 23-2 22-3 21-4 20-5 19-6 18-7 17-8 16-9 15-10 14-11 13-12
> > n=13:
> > 26-10 25-11 24-12 23-13
> > 22-3 21-4 20-5 19-6 18-7 17-8 16-9
> > 15-1 14-2
> > n=14:
> > 28-21
> > 27-9 26-10 25-11 24-12 22-14 20-16
> > 23-2 19-6 18-7 17-8
> > 15-1 13-3
> > 5-4
> > n=15:
> > 30-19 29-20 28-21 27-22 26-23
> > 25-11
> > 24-1 18-7 17-8 16-9 15-10 13-12
> > 14-2
> > 6-3 5-4
> > n=16:
> > 32-17 31-18 30-19
> > 29-7 28-8 27-9 26-10 25-24
> > 22-14 20-16
> > 23-2 21-4
> > 15-1 13-12 11-5
> > 6-3
> >
> > Bye,
> > Roberto Tauraso
> >
>