Kezdőlap


Feladat:	Gy.2297	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Csűrös M. , Nagy 888 Sz.
Füzet:	1986/május, 209 - 210. oldal		PDF \| MathML
Témakör(ök):	Számhalmazok, Halmazalgebra, Kombinatorika, Skatulyaelv, Gyakorlat
Hivatkozás(ok):	Feladatok: 1985/november: Gy.2297

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. Jelölje a megadott számok halmazát $A$ . Mivel a számok különbözőek, ezért közülük legalább kettő páratlan. Ha $b$ a legnagyobb $A$ -beli páratlan szám, akkor tekintsük a $b - b_{j}$ különbségeket, ahol $b_{j}$ -k a további $A$ -beli páratlan számok. Ezek a különbségek különböző pozitív páros számok. Ha hozzájuk vesszük az $A$ -beli páros számokat is, akkor 51 darab pozitív páros számunk van, amelyek egyike sem nagyobb 100-nál. A kapott 51 darab páros szám között tehát egyenlőknek is kell lenniük, hiszen összesen 50 darab 100-nál nem nagyobb pozitív páros szám van.
Van tehát olyan páros, $A$ -beli $a$ szám, amelyre $a = b - b_{j}$ valamelyik $A$ -beli páratlan $b_{j}$ számra. Ez a három szám nyilván különböző, így valóban találtunk egy kívánt számhármast.

Megjegyzés. Az állítás éles, abban az értelemben, hogy 52 helyett 51 számra már nem feltétlenül létezik megfelelő számhármas. Ha ugyanis az 51 szám a következő:

50, 51, ..., 100

, akkor közülük bármely kettőnek az összege nagyobb, mint 100.
Másrészről viszont a fenti bizonyítás érvényes marad, ha az 52 számról csak annyit tudunk, hogy egyikük sem nagyobb, mint 101, hisz 101-nél nem nagyobb páros szám is 50 darab van. Ugyanezzel a gondolatmenettel általában is megmutatható, hogy ha

n ≧ 3

és

n

darab különböző pozitív egész szám egyike sem nagyobb, mint

2 n - 3

, akkor létezik a megfelelő számhármas. Ez az állítás már éles, tehát

2 m - 3

-nál nagyobb számmal nem igaz.

II. megoldás. Megmutatjuk, hogy ha

m ≧ 3

adott pozitív egész, akkor

[\frac{m}{2}] + 2

darab

m

-nél nem nagyobb pozitív egész közül kiválasztható három úgy, hogy közülük kettőnek az összege egyenlő a harmadikkal. Ez

m = 100

esetben épp a bizonyítandó állítás.
Jelölje

[\frac{m}{2}] + 2

értékét

k

és legyen az adott

k

darab szám nagyság szerint

a_{1} < a_{2} ... < a_{k}

. Megmutatjuk, hogy a számok legnagyobbika,

a_{k}

előáll két másik megadott szám összegeként.
Az első megoldás gondolatmenetéhez hasonlóan most a

\begin{matrix} B = {a_{k} - a_{1}, a_{k} - a_{2}, ..., a_{k} - a_{k - 1}} és a C = {a_{1}, a_{2}, ..., a_{k - 1}} \end{matrix}

halmazokat kell vizsgálnunk. Most azonban vigyáznunk kell: a két halmaz közös elemére fennállhat

a_{k} - a_{i} = a_{i}

, vagyis a három szám nem különböző. Ha azonban a két halmaznak egynél több közös eleme van, akkor mivel

a_{k} = 2 a_{i}

legfeljebb egy

i

-re teljesülhet, valamelyik közös elem biztosan megoldást ad.
Mivel a

B

és a

C

elemei 1 és

m - 1

közötti számok, a

B \cup C

halmaz legfeljebb

m - 1

elemű. Ismeretes, hogy

\begin{matrix} ∣ B \cup C ∣ = ∣ B ∣ + ∣ C ∣ - ∣ B \cap C ∣, \end{matrix}

ahonnan

\begin{matrix} m - 1 ≧ 2 (k - 1) - ∣ B \cap C ∣, hisz ∣ B ∣ = ∣ C ∣ = k - 1. \end{matrix}

Rendezés után kapjuk, hogy

\begin{matrix} ∣ B \cap C ∣ ≧ 2 k - m - 1, \end{matrix}

vagyis

\begin{matrix} ∣ B \cap C ∣ ≧ 2 [\frac{m}{2}] - m + 3. \end{matrix}

(*)

Mivel a

(*)

jobb oldalán álló mennyiség a szóba jövő

m

-ekre legalább 2, a két halmaznak legalább két közös eleme van. Ebből pedig, mint láttuk, következik a bizonyítandó állítás.

Megjegyzés. A két megoldásban két, egymással szoros kapcsolatban álló mennyiséget határoztunk meg. Az első megoldás szerint, ha adott

n ≧ 3

esetén

α (n)

jelöli azt a maximális értéket, amelyre igaz, hogy

n

darab

α (n)

-nél nem nagyobb különböző pozitív egész közül mindig kiválasztható megfelelő számhármas, akkor

α (n) = 2 n - 3

.
A második megoldásban a fenti kérdés megfordításaként azt láttuk be, hogy ha adott

m ≧ 3

esetén

β (m)

jelöli azt a minimális értéket, amelyre igaz, hogy

β (m)

darab

m

-nél nem nagyobb különböző számból mindig kiválasztható megfelelő számhármas, akkor

β (m) = [\frac{m}{2}] + 2

. (Tulajdonképpen csak

β (m) ≦ [\frac{m}{2}] + 2

-t láttunk, de kisebb számokra nyilvánvalóan létezik ellenpélda.)
Érdekességként megemlítjük még, hogy várakozásunknak megfelelően

β (α (n)) = n

minden

n ≧ 3

-ra igaz, de páros

m

-re

α (β (m)) = m + 1