Kezdőlap


Feladat:	1992. évi Nemzetközi Matematika Diákolimpia 23. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Kós Géza
Füzet:	1993/január, 6 - 9. oldal		PDF \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Teljes indukció módszere, Indirekt bizonyítási mód, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1992/október: 1992. évi Nemzetközi Matematika Diákolimpia 23. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

(a) Az állításhoz nyilván elég az, hogy ha $n \geq 4$ , akkor $n^{2}$ nem írható fel $n^{2} - 13$ pozitív négyzetszám összegeként. Tegyük fel, hogy mégis felírható:

\begin{matrix} n^{2} = a_{1}^{2} + a_{2}^{2} + \dots + a_{n^{2} - 13}^{2}, \end{matrix}

ahol

a_{1}, \dots, a_{n^{2} - 13} \geq 1.

Rendezzünk át a következőképpen:

\begin{matrix} \sum_{i = 1}^{n^{2} - 13} (a_{i}^{2} - 1) = 13 . \end{matrix}

(1)

Ha megmutatjuk, hogy a

13

nem írható fel

x^{2} - 1

alakú

(x ⩾ 1)

számok összegeként, készen vagyunk. Mivel

x \geq 4

esetén

x^{2} - 1 > 13

, az

a_{i}

-k értéke csak

1

2

és

3

lehet, vagyis (1) bal oldalán minden tag

0

3

vagy

8

.
Ha nem szerepel

8

-as, akkor az összeg osztható

3

-mal; ha egy

8

-as szerepel, akkor az összeg

3

-mal osztva

2

maradékot ad; ha pedig legalább két

8

-as szerepel, akkor az összeg legalább

16

. Mivel a

13

3

-mal osztva

1

maradékot ad és

16

-nál kisebb, az összeg semmiképpen nem lehet

13

.
Igaz azonban az ‐ és ezt a (b) részben fel fogjuk használni ‐, hogy a

13

-nál nagyobb egész számok mind felírhatók

x^{2} - 1

alakú számok összegeként, sőt akár

3

-asokból és

8

-asokból álló összegként is.
(b) Nyilván olyan

n

-et kell keresnünk, amelyre igaz, hogy

n^{2}

felírható többek között két pozitív négyzetszám összegeként, vagyis

n

egy pitagoraszi számhármas legnagyobb eleme. A legkisebb ilyen számok:

\begin{matrix} 5, 10, 13, 15, 17. \end{matrix}

Könnyen ellenőrizhető, hogy ezek közül az

5

és a

10

négyzete nem írható fel három négyzetszám összegeként, ezért

n = 5 és n = 10

nem jó. Be fogjuk azonban bizonyítani, hogy

n = 13

megfelelő. Ehhez, mivel az (a) állítást már bebizonyítottuk, elég azt megmutatni, hogy

S (13) ⩾ 13^{2} - 14 = 155

, azaz a

13^{2} = 169

felírható

1,2,3, ...,154

vagy éppen

155

pozitív négyzetszám összegeként.
Legyen

k \leq 155

és próbáljuk meg felírni

169

-et

k

darab pozitív négyzetszám összegeként:

\begin{matrix} a_{1}^{2} + a_{2}^{2} + \dots + a_{k}^{2} = 169, \end{matrix}

ahol

a_{1}, ..., a_{k} \geq 1

. Rendezzük át ezt (1)-hez hasonlóan:

\begin{matrix} \sum_{i = 1}^{k} (a_{i}^{2} - 1) = 169 - k . \end{matrix}

(2)

Most tehát a

169 - k

számot kell felírnunk

k

darab

x^{2} - 1

alakú szám összegeként. Azok az

x^{2} - 1

alakú számok, amelyek

169

-nél kisebbek, a következők:

\begin{matrix} 0, 3, 8, 15, 24, 35, 48, 63, 80, 99, 120, 143, 168. \end{matrix}

Legyen

a_{1}

a legnagyobb olyan pozitív egész szám, amelyre

\begin{matrix} a_{1}^{2} - 1 \leq 155 - k \end{matrix}

(ilyen létezik, mert

155 - k \geq 0

), azaz

\begin{matrix} a_{1}^{2} - 1 = {\begin{matrix} 0, & ha 14 \leq 169 - k \leq 16; \\ 3, & ha 17 \leq 169 - k \leq 21; \\ 8, & ha 22 \leq 169 - k \leq 28; \\ 15, & ha 29 \leq 169 - k \leq 37; \\ 24, & ha 38 \leq 169 - k \leq 48; \\ 35, & ha 49 \leq 169 - k \leq 61; \\ 48, & ha 62 \leq 169 - k \leq 76; \\ 63, & ha 77 \leq 169 - k \leq 93; \\ 80, & ha 94 \leq 169 - k \leq 112; \\ 99, & ha 113 \leq 169 - k \leq 133; \\ 120, & ha 134 \leq 169 - k \leq 156; \\ 143, & ha 157 \leq 169 - k \leq 168 . \end{matrix} \end{matrix}

Ezután a többi

a_{i}

-t úgy kell megválasztanunk, hogy

\begin{matrix} \sum_{i = 2}^{k} (a_{i}^{2} - 1) = 169 - k - (a_{1}^{2} - 1) \end{matrix}

teljesüljön. Az

a_{1}

választása miatt

14 \leq 169 - k - (a_{1}^{2} - 1) \leq 36

. A továbbiakban tehát ezt a

14

és

36

közé eső számot kell

x^{2} - 1

alakú számok összegeként felírnunk.
Ha

169 - k - (a_{1}^{2} - 1)

osztható

3

-mal, akkor írjuk fel legfeljebb

12

darab

3

-as összegeként; ha

3

-mal osztva

1

maradékot ad, akkor

2

darab

8

-as és legfeljebb

6

darab

3

-as összegeként; ha pedig

3

-mal osztva

2

maradékot ad, akkor

1

darab

8

-as és legfeljebb

9

darab

3

-as összegeként írjuk fel.
Így a

169 - k - (a_{1}^{2} - 1)

számot felírtuk legfeljebb

12

darab

x^{2} - 1

alakú szám összegeként. (Természetesen ennél valamivel jobb eredményt is kaphatunk, ha például

5

, illetve

8

darab

3

-ast kicserélünk egy

15

-ösre, illetve

24

-esre. Könnyen ellenőrizhető, hogy

169 - k - (a_{1}^{2} - 1)

felírható legfeljebb

6

darab

x^{2} - 1

alakú szám összegeként is. Mindez azonban a megoldás menetét nem változtatja meg.)
Ha

k ⩾ 13

, akkor a többi tagot

0

nak választva megoldást adtunk (2)-re; ezzel bebizonyítottuk, hogy a

169

felírható

13,14, ...,155

pozitív négyzetszám összegeként.
Azt, hogy

1,2, ...,12

pozitív négyzetszám összegeként is előáll a

169

, úgy igazoljuk, hogy megadunk egy-egy lehetséges felírást:

\begin{matrix} 169 & = 13^{2}; \\ 169 & = 5^{2} + 12^{2}; \\ 169 & = 3^{2} + 4^{2} + 12^{2}; \\ 169 & = 4^{2} + 5^{2} + 2 \cdot 8^{2}; \\ 169 & = 5^{2} + 4 \cdot 6^{2}; \\ 169 & = 3^{2} + 4^{2} + 4 \cdot 6^{2}; \\ 169 & = 5 \cdot 4^{2} + 5^{2} + 8^{2}; \\ 169 & = 4 \cdot 3^{2} + 5^{2} + 3 \cdot 6^{2}; \\ 169 & = 9 \cdot 4^{2} + 5^{2}; \\ 169 & = 3^{2} + 10 \cdot 4^{2}; \\ 169 & = 1^{2} + 4 \cdot 2^{2} + 5 \cdot 4^{2} + 2 \cdot 6^{2} . \end{matrix}

Ezzel bebizonyítottuk, hogy

n = 13

valóban megfelelő.
(c) Megmutatjuk, hogy ha valamilyen

n ⩾ 8

egész számra

S (n) = n^{2} - 14

, akkor

S (2 n) = {(2 n)}^{2} - 14

. Ebből az állítás azonnal következik, hiszen akkor indukcióval igazolható, hogy minden nemnegatív egész

m

számra

n = 13 \cdot 2^{m}

megfelelő.
Valóban, ezt

m = 0

-ra a (b) részben bebizonyítottuk, ha pedig

n = 13 \cdot 2^{m}

megfelelő, akkor

n = 2 \cdot 13 \cdot 2^{m} = 13 \cdot 2^{m + 1}

is megfelelő.
Most tehát belátjuk, hogy ha

S (n) = n^{2} - 14

, akkor

4 n^{2}

minden

1 \leq k \leq 4 n^{2} - 14

-re felírható

k

darab pozitív négyzetszám összegeként. Ebből, az (a) állítást is felhasználva, következik, hogy

S (2 n) = 4 n^{2} - 14

.
Legyen először

k \leq n^{2} - 14

. Ebben az esetben

n^{2}

-et fel tudjuk bontani

k

darab pozitív négyzetszám összegére. Ha pedig ebben a felbontásban mindegyik négyzetszámot megszorozzuk

4

-gyel,

4 n^{2}

egy felbontását kapjuk. Legyen ezután

k_{1}, k_{2}, k_{3}, k_{4}

négy

(n^{2} - 14)

-nél nem nagyobb pozitív egész. Bontsuk fel

n^{2}

-et

k_{1}, k_{2}, k_{3}

, ill.

k_{4}

darab négyzetszám összegére:

\begin{matrix} n^{2} & = a_{1}^{2} + a_{2}^{2} + ... + a_{k_{1}}^{2}; & n^{2} & = b_{1}^{2} + b_{2}^{2} + ... + b_{k_{2}}^{2}; \\ n^{2} & = c_{1}^{2} + c_{2}^{2} + ... + c_{k_{3}}^{2}; & n^{2} & = d_{1}^{2} + d_{2}^{2} + ... + d_{k_{4}}^{2} . \end{matrix}

Ha ezeket a négyzetszámokat mind összeadjuk,

4 n^{2}

-nek egy olyan felbontását kapjuk, amelyben

k_{1} + k_{2} + k_{3} + k_{4}

darab négyzetszám szerepel:

\begin{matrix} n^{2} = a_{1}^{2} + ... + a_{k_{1}}^{2} + b_{1}^{2} + ... + d_{k_{2}}^{2} + c_{1}^{2} + ... + c_{k_{3}}^{2} + d_{1}^{2} + ... + d_{k_{4}}^{2} . \end{matrix}

Mivel

k_{1} + k_{2} + k_{3} + k_{4}

bármilyen

4

és

4 (n^{2} - 14) = 4 n^{2} - 56

közötti szám lehet, ez a módszer jó konstrukciőt ad

4 \leq k \leq 4 n^{2} - 56

-ra.
Most bontsuk fel

4 n^{2}

-et úgy, hogy

n^{2}

-et tetszőleges módon felbontjuk pozitív négyzetszámok összegére, és ehhez a felbontáshoz adjunk hozzá

3 n^{2}

darab

1^{2}

-t. Ezzel

4 n^{2}

-nek egy olyan felbontását kapjuk, amelyben a tagok száma

3 n^{2} + 1

és

4 n^{2} - 14

között bármilyen egész szám lehet.
A három konstrukció, amit mutattunk,

\begin{matrix} 1 \leq k \leq n^{2} - 14, 4 \leq k \leq 4 n^{2} - 56, \end{matrix}

illetve

\begin{matrix} 3 n^{2} + 1 \leq k \leq 4 n^{2} - 14 \end{matrix}

esetén adta meg

4 n^{2}

-nek egy felírását

k

darab pozitív négyzetszám összegeként. Ha

n ⩾ 8

, akkor

4 < n^{2} - 14

és

3 n^{2} + 1 < 4 n^{2} - 56

, ezért minden

1 \leq k \leq n^{2} - 14

-re működik valamelyik módszer.
Ezzel az állítást igazoltuk.

Megjegyzés. Ismeretes, hogy minden pozitív egész szám felírható legfeljebb 4 négyzetszám összegeként. Ennek felhasználásával be lehet bizonyítani, hogy ha

n^{2}

felírható 2 és 3 pozitív négyzetszám összegeként is, akkor

S (n) = n^{2} - 14