OKTV 2010/2011 3. kategória döntő 2. feladat
(Feladat azonosítója: OKTV_20102011_3kdf2f )
Témakör: *Kombinatorika

Anna és Bálint a következő játékot játsszák: Anna rajzol egy tetszőlegesen nagy üres (azaz él nélküli) gráfot, majd egyesével behúz tetszőleges éleket, amelyeket Bálint közvetlenül a behúzás után kékre vagy pirosra színez. További szabály, hogy az így keletkező gráfban minden csúcs foka legfeljebb k lehet, és k értékében előre megállapodnak. Melyik az a legkisebb k, amely mellett Anna ügyes játékkal mindenképpen létre tud hozni egy 2011 hosszúságú egyszínű utat?



 

Megoldás: 

$ k\ge3 $