Feladat:	2014. évi Kürschák matematikaverseny 1. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Fleiner Tamás
Füzet:	2015/február, 68. oldal		PDF  |  MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Kombinatorika - Gráfelmélet
Hivatkozás(ok):	Feladatok: 2015/február: 2014. évi Kürschák matematikaverseny 1. 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.   1. megoldás. Legyen $A$ a társaság egy olyan tagja, aki a társaságból a lehető legtöbb személyt ismeri. Legyen $B$ egy olyan illető, akit $A$ nem ismer, $C$ pedig legyen $B$ egy ismerőse. Mivel $C$-nek legfeljebb annyi ismerőse van, mint $A$-nak, ezért függetlenül attól, hogy $A$ és $C$ ismeri-e egymást, $A$-nak legalább annyi $C$-től különböző ismerőse van, mint ahány $A$-tól különböző ismerőse van $C$-nek. A konstrukció folytán $C$ ismeri azt a $B$-t, akit $A$ nem ismer. Ezért $A$-nak bizonyosan van olyan $C$-től különböző $D$ ismerőse, akit $C$ nem ismer. Ekkor ha $A$, $B$, $C$ és $D$ ebben a sorrendben ülnek az asztalhoz, akkor éppen a feladatban kirótt feltételt teljesítik.  $\square$   2. megoldás. Készítsük el az élszínezett $G$ gráfot az $n$ pontú teljes gráfból az alábbiak szerint. A $G$ gráf csúcsait kölcsönösen egyértelműen megfeleltetjük a társaság tagjainak, és $G$ egy éle akkor legyen piros, ha a csúcsoknak megfelelő tagok nem ismerik egymást, egyébként pedig az adott él színe legyen zöld. A bizonyítandó állítás átfogalmazható úgy, hogy ha a teljes gráf éleit úgy színezzük pirosra és zöldre, hogy minden csúcsból indul piros és zöld él is, akkor a gráfban van tarka négyszög, azaz négy különböző $A$, $B$, $C$ és $D$ csúcs úgy, hogy míg az $AB$ és $CD$ élek pirosak, addig a $BC$ és $DA$ élek zöldek. Az alábbiakban ezt az állítást fogjuk $n$ szerinti teljes indukcióval igazolni. Ez az állítás $n=1$ esetén nyilvánvalóan teljesül, hiszen a feltevés lehetetlent kíván. Tegyük fel tehát, hogy legfeljebb $n-1$ csúcsú gráfokra már igazoltuk az indukciós állítást, és a vizsgált $G$-nek $n$ csúcsa van. Legyen $A$ a $G$ egy csúcsa. Ha az $A$ törlésével keletkező $G-A$ gráf minden csúcsából indul piros és zöld él is, akkor kész vagyunk, hisz az indukciós feltevés miatt $G-A$-ban van tarka négyszög, ami persze egyúttal $G$-ben is tarka négyszög. Feltehetjük tehát, hogy $G-A$ egy $B$ csúcsából (mondjuk) csak piros él indul (és persze $AB$ zöld). Ha most $G-B$-ben nincs tarka négyszög, akkor az indukciós feltevés miatt $G-B$-ben van olyan $C$ csúcs, amelyből csupa egyszínű él indul. Ha $A=C$, akkor a zöld $AB$ élen kívül $A$-ból és $B$-ből csak piros élek indulnak. Legyen $BX$ egy piros, $XY$ pedig egy zöld él. Mivel $XY$ zöld, ezért $Y\ne A$, tehát $ABXY$ tarka négyszög. Ha pedig $A\ne C$, akkor legyen $AD$ egy $A$-ból induló piros él. A konstrukció folytán $AB$ zöld, $BC$ piros, $CD$ zöld és $DA$ piros, tehát $ABCD$ egy $G$-beli tarka négyszög. Az indukciós állítást ezzel igazoltuk, a bizonyítás ezzel teljes.  $\square$   Megjegyzés. Általában nem igaz, hogy egy $4$-személyesnél nagyobb asztalhoz is biztosan le tudjuk ültetni a társaság néhány tagját a feladatban leírt módon. Ha ugyanis a társaságban van két olyan ismerős, hogy egyikük se ismeri a társaság egyetlen más tagját sem, továbbá e két ismerősön kívül mindenki mindenkit ismer, akkor teljesül a feladatban kirótt feltétel, de 4-nél több ember nem ültethető le a kívánt módon.