View source for KGS math club/solution pairing

===Problem===
For which natural numbers <math>n</math> is it possible to take the integers <math>1, \dots, n</math>
and pair them up so that the sum of each pair is a perfect square?

===Main Statement===
For all even <math>n</math>, except for <math>2, 4, 6, 10, 12, 20</math> and <math>22</math>.

===Preparations===
Clearly, pairings are not possible for odd <math>n</math>.

For numbers <math>a, b</math>, we say that <math>a</math> is a '''partner''' of <math>b</math>, if <math>a + b</math> is a perfect square.

The main statement is established through the following claims.

===Claim (1) - The exceptional cases===
No pairing is possible for the exceptions listed above.

'''Proof.'''

:case <math>n = 2</math>:
::The number <math>1</math> does not have a partner.

:case <math>n = 4</math>:
::The number <math>4</math> does not have a partner.

:case <math>n = 6</math>:
::The only partner for <math>1</math> is <math>3</math>.
::With <math>3</math> already occupied, <math>6</math> is left without a partner.

:case <math>n = 10, 12</math>:
::The only partner for <math>9</math> is <math>7</math>.
::With <math>7</math> already occupied, <math>2</math> is left without a partner.

:case <math>n = 20, 22</math>:
::The only partner for <math>18</math> is <math>7</math>.
::With <math>7</math> already occupied, the only remaining partner for <math>2</math> is <math>14</math>.
::With <math>14</math> already occupied, the only remaining partner for <math>11</math> is <math>5</math>.
::With <math>5</math> already occupied, the only remaining partner for <math>20</math> is <math>16</math>.
::With <math>16</math> and <math>7</math> already occupied, <math>9</math> is left without a partner.

===Claim (2) - Pairings for small cases===
Except for the exceptional cases, there is a pairing for each even <math>n</math> up to <math>62</math>.

'''Proof.'''

