Kezdőlap


Feladat:	Gy.2414	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Balogh 171 J. , Benczúr Péter , Csirik J. , Jónás A. , Németh Endre , Pásztor 625 G. , Szamuely T.
Füzet:	1987/december, 452 - 453. oldal		PDF \| MathML
Témakör(ök):	Számhalmazok, Rekurzív eljárások, Konstruktív megoldási módszer, Számsorozatok, Gyakorlat
Hivatkozás(ok):	Feladatok: 1987/május: Gy.2414

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.

I. megoldás. Ilyen halmaz létezik, például a páratlan kitevőjű kettőhatványok $H$ halmaza, azaz $H = {2, 2^{3}, 2^{5}, ...} .$ Válasszuk ki ugyanis ennek egy tetszőleges véges $K = {2^{a_{1}}, 2^{a_{2},} ..., 2^{a_{m}}}$ részhalmazát, és tegyük fel, hogy $a_{1} < a_{2} < ... < a_{m} .$
A $K$ -beli elemek

\begin{matrix} S = 2^{a_{1}} + 2^{a_{2}} + ... + 2^{a_{m}} = 2^{a_{1}} (1 + 2^{a_{2} - a_{1}} + ... + 2^{a_{m} - a_{1}}) \end{matrix}

összege 2-nek pontosan az

a_{1}

-edik hatványával osztható, hiszen a zárójelben páratlan szám áll

(a_{i} > a_{1}, i = 2, 3, ..., m)

. Mivel egy négyzetszám prímtényezős felbontásában minden prímnek páros hatványon kell szerepelnie, ezért

S

nem négyzetszám, vagyis a megadott

H

halmaz valóban kielégíti a feltételeket.

II. megoldás. Mutatunk egy lényegesen más konstrukciót, miközben rekurzív módon adunk meg egy megfelelő

a_{n}

sorozatot. Legyen

a_{1} = 2

és ha

a_{n}

-ig már definiáltuk a sorozat elemeit, akkor legyen

\begin{matrix} a_{n + 1} = {(a_{1} + a_{2} + ... + a_{n})}^{2} + 1. \end{matrix}

Nyilván

a_{1} < a_{2} < ... < a_{n} < ...,

tehát a

H = {a_{1}, a_{2}, ...}

halmaznak végtelen sok eleme van.
Tekintsük ennek egy tetszőleges véges

K = {a_{i_{1},} a_{i}_{2}, ..., a_{i_{m}}}

részhalmazát, amelynek legyen

a_{i_{m}}

a legnagyobb eleme. (Nyilván föltehető, hogy

K

legalább kételemű, hisz

H

elemei nem négyzetszámok.) Ekkor az

\begin{matrix} {(a_{1} + a_{2} + ... + a_{i_{m} - 1})}^{2} < a_{i_{m}} < (a_{i_{1}} + ... + a_{i_{m} - 1}) + a_{i_{m}} = \\ = (a_{1} + ... + a_{i_{m} - 1}) + {(a_{1} + a_{2} + ... + a_{i_{m} - 1})}^{2} + 1 < {(a_{1} + a_{2} + ... + a_{i_{m} - 1} + 1)}^{2} \end{matrix}

egyenlőtlenség mutatja, hogy a

K

-beli elemek

a_{i_{1}} + a_{i_{2}} + ... + a_{i_{m}}

összege két szomszédos négyzetszám közé esik, tehát nem lehet négyzetszám.

Megjegyzések:

1. Sokan megemlítették, hogy az első megoldásban mutatott

H

halmazban 2 helyett tetszőleges nem négyzetszámot is írhatnánk. Például a

H = {10, 10^{3}, 10^{5}, ...}

halmaz tetszőleges véges részhalmazában az elemek összege páratlan sok nullára végződik, tehát nem négyzetszám.
2. A feladat általánosítható négyzetszámok helyett tetszőleges

k

-adik hatványokra. Mindkét megoldás gondolatmenetével konstruálható olyan végtelen számhalmaz, amelynek egyetlen véges részhalmazában sem teljes

k

-adik hatvány az elemek összege.
Németh Endre (Budapest, Fazekas M. Gimn., I. o. t.) a következő általánosítást igazolta:
Ha megadunk néhány egynél nagyobb pozitív egész

k_{1}, k_{2}, ..., k_{m}

számot, akkor létezik pozitív egészekből álló olyan végtelen halmaz, melynek egyetlen nem üres véges részhalmazában sem teljes

k_{1}

-ik, vagy

k_{2}

-ik,

...,

vagy

k_{m}

-ik hatvány az elemek összege. Bizonyításában az I. megoldás gondolatmenetét használta a

H = {2, 2^{K + 1}, 2^{2 K + 1,} ...}

halmazra, ahol

K = k_{1} \cdot k_{2} \cdot ... \cdot k_{m} .

3. Benczúr Péter (Budapest, Fazekas M. Gimn., I. o. t.) megmutatta, hogy a feladat kérdésére adott válasz négyzetszámok helyett tetszőleges olyan pozitív egészekből álló monoton növő

c_{1}, c_{2}, ...

számsorozatra is igenlő, melynek különbségsorozata (tehát a

c_{2} - c_{1}, c_{3} - c_{2} ..., c_{n + 1} - c_{n}, ...

sorozat) nem korlátos. (A feladatban

c_{n} = n^{2}

.) Bizonyításában a II. megoldáshoz hasonlóan rekurzióval definiálta a halmaz elemeit; a meglévő

a_{1}, a_{2} ..., a_{n}

elemek után

a_{n + 1} -et c_{m} + 1

-nek választotta, ahol

c_{m + 1} - c_{m} > a_{1} + ... + a_{n} + 1.

A különbségsorozatra tett feltétel miatt ilyen

m

index mindig található.
4. Többen úgy fogalmazták a II. megoldás gondolatmenetéhez hasonló okoskodásukat, hogy bármely véges halmazhoz, melynek egyetlen részhalmazában sem négyzetszám az elemek összege, hozzávehető még egy szám úgy, hogy az így kapott bővebb halmazra is igaz marad ez a feltétel.
Ezzel szó szerint azt mutatták meg, hogy tetszőlegesen nagy megfelelő halmaz található, de a feladat ennél többet kívánt, hiszen egy végtelen halmazt kellett keresni. Ebben az esetben ‐ némi átfogalmazással ‐ bizonyításuk átvihető a végtelen halmaz esetére, de ez nem mindig van így, ezért a jövőben ügyeljenek erre jobban megoldóink.