Az I/14. feladat MEGOLDÁSA:

Mohó algoritmust fogunk használni. Válasszunk ki egy tetszőleges embert, ő lesz E₁, és állítsuk félre összes ismerősét. Legfeljebb tíz ismerőse van, így marad még (rajta kívül) legalább száz ember. Válasszunk ki ezek közül is egy tetszőleges E₂ embert és állítsuk félre E₂ összes ismerősét is. Így megint legfeljebb tízet állítottunk félre, tehát marad még (a két kiválasztotton és a legfeljebb 20 félreállítotton kívül) legalább 89 ember. Ezt az eljárást folytatva minden lépésben kiválasztunk egy új embert (az i-edik lépésben E_i-t) és félre állítjuk az ismerőseit. A (félreállítottakon és kiválasztottakon kívül) maradó emberek nem ismerik az addig kiválasztottakat. (Ezért az újonnan kiválasztott ember sem ismerheti a régebben kiválasztottakat.) A még választható emberek (=maradó) száma minden lépésben legfeljebb 11-gyel csökken. Vagyis a tíz ember kiválasztása után még mindig marad egy, aki az előző tízet nem ismeri. Tehát legalább 11 embert sikerül kiválasztanunk, hogy közülük senki ne ismerjen senkit. Ha a 110 ember olyan 11 fős „klikkeket” alkot, akik kölcsönösen ismerik egymást, viszont két klikk emberei közül senki nem ismer senkit, akkor ebből a társaságból nem lehet 10-nél több embert kiválasztani, hiszen minden „klikkből” csak egy embert választhatunk. Az állítás tehát ebben az irányban nem javítható.

Másrészt ha e 110 tagú társasághoz hozzáveszünk még egy 11 tagú „klikket”, akkor az így kapott 11 „klikk” mindegyikéből csak egy embert választhatunk, tehát még 121 tagú társaságra sem mindig igaz, hogy kiválasztható 12 megfelelő ember. Az állítás tehát mindkét irányban éles. Pontosabban még 120 emberre is igaz, hogy 11 megfelelő ember van benne, de 12 már nincs. Gráfelméleti nyelven azt bizonyítottuk be, hogyha egy 111 pontú gráfban minden pont foka legfeljebb tíz, akkor van 11 pont, amelyek közül semelyik kettő között nem fut él, és ugyanez nem minden 110 pontú gráfra igaz.

MEGOLDÁS