Kezdőlap


Feladat:	F.2230	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Beleznay F. , Bohus G. , Csikós Zsolt , Fodor L. , Halász P. , Heckenast L. , Horváth 718 I. , Kappelmayer Hedvig , Kelemen B. , Kiss 352 Gy. , Lipusz Cs. , Simonyi G. , Slenker Gy. , Sz. Nagy Cs. , Szegedy Patrik , Umann G.
Füzet:	1980/április, 151 - 152. oldal		PDF \| MathML
Témakör(ök):	Kombinatorikus geometria síkban, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1979/december: F.2230

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. Tegyük fel, hogy a $P_{1}$ , $...$ , $P_{k}$ pontok indexük növekvő sorrendjében helyezkednek el. Jelöljük a $P_{i} P_{j} (i \neq j)$ pontpár fölé rajzolt kört $K_{i j}$ -vel, és rendeljük hozzá minden $P_{t}$ ponthoz azon $K_{i j}$ körök színeinek halmazát, melyekre $i < j$ . Így minden ponthoz hozzárendeltük az $n$ szín egy részhalmazát. Mint ismeretes, egy $n$ elemű halmaznak $2^{n}$ különböző részhalmaza van, így ha $k > 2^{n}$ , létezik olyan $1 \leq q < r \leq k$ , hogy a $P_{q}$ és $P_{r}$ pontokhoz ugyanazon színekből álló részhalmazt rendeltük. Szemléletesen fogalmazva a $P_{q}$ és $P_{r}$ pontokba ugyanolyan színű körök "érkeznek jobbról''. Ekkor a $K_{q r}$ kör és az összes $K_{r m} (r < m)$ kör kivülről érinti egymást, és ez utóbbi körök között a fentiek szerint biztosan létezik a $K_{q r}$ körrel azonos színű.

Csikós Zsolt (Budapest, Fazekas M. Gyak. Gimn., II. o. t.)

II. megoldás. Az állítást

n

szerinti teljes indukcióval bizonyítjuk.

n = 1

esetén

k > 2

, tehát van legalább egy kívülről érintkező körpáros, és ezek egyforma színűek.
Tegyük fel, hogy

(n - 1)

-re igaz az állítás, belátjuk, hogy

n

-re is teljesül.
Tekintsük a

k > 2^{n}

pontból és a hozzájuk tartozó

n

színnel kiszínezett körökből álló rendszert. Válasszunk ki ebben egy színt, nevezzük ezt kéknek, és tegyük fel, hogy a pontok az egyenesen balról jobbra, indexük növekedő sorrendjében helyezkednek el.
Megmutatjuk, hogy ha nincs két egymást kívülről érintő kék kör, akkor van a pontoknak egy legalább

k / 2

pontból álló részrendszere, amelyben nincs kék kör. Legyen

H_{1}

azoknak a

P_{i}

pontoknak a halmaza, amelyekhez létezik olyan hogy

r < i

, hogy

K_{r, i}

színe kék.

H_{2}

legyen azoknak a

P_{j}

pontoknak a halmaza, melyekhez létezik olyan

s > j

, hogy

K_{j, s}

színe kék,

H_{3}

pedig azoké, melyekből egyáltalán nem indul ki kék kör.
Világos, hogy

H_{1} \cup H_{2} \cup H_{3}

az összes pontot tartalmazza. Feltehetjük, hogy

H_{1}

-ben legalább annyi pont van, mint

H_{2}

-ben (ellenkező esetben e kettőt felcserélhetnénk). Így a

H = H_{1} \cup H_{3}

halmaz tartalmazza a pontoknak legalább felét, azaz legalább

[\frac{k + 1}{2}] > 2^{n - 1}

pontot. Ha két

H_{1}

-beli

P_{x}

és

P_{y}

pontra

(x < y)

illeszkedő

K_{x, y}

kör kék színű volna, akkor ez a kör kívülről érintené a

P_{x}

ponton átmenő,

P_{x}

-től balra eső kék színű kört. (Ilyen van, mert

P_{x} \in H_{1}

.) Így két

H_{1}

-beli pontot nem köt össze kék kör. Tehát a

H

-beli pontok fölé rajzolt körök között egyáltalán nincs kék, hiszen

H_{3}

-beli ponton nem megy át kék kör. A

H

-beli pontokat összekötő körök

(n - 1)

színnel vannak színezve, így az indukciós feltétel szerint létezik közöttük két egyforma színű, egymást kívülről érintő kör. Ezek természetesen részei a kiindulási,

k

pontot tartalmazó rendszernek, így az állítást igazoltuk.

Szegedy Patrik (Budapest, Fazekas M. Gyak. Gimn., IV. o. t.)

Megjegyzés. Megmutatjuk, hogy

k = 2^{n}

esetén már létezik olyan színezés, melyben nincs két egymást kívülről érintő, azonos színű kör.

n = 1

esetén ez nyilván teljesül, hiszen egyetlen körről van szó. Feltéve, hogy ez az állítás igaz

(n - 1)

-re, bizonyítjuk

n

-re.
Tekintsük a

2^{n}

pontból és az őket összekötő körökből álló rendszert. Jelöljük az egyenesen balról az első

2^{n - 1}

-pontot rendre

R_{1}

R_{2}

...

R_{2^{n - 1}}

-gyel, a pontok másik felét pedig rendre

Q_{1}

Q_{2}

...

Q_{2^{n - 1}}

-gyel. Mind a két rész pontjaira illeszkedő körök kiszínezhetők a feltevés szerint

(n - 1)

színnel. Az

n

-edik színt pedig arra használjuk, hogy a két részrendszert összekötő

R_{i} Q_{j}

köröket színezzük. Így nem jön létre két egymást kívülről érintő

n

-edik színű kör, mert az

R_{i}

pontokból csak jobbra, a

Q_{j}

pontokból csak balra indulnak ki ilyen körök.