Problem

[Richard Guy]

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
>