Kezdőlap


Feladat:	B.3500	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Peres Sámuel , Tóth János
Füzet:	2002/április, 228 - 229. oldal		PDF \| MathML
Témakör(ök):	Szöveges feladatok, Logikai feladatok, Irányított gráfok, Feladat
Hivatkozás(ok):	Feladatok: 2001/november: B.3500

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. Legyen a sor bal szélén álló fiú $F_{1}$ és tekintsük azt a lányt, $L_{1}$ -et, akit $F_{1}$ választott. Ha az ő választottja, $F_{2}$ azonos $F_{1}$ -gyel, akkor $F_{1}$ és $L_{1}$ egymást választották, készen vagyunk. Ha nem, akkor $F_{2}$ jobbra áll a sorban $F_{1}$ -től. Legyen most $F_{2}$ választottja $L_{2}$ . Mivel $F_{1}$ és $F_{2}$ útvonalai nem keresztezték egymást, ezért $L_{2}$ nem állhat $L_{1}$ -től balra. Ha $L_{1}$ és $L_{2}$ azonosak, akkor az $(F_{2}, L_{1})$ pár megfelelő, így föltehető, hogy $L_{2}$ az $L_{1}$ -től jobbra áll.

Az előző gondolatmenetet megismételve kapjuk, hogy ha

L_{2}

és

F_{2}

nem egymást választották, akkor

L_{2}

választottja,

F_{3}

F_{2}

-től jobbra áll. Ezt folytatva látható, hogy ha nincs olyan fiú és lány, akik egymást választották, akkor fiúk ‐ és lányok ‐ olyan

F_{1}, F_{2}, F_{3}, ... L_{1}, L_{2}, ...

sorozatát kapjuk, ahol minden fiú ‐ és lány ‐ az előzőtől jobbra áll az eredeti sorban. Mivel az ilyen sorozatok hossza szükségképpen véges, a fenti eljárás előbb-utóbb elakad, ez pedig, mint láttuk, éppen azt jelenti, hogy a megfelelő fiú és lány egymást választották.

Peres Sámuel (Dunaszerdahely, Vámbéry Ármin Gimn., 10. évf.

Megjegyzés. A bizonyításban nem használtuk ki, hogy a fiúk és a lányok száma egyenlő, csak azt, hogy mindkét halmaz véges. Igazából annyi is elegendő, ha csak az egyik halmaz véges, bár ebben az esetben gyakorlati nehézségekbe ütközne a választás lebonyolítása.

II. megoldás. Jelöljük a fiúkat és a lányokat a sorban elfoglalt helyük sorszámával. Ekkor a fiúk és a lányok választását egy-egy függvénnyel adhatjuk meg: ha az

i

-edik fiú a

j

-edik lányt választotta, akkor

f (i) = j

és hasonlóan értelmezhetjük a lányok g választásfüggvényét.
Ekkor

f,g : [1..100] \to [1..100]

, a nem metsző útvonalakról szóló különös feltétel pedig természetes jelentést kap ebben az értelmezésben: mindkét függvény monoton növő. A bizonyítandó állítás így azt jelenti, hogy van olyan

1 \leq k \leq 100

, amelyre

f(g (k)) = k

.
Jelöljük az

f\circg

összetett függvényt h-val. Monoton növő függvények kompozíciójaként a h is monoton növő, továbbá

1 \leq h (1) \leq h (100) \leq 100

. Legyen

m

az a legkisebb 1 és 100 közé eső egész, amelyre

i \geq h (i)

. Mivel

100 \geq h (100)

így a fenti

m

létezik. Ha

m = 1

, akkor

h (1) = 1

, ha pedig

m > 1

, akkor

m

értelmezése és a h monoton növekedése miatt

\begin{matrix} 1 \leq m - 1 < h (m - 1) \leq h (m) \leq m \leq 100, \end{matrix}

vagyis

h (m) = m

Tóth János (Békéscsaba, Rózsa Ferenc Gimn., 12. évf.