Difference between revisions of "KGS math club/solution pairing"
(→The Finish) |
|||
(3 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 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 20:30, 24 March 2016
Contents
Problem
For which natural numbers is it possible to take the integers
and pair them up so that the sum of each pair is a perfect square?
Main Statement
For all even , except for
and
.
Preparations
Clearly, pairings are not possible for odd .
For numbers , we say that
is a partner of
, if
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
:
- The number
does not have a partner.
- The number
- case
:
- The number
does not have a partner.
- The number
- case
:
- The only partner for
is
.
- With
already occupied,
is left without a partner.
- The only partner for
- case
:
- The only partner for
is
.
- With
already occupied,
is left without a partner.
- The only partner for
- case
:
- The only partner for
is
.
- With
already occupied, the only remaining partner for
is
.
- With
already occupied, the only remaining partner for
is
.
- With
already occupied, the only remaining partner for
is
.
- With
and
already occupied,
is left without a partner.
- The only partner for
Claim (2) - Pairings for small cases
Except for the exceptional cases, there is a pairing for each even up to
.
Proof.
Claim (3) - The main inequality
For each , the inequality
holds.
Proof. Proceed by induction on . The statement is true for
, since the lhs
of the inequality evaluates to
and the rhs evaluates to
.
Now assume the statement is true for
and note that
.
Adding this inequality to the induction hypothesis gives
which simplifies to
and this gives the statement for .
Claim (4) - Rewriting the main inequality
For each , the inequality
holds.
Proof. Start with the inequality from Claim (3).
Subtract from both sides
Add to both sides
Factor both sides, using the binomial formula for the rhs
Take the square root of both sides
Finally, adding to both sides gives the statement.
Claim (5) - Finding odd perfect squares
For each even , there is an odd perfect square in the closed interval
.
Proof. Proceed by induction on the even . The statement is true for
, since
Now assume that the statement is true for , that is, there is
an odd
with
. If
is already
at least
, then
also satisfies the statement for
,
since then
The remaining case actually simplifies to
since the case is ruled out, because
is even and
is odd.
Add
to the equation above and obtain
Factoring the lhs and replacing in the rhs gives
By Claim (4), this expression is less or equal to .
Hence,
is an odd perfect square in the interval
and this concludes the induction.
The Finish
Using the claims, we prove the Main Statement by induction on the even .
By the Claims (1) and (2), the Main Statement is true for all even .
Now let be even with
.
With Claim (5), we find an odd perfect square
in the interval
.
Let and observe
which implies the stronger inequality
since is odd. By construction of
,
and
sum up to
and hence are partners. Furthermore, since
and
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
Hence, in order to complete the pairing for all numbers up to ,
it only remains to pair up the numbers up to
.
Note that
is even.
If , then apply Claim (5) recursively again, to
instead of
,
in order to pair up another portion of the yet unpaired numbers.
Eventually, we will reach a scenario where
.
By the construction of
we know that
.
Hence
cannot be one of the exceptional cases and we may
apply Claim (2) to find a pairing for all the remaining numbers up to
.
Credits
Work partially supported by suggestions and/or Thai food from/with Vladimir and Konrad.