Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "KGS math club/solution pairing"
(→‎The Finish)
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
===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===
 
===Main Statement===
 
For all even <math>n</math>, except for <math>2, 4, 6, 10, 12, 20</math> and <math>22</math>.
 
For all even <math>n</math>, except for <math>2, 4, 6, 10, 12, 20</math> and <math>22</math>.
Line 107: Line 111:
  
 
===Claim (5) - Finding odd perfect squares===
 
===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>.
+
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
 
'''Proof.''' Proceed by induction on the even <math>n</math>. The statement is true for <math>n = 64</math>, since
Line 140: Line 144:
 
Using the claims, we prove the Main Statement by induction on the even <math>n</math>.
 
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 <math>n \leq 62</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>.
 
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>.
 
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
 
Let <math>p = k^2 - n</math> and observe
  
Line 173: Line 178:
 
apply Claim (2) to find a pairing for all the remaining numbers up to
 
apply Claim (2) to find a pairing for all the remaining numbers up to
 
<math>p - 1</math>.
 
<math>p - 1</math>.
 +
 +
===Credits===
 +
Work partially supported by suggestions and/or Thai food from/with Vladimir and Konrad.

Latest revision as of 19:30, 24 March 2016

Problem

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

Main Statement

For all even $n$, except for $2, 4, 6, 10, 12, 20$ and $22$.

Preparations

Clearly, pairings are not possible for odd $n$.

For numbers $a, b$, we say that $a$ is a partner of $b$, if $a + b$ 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 $n = 2$:
The number $1$ does not have a partner.
case $n = 4$:
The number $4$ does not have a partner.
case $n = 6$:
The only partner for $1$ is $3$.
With $3$ already occupied, $6$ is left without a partner.
case $n = 10, 12$:
The only partner for $9$ is $7$.
With $7$ already occupied, $2$ is left without a partner.
case $n = 20, 22$:
The only partner for $18$ is $7$.
With $7$ already occupied, the only remaining partner for $2$ is $14$.
With $14$ already occupied, the only remaining partner for $11$ is $5$.
With $5$ already occupied, the only remaining partner for $20$ is $16$.
With $16$ and $7$ already occupied, $9$ is left without a partner.

Claim (2) - Pairings for small cases

Except for the exceptional cases, there is a pairing for each even $n$ up to $62$.

Proof.

$n = 8 : [[1, 8], [2, 7], [3, 6], [4, 5]]$
$n = 14 : [[1, 8], [2, 14], [3, 13], [4, 12], [5, 11], [6, 10], [7, 9]]$
$n = 16 : [[1, 8], [2, 7], [3, 6], [4, 5], [9, 16], [10, 15], [11, 14], [12, 13]]$
$n = 18 : [[1, 15], [2, 14], [3, 13], [4, 12], [5, 11], [6, 10], [7, 18], [8, 17], [9, 16]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$
$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]]$

Claim (3) - The main inequality

For each $n \geq 64$, the inequality $68n \leq n^2 + 276$ holds.

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

\[68n + 68 \leq n^2 + 276 + 2n + 1\]

which simplifies to

\[68(n + 1) \leq (n + 1)^2 + 276\]

and this gives the statement for $n + 1$.

Claim (4) - Rewriting the main inequality

For each $n \geq 64$, the inequality $n + 4\sqrt{n + 25} + 29 \leq 2n + 3$ holds.

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

\[68n \leq n^2 + 276\]

Subtract $52n$ from both sides

\[16n \leq n^2 - 52n + 276\]

Add $400$ to both sides

\[16n + 400 \leq n^2 - 52n + 676\]

Factor both sides, using the binomial formula for the rhs

\[16(n + 25) \leq (n - 26)^2\]

Take the square root of both sides

\[4\sqrt{n + 25} \leq n - 26\]

Finally, adding $n + 29$ to both sides gives the statement.

Claim (5) - Finding odd perfect squares

For each even $n \geq 64$, there is an odd perfect square in the closed interval $[n + 24, 2n - 1]$.

Proof. Proceed by induction on the even $n$. The statement is true for $n = 64$, since

\[n + 24 = 88 \leq 11^2 = 121 \leq 127 = 2n - 1\]

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

\[(n + 2) + 24 = n + 26 \leq k^2 \leq 2n - 1 \leq 2n + 3 = 2(n + 2) - 1\]

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

\[k^2 = n + 25\]

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

\[k^2 + 4k + 4 = n + 4k + 29\]

Factoring the lhs and replacing $k$ in the rhs gives

\[(k + 2)^2 = n + 4\sqrt{n + 25} + 29\]

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

The Finish

Using the claims, we prove the Main Statement by induction on the even $n$.

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

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

Let $p = k^2 - n$ and observe

\[24 \leq p \leq n - 1\]

which implies the stronger inequality

\[24 < p \leq n - 1\]

since $p$ is odd. By construction of $p$, $p$ and $n$ sum up to $k^2$ and hence are partners. Furthermore, since $p$ and $n$ 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

\[(p + 1) + (n - 1) = k^2\] \[(p + 2) + (n - 2) = k^2\] \[(p + 3) + (n - 3) = k^2\] \[\dots\]

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

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

Credits

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=KGS_math_club/solution_pairing&oldid=77811"