:<math>n = 8 : [[1, 8], [2, 7], [3, 6], [4, 5]]</math>
:<math>n = 14 : [[1, 8], [2, 14], [3, 13], [4, 12], [5, 11], [6, 10], [7, 9]]</math>
:<math>n = 16 : [[1, 8], [2, 7], [3, 6], [4, 5], [9, 16], [10, 15], [11, 14], [12, 13]]</math>
:<math>n = 18 : [[1, 15], [2, 14], [3, 13], [4, 12], [5, 11], [6, 10], [7, 18], [8, 17], [9, 16]]</math>
:<math>n = 24 : [[1, 24], [2, 23], [3, 22], [4, 21], [5, 20], [6, 19], [7, 18], [8, 17], [9, 16], [10, 15], [11, 14], [12, 13]]</math>
:<math>n = 26 : [[1, 15], [2, 14], [3, 22], [4, 21], [5, 20], [6, 19], [7, 18], [8, 17], [9, 16], [10, 26], [11, 25], [12, 24], [13, 23]]</math>
:<math>n = 28 : [[1, 15], [2, 14], [3, 6], [4, 21], [5, 20], [7, 18], [8, 28], [9, 16], [10, 26], [11, 25], [12, 24], [13, 23], [17, 19], [22, 27]]</math>
:<math>n = 30 : [[1, 3], [2, 14], [4, 5], [6, 30], [7, 18], [8, 28], [9, 16], [10, 26], [11, 25], [12, 24], [13, 23], [15, 21], [17, 19], [20, 29], [22, 27]]</math>
:<math>n = 32 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 16], [11, 14], [12, 13], [15, 21], [17, 32], [18, 31], [19, 30], [20, 29], [22, 27], [23, 26], [24, 25]]</math>
:<math>n = 34 : [[1, 3], [2, 7], [4, 5], [6, 19], [8, 28], [9, 27], [10, 26], [11, 25], [12, 24], [13, 23], [14, 22], [15, 21], [16, 33], [17, 32], [18, 31], [20, 29], [30, 34]]</math>
:<math>n = 36 : [[1, 3], [2, 7], [4, 21], [5, 20], [6, 10], [8, 28], [9, 27], [11, 25], [12, 24], [13, 36], [14, 22], [15, 34], [16, 33], [17, 32], [18, 31], [19, 30], [23, 26], [29, 35]]</math>
:<math>n = 38 : [[1, 3], [2, 7], [4, 21], [5, 20], [6, 10], [8, 28], [9, 27], [11, 38], [12, 37], [13, 36], [14, 22], [15, 34], [16, 33], [17, 32], [18, 31], [19, 30], [23, 26], [24, 25], [29, 35]]</math>
:<math>n = 40 : [[1, 3], [2, 7], [4, 5], [6, 19], [8, 28], [9, 40], [10, 39], [11, 38], [12, 37], [13, 36], [14, 35], [15, 21], [16, 33], [17, 32], [18, 31], [20, 29], [22, 27], [23, 26], [24, 25], [30, 34]]</math>
:<math>n = 42 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 41], [9, 27], [11, 38], [12, 37], [13, 36], [14, 35], [15, 34], [16, 33], [17, 32], [18, 31], [19, 30], [20, 29], [21, 28], [22, 42], [23, 26], [24, 40], [25, 39]]</math>
:<math>n = 44 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 27], [11, 14], [12, 37], [13, 36], [15, 34], [16, 33], [17, 32], [18, 31], [19, 30], [20, 44], [21, 43], [22, 42], [23, 41], [24, 40], [25, 39], [26, 38], [29, 35]]</math>
:<math>n = 46 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 16], [11, 14], [12, 13], [15, 34], [17, 32], [18, 46], [19, 30], [20, 44], [21, 43], [22, 42], [23, 41], [24, 40], [25, 39], [26, 38], [27, 37], [29, 35], [31, 33], [36, 45]]</math>
:<math>n = 48 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 16], [11, 14], [12, 13], [15, 21], [17, 32], [18, 31], [19, 30], [20, 29], [22, 27], [23, 26], [24, 25], [33, 48], [34, 47], [35, 46], [36, 45], [37, 44], [38, 43], [39, 42], [40, 41]]</math>
:<math>n = 50 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 16], [11, 14], [12, 13], [15, 34], [17, 47], [18, 46], [19, 30], [20, 44], [21, 43], [22, 42], [23, 41], [24, 40], [25, 39], [26, 38], [27, 37], [29, 35], [31, 50], [32, 49], [33, 48], [36, 45]]</math>
:<math>n = 52 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 16], [11, 14], [12, 52], [13, 36], [15, 34], [17, 47], [18, 46], [19, 45], [20, 44], [21, 43], [22, 42], [23, 41], [24, 40], [25, 39], [26, 38], [27, 37], [29, 35], [30, 51], [31, 50], [32, 49], [33, 48]]</math>
:<math>n = 54 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 16], [11, 53], [12, 37], [13, 36], [14, 35], [15, 34], [17, 47], [18, 46], [19, 45], [20, 44], [21, 43], [22, 42], [23, 41], [24, 40], [25, 39], [26, 38], [27, 54], [29, 52], [30, 51], [31, 50], [32, 49], [33, 48]]</math>
:<math>n = 56 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 55], [11, 53], [12, 37], [13, 36], [14, 22], [15, 34], [16, 33], [17, 47], [18, 46], [19, 45], [20, 44], [21, 43], [23, 41], [24, 40], [25, 56], [26, 38], [27, 54], [29, 35], [30, 51], [31, 50], [32, 49], [39, 42], [48, 52]]</math>
:<math>n = 58 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 55], [11, 53], [12, 37], [13, 36], [14, 22], [15, 34], [16, 33], [17, 47], [18, 46], [19, 45], [20, 44], [21, 43], [23, 58], [24, 57], [25, 56], [26, 38], [27, 54], [29, 35], [30, 51], [31, 50], [32, 49], [39, 42], [40, 41], [48, 52]]</math>
:<math>n = 60 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 16], [11, 53], [12, 37], [13, 36], [14, 35], [15, 34], [17, 47], [18, 46], [19, 45], [20, 44], [21, 60], [22, 59], [23, 58], [24, 57], [25, 56], [26, 55], [27, 54], [29, 52], [30, 51], [31, 50], [32, 49], [33, 48], [38, 43], [39, 42], [40, 41]]</math>
:<math>n = 62 : [[1, 3], [2, 7], [4, 5], [6, 10], [8, 28], [9, 16], [11, 14], [12, 52], [13, 51], [15, 49], [17, 32], [18, 46], [19, 62], [20, 61], [21, 60], [22, 59], [23, 58], [24, 57], [25, 56], [26, 55], [27, 54], [29, 35], [30, 34], [31, 50], [33, 48], [36, 45], [37, 44], [38, 43], [39, 42], [40, 41], [47, 53]]</math>

===Claim (3) - The main inequality===
For each <math>n \geq 64</math>, the inequality <math>68n \leq n^2 + 276</math> holds.

'''Proof.''' Proceed by induction on <math>n</math>. The statement is true for <math>n = 64</math>, since the lhs
of the inequality evaluates to <math>4352</math> and the rhs evaluates to <math>4372</math>.
Now assume the statement is true for <math>n \geq 64</math> and note that <math>68 \leq 2n + 1</math>.
Adding this inequality to the induction hypothesis gives

<cmath>68n + 68 \leq n^2 + 276 + 2n + 1</cmath>

which simplifies to

<cmath>68(n + 1) \leq (n + 1)^2 + 276</cmath>

and this gives the statement for <math>n + 1</math>.

===Claim (4) - Rewriting the main inequality===
For each <math>n \geq 64</math>, the inequality <math>n + 4\sqrt{n + 25} + 29 \leq 2n + 3</math> holds.

'''Proof.''' Start with the inequality from Claim (3).

<cmath>68n \leq n^2 + 276</cmath>

Subtract <math>52n</math> from both sides

<cmath>16n \leq n^2 - 52n + 276</cmath>

Add <math>400</math> to both sides

<cmath>16n + 400 \leq n^2 - 52n + 676</cmath>

Factor both sides, using the binomial formula for the rhs

<cmath>16(n + 25) \leq (n - 26)^2</cmath>

Take the square root of both sides

<cmath>4\sqrt{n + 25} \leq n - 26</cmath>

Finally, adding <math>n + 29</math> to both sides gives the statement.

===Claim (5) - Finding odd perfect squares===
For each even <math>n \geq 64</math>, there is an odd perfect square in the closed interval <math>[n + 24, 2n - 1]</math>.

'''Proof.''' Proceed by induction on the even <math>n</math>. The statement is true for <math>n = 64</math>, since

<cmath>n + 24 = 88 \leq 11^2 = 121 \leq 127 = 2n - 1</cmath>

Now assume that the statement is true for <math>n</math>, that is, there is
an odd <math>k</math> with <math>n + 24 \leq k^2 \leq 2n - 1</math>. If <math>k^2</math> is already
at least <math>n + 26</math>, then <math>k^2</math> also satisfies the statement for <math>n + 2</math>,
since then

<cmath>(n + 2) + 24 = n + 26 \leq k^2 \leq 2n - 1 \leq 2n + 3 = 2(n + 2) - 1</cmath>

The remaining case <math>n + 24 \leq k^2 < n + 26</math> actually simplifies to

<cmath>k^2 = n + 25</cmath>

since the case <math>k^2 = n + 24</math> is ruled out, because <math>n</math> is even and <math>k</math> is odd.
Add <math>4k + 4</math> to the equation above and obtain

<cmath>k^2 + 4k + 4 = n + 4k + 29</cmath>

Factoring the lhs and replacing <math>k</math> in the rhs gives

<cmath>(k + 2)^2 = n + 4\sqrt{n + 25} + 29</cmath>

By Claim (4), this expression is less or equal to <math>2n + 3</math>.
Hence, <math>(k + 2)^2</math> is an odd perfect square in the interval
<math>[(n + 2) + 24, 2(n + 2) - 1]</math> and this concludes the induction.

===The Finish===
Using the claims, we prove the Main Statement by induction on the even <math>n</math>.

By the Claims (1) and (2), the Main Statement is true for all even <math>n \leq 62</math>.

Now let <math>n</math> be even with <math>n \geq 64</math>.
With Claim (5), we find an odd perfect square <math>k^2</math> in the interval <math>[n + 24, 2n - 1]</math>.

Let <math>p = k^2 - n</math> and observe

<cmath>24 \leq p \leq n - 1</cmath>

which implies the stronger inequality

<cmath>24 < p \leq n - 1</cmath>

since <math>p</math> is odd. By construction of <math>p</math>, <math>p</math> and <math>n</math> sum up to <math>k^2</math>
and hence are partners. Furthermore, since <math>p</math> and <math>n</math> are of
opposite parity, there is an even number of numbers strictly
between them. These numbers may be paired up straightforward in the following way

<cmath>(p + 1) + (n - 1) = k^2</cmath>
<cmath>(p + 2) + (n - 2) = k^2</cmath>
<cmath>(p + 3) + (n - 3) = k^2</cmath>
<cmath>\dots</cmath>

Hence, in order to complete the pairing for all numbers up to <math>n</math>,
it only remains to pair up the numbers up to <math>p - 1</math>.
Note that <math>p - 1</math> is even.

If <math>64 \leq p - 1</math>, then apply Claim (5) recursively again, to <math>p - 1</math> instead of <math>n</math>,
in order to pair up another portion of the yet unpaired numbers.
Eventually, we will reach a scenario where <math>p - 1 \leq 62</math>.
By the construction of <math>p</math> we know that <math>24 \leq p - 1</math>.
Hence <math>p - 1</math> cannot be one of the exceptional cases and we may
apply Claim (2) to find a pairing for all the remaining numbers up to
<math>p - 1</math>.

===Credits===
Work partially supported by suggestions and/or Thai food from/with Vladimir and Konrad.