Feladat: F.1834 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1973/február, 62 - 63. oldal  PDF  |  MathML 
Témakör(ök): Indirekt bizonyítási mód, Kombinatorika, Konstruktív megoldási módszer, Feladat
Hivatkozás(ok):Feladatok: 1972/szeptember: F.1834

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. Gondoljuk, hogy a résztvevők egyenként érkeznek olyan időközökben, hogy megállapíthatják, van-e (régi) ismerősük a lassanként benépesülő I., II., III. teremben, és eszerint irányíthatjuk őket valamelyik terembe.
Minden olyan vendéget, aki az I.-ben nem talál ismerősre, mindjárt itt hagyunk. Akinek az I.-ben van ismerőse, azt a II.-ba, ha pedig itt is talál ismerősre, akkor a III.-ba küldjük. Nem léphet föl annak a szükségessége, hogy valaki számára még ekkor is egy negyedik termet kellene nyitnunk.
Tegyük föl ugyanis, hogy egy A vendég a III. teremben látja meg egy ismerősét, B-t. Ebből azt is megtudjuk, hogy A már a II.-ban is, az I.-ben is meglátta egy-egy ismerősét (mindegy, hogy kit), továbbá azt is, hogy ez a B amiatt került a III.-ba, mert egyrészt a II.-ban meglátta egy ismerősét, C-t, másrészt hogy B az I.-ben is talált ismerőst (mindegy, hogy kit), végül azt is tudjuk, hogy ez a C amiatt jutott a II.-ba, mert az I.-ben meglátta egy ismerősét, D-t. Ekkor pedig A-B-C-D olyan embernégyes, akiknek ebben a sorrendben való láncolata ‐ és persze a fordított sorrendben is ‐ ellentmond a meghívottakra vonatkozó közlésnek. Tehát A legkésőbb a III. teremben ismeretlen környezetbe jutott.

 

II. megoldás. Az elhelyezés folyamatát két szakaszra bontjuk: előbb azokat helyezzük el, akiknek a társaságban van legalább 3 ismerősük, majd a többieket. (A "sok'' ismerősű résztvevők kérdése tűnik első gondolatra nehezebbnek.)
Nos, az első csoportot egyszerre bevezethetjük az első terembe, mert tagjai nem ismerhetik egymást. Ha ugyanis E és F ebbe a csoportba tartoznak, akkor E-nek van legalább két olyan ismerőse, aki F-től különböző; legyen egy ilyen ismerőse G, másrészt F-nek van legalább egy, E-től és G-től különböző ismerőse, mondjuk H. Így, ha E és F ismernék egymást, akkor G, E, F, H olyan csoport lenne, amilyennek a létezése ki van zárva.
A többi résztvevőket már egyenként vezetjük be a termekbe. Mivel mindegyiküknek legföljebb két ismerőse van, bármelyiket legkésőbb a harmadik próbálkozásra elhelyezhetjük, még akkor is, ha két ismerősük van és ha ezeket már elhelyeztük is, éspedig két különböző terembe. (Hozzátehetjük: ilyen elhelyezésük később sorra kerülő vendég elhelyezését sem akadályozhatja.) Ezzel az állítást bebizonyítottuk.
 
Megjegyzések. 1. Az első csoport tagjairól többet is mondhatunk: ha van olyan vendég, akinek legalább három ismerőse van, az ő ismerősei közül egyiknek sincs még második ismerőse sem. Ha ugyanis János az első csoportba tartozik és három ismerőse Imre, Károly és László, akkor Károly sem Lászlót nem ismerheti, sem egy Miklóst, aki János számára ismeretlen, mert különben az Imre ‐János-Károly‐László (vagy Miklós) láncolat ellentmond a föltevésnek. ‐ Eszerint Jánost az I. teremben leültetve, az ő akárhány tagú ismeretségi köre elhelyezhető akár egyetlen további teremben is. És akárhány ilyen "János-típusú'' együttes van a meghívottak közt, elég számukra két terem.
2. Mégsem mondhatjuk, hogy a termek száma lecsökkenthető 2-re. Ha ugyanis Mária, Nusi és Olga páronként ismerik egymást, akkor elhelyezésükhöz szükség van a 3 teremre. (Így persze a lányok egyikének sem lehet további ismerőse.)
3. Ha a vendégeket pontokkal ábrázoljuk, a köztük esetenként fennálló ismeretségeket pedig a megfelelő pontpár valamilyen folytonos vonallal való összekötésével (vagyis a feladat előzményeiről egy ún. gráfot rajzolunk), akkor a "János-típusú'' együttest ún. csillag ábrázolja, a "Mária-típusú'' együttest pedig ún. háromszög. Ha a feladat ismeretségeinek gráfja szétbomlik csupa csillagra, akkor elég 2 terem, ha van benne háromszög, akkor csak 3 teremmel érünk célhoz. ‐ Több dolgozat tartalmazza annak bizonyítását is, hogy a feladat gráfja másféle részeket nem tartalmazhat.
4. Általában bizonyítható, hogy (n-1) teremben elhelyezhető a társaság (minden teremben olyan meghívottakkal, akik eredetileg nem ismerik egymást), ha nem fordul elő n tagból álló ismeretségláncolat. Feladatunkban n=4 volt.