Feladat: 1962. évi Arany Dániel matematikaverseny 2. forduló haladók (speciális) 3. feladata Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1963/január, 16 - 17. oldal  PDF  |  MathML 
Témakör(ök): Konstruktív megoldási módszer, Arany Dániel
Hivatkozás(ok):Feladatok: 1962/szeptember: 1962. évi Arany Dániel matematikaverseny 2. forduló haladók (speciális) 3. feladata

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.

3. feladat. Három fiú és három leány közül mindegyik fiú pontosan két leányt és mindegyik leány pontosan két fiút ismer. Bizonyítandó, hogy a fiúk és leányok párokba állíthatók úgy, hogy mindenki ismerőssel kerüljön össze.

 

I. megoldás. Álljanak körbe a leányok (arccal a kör belseje felé), és álljon mindegyik fiú a mögé a leány mögé, akit nem ismer. Így minden leány mögött pontosan egy fiú áll. Nem lehet ugyanis, hogy valamelyik fiú ne találna magának helyet, mert úgy mind a három leányt ismerné; és az sem lehet, hogy két fiú állna egy leány mögé, mert akkor az illető leánynak csak egy fiú ismerőse lenne. Lépjen most mindegyik fiú a körben egy hellyel jobbra. Így mindegyikük ismerős leány mögé jut, azzal álljon párba. Ezzel a kívánt felállítás lehetséges voltát bebizonyítottuk.
Ismerősök kerülnek egy párba akkor is, ha mindegyik fiú egy hellyel balra lép a körben. Eszerint a követelménynek kétféleképpen is eleget lehet tenni.
 

II. megoldás. Fogja meg az első fiú az őt ismerő két leány kezét, majd ők a másik fiú ismerősük kezét. Ez nem lehet ugyanaz a fiú, mert akkor a körből kimaradó fiú és leány a körben levő két leány, ill. két fiú egyikét sem ismerné, s így nem lehetne két-két ismerősük. A most a körbe állt mindkét fiú másik leányismerőse viszont a harmadik leány, hiszen ő az első fiút nem ismeri. Így vele a kör zárul. Ha most körben minden második kézfogást elengednek a körben állók, éppen az előírásnak megfelelő párokat kapunk.
 

Megjegyzés. Ez a megoldás megegyezik az elsővel abban, hogy mindkettőben kizárjuk nem-ismerős fiú-leány pár összeállítását. Az utóbbi módszer viszont akárhány pár megalakítására is használható, hacsak a leányok és a fiúk száma egyenlő (n), és minden jelenlevő a másik csoportból pontosan két személyt ismer. 1 n>3 esetén előfordulhat, hogy a kézfogás során több kör alakul ki. 4-tagú kör is lehetséges, ezt az adott esetben csak a kimaradók csekély száma tette lehetetlenné.
 

III. megoldás. Álljanak a fiúk és lányok ideiglenesen akárhogyan párba. Ha mindenki ismerőssel került össze, nincs további tennivaló. Ha valamelyik fiú nem ismeri a párját, akkor vegyenek maguk mellé egy másik párt, és a leányok cseréljenek helyet. Miután minden fiú csak egy leányt nem ismer, és minden leány csak egy fiút nem ismer, a cserével elérik, hogy mind a két pár tagjai ismerik egymást. Ha most a harmadik pár tagjai is ismerik egymást, nincs további tennivaló. Az ellenkező esetben velük és még egy párral az előbbi eljárást megismételjük. Eszerint, a legkedvezőtlenebb esetből kiindulva is sikerül két cserével elvégezni a kívánt párbaállítást.
 

Megjegyzés. Számos versenyző elnevezte a fiúkat és a leányokat és ezután sorravette az összes lehetséges ismeretségeket. Ez az eljárás szükségtelenül bonyolítja a feladat megoldását.
1Vö. Hajós ‐ Neukom ‐ Surányi: Matematikai Versenytételek II. (Tankönyvkiadó, Bp. 1957.) 31 ‐ 33. o.