Kezdőlap


Feladat:	N.14	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Csörnyei Marianna , Szeidl Ádám
Füzet:	1994/december, 502 - 503. oldal		PDF \| MathML
Témakör(ök):	Számhalmazok, Indirekt bizonyítási mód, Számsorozatok, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1993/december: N.14

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.

Indirekt úton bizonyítunk, feltételezve, hogy nem létezik megfelelő számhármas. Legyen a három felhasznált szín a kék, a piros és a sárga. Nyilván feltehető, hogy az 1 kék. Ha van két egymást követő elem, amelyek színe piros és sárga (vagy sárga és piros), akkor készen vagyunk, mert a kisebbikhez a kék 1-et hozzáadva a nagyobbikat kapjuk, ami épp egy, a feltételeket teljesítő megoldás.
A továbbiakban sorozatnak azonos színű, egymás után következő elemeket nevezünk. Két sorozat közül az a kisebbik, amelyiknek első (legkisebb) tagja kisebb. (Látható, hogy ez a definíció egyértelmű.) Egy sorozat hossz egyenlő tagjai számával.
Tekintsük most a piros és sárga sorozatok közül a leghosszabbakat, legyen ezek hossza $k$ . Vegyük most a legkisebb $k$ hosszú sorozatot. Feltehető, hogy ez éppen piros. Elemei legyenek:

\begin{matrix} a_{1}, a_{1} + 1, a_{1} + 2, ..., a_{1} + k - 1 = a_{k} . \end{matrix}

Tetszőleges sárga elemet kiválasztva, az vagy kisebb, mint

a_{1}

, vagy nagyobb, mint

a_{k}

(hiszen a közbenső elemek pirosak). Ezért, ha képezzük e sárga értéknek és piros sorozatunk tagjainak különbségeit, akkor

k

darab egymást követő és a halmazunkba tartozó pozitív egészhez jutunk. Ezen számok egyike sem lehet kék, indirekt feltevésünk miatt. Ha van köztük sárga is és piros is, akkor kell, hogy legyen két egymást követő elem, amelyek egyike sárga, másika piros, amely a korábbiak szerint ellentmondana indirekt feltevésünknek.
Tehát az eredményül kapott

k

darab szám egy sárga vagy egy piros sorozatot alkot. Innen következik, hogy nincs

a_{1}

-nél kisebb sárga elem. Ha ugyanis

b < a_{1}

sárga volna, akkor az

\begin{matrix} a_{1} - b, a_{1} - b + 1, ..., a_{1} - b + k - 1 = a_{k} - b \end{matrix}

számok

k

hosszú sorozatot alkotnának, ami tekintve, hogy

a_{1} - b < a_{1}

, ellentmond az

(a_{1}, ..., a_{k})

sorozat minimalitásának.
Az sem igaz, hogy van kéttagú sárga sorozat. Legyen ugyanis a

b

és

b + 1

számok színe sárga. Ekkor mivel

b > a_{1}

, a

\begin{matrix} b - a_{1}, b - a_{1} + a, ..., b - a_{1} + k - 1, (b + 1) - a_{1} + k - 1 \end{matrix}

számok mindegyike piros vagy sárga kell legyen (a fentiekhez hasonlóan), tehát

k + 1

elemű piros vagy sárga sorozatot kapnánk, ami ellentmond

k

maximalitásának.
Jelöljük a sárga elemeket

b_{1} < b_{2} < ... < b_{s}

-sel, ahol

s > \frac{n}{4}

.
Tegyük fel, hogy

k > 1

. Tekintsük az alábbi számokat:

\begin{matrix} b_{1} - a_{1}, & b_{1} - (a_{1} + 1), ..., b_{1} - a_{k}, \\ b_{2} - a_{1}, & b_{2} - (a_{1} + 1), ..., b_{2} - a_{k}, \\ ⋮ \\ b_{s} - a_{1}, & b_{s} - (a_{1} + 1), ..., b_{s} - a_{k}, \end{matrix}

Minden sorban egy-egy

k

tagú piros vagy sárga sorozat áll, s mivel

k \geq 2

, következik, hogy minden elem piros. Ezen kívül a felírt

k \cdot s

darab elem közül bármely kettő különböző, hiszen most maximális hosszúságú piros sorozatokról van szó. Van tehát legalább

k s

darab piros,

s

darab sárga és

p

(> \frac{n}{4})

darab kék elemünk. Eszerint

\begin{matrix} n \geq k \cdot s + s + p > \frac{k \cdot n}{4} + \frac{n}{4} + \frac{n}{4} \geq \frac{2 n}{4} + \frac{n}{2} = n, \end{matrix}

ami ellentmondás. Itt persze felhasználtuk, hogy

k \geq 2

. A

k = 1

esetben vizsgáljuk az összes piros és sárga elemet 1-gyel megelőző tagokat. Ezek színe csak kék lehet, mert ellenkező esetben vagy kéttagú sorozatot, vagy egymás melletti piros és sárga elemeket kapunk. Mivel az 1 kék, az összes ilyen elem valóban benne van a kérdéses halmazban (az

1 - 1 = 0

eset okozhatott volna gondot). Ez tehát több mint

\frac{n}{4} + \frac{n}{4}

darab kék elem. Ezen kívül van több mint

\frac{n}{4}

piros és több mint

\frac{n}{4}

sárga elem. Ez összesen megint több, mint

n

.
Az ellentmondásból következik a bizonyítandó állítás.
A ..legalább'' feltétel esetén elképzelhető olyan színezés, ahol nincs megfelelő számhármas, de csak ha

4 ∣ n

. Ekkor színezzük a páratlan számokat kékre, a párosakat pedig pirosra és sárgára úgy, hogy mindkét színből pontosan

\frac{n}{4}

darab legyen. Mivel páros + páros = páros és páros + páratlan = páratlan, azért ilyenkor nem kaphatunk különböző színű megoldást.

Szeidl Ádám (Miskolc, Földes F. Gimn., IV. o. t.)