Feladatok

1.) Két személy a következő játékot játssza: Az első személy minden időpontban 100 lépést tehet a két-dimenziós rácson az origóból indulva, és csak fölfelé vagy jobbra léphet. Ezután a második játékos kijelöl egy rácspontot, melyre az első játékos nem léphet. A két játékos látja egymás lépéseit. Az első játékos szeretne az origótól tetszőleges messze eljutni, a második játékos pedig ezt meg akarja akadályozni. Ki nyeri meg ezt a játékot jó stratégia esetén?

1b.) Mi a helyzet, ha az első játékos nemcsak felfelé, de lefelé is léphet? Ha az első játékos a három-dimenziós rácson bolyonghat, de minden irányban csak előre léphet? Ha magasabb dimenziós rácson bolyonghat, minden irányban csak előre lépve? Ha a két-dimenziós rácson bármely irányban léphet? (Úgy tudjuk, hogy az utolsó két kérdés megoldatlan. Sőt, mi a háromdimenziós feladatot sem tudjuk megoldani. Ezt a feladatot P.R. Mauldin professzortól hallottuk.)

2.) Legyenek adva a síkban körök, melyek közül semmelyik kettő nem metszi egymást, és tekintük az összes olyan pontot, ahol e körök közül legalább kettő érinti egymást. Bizonyitsuk be, hogy az e pontokból álló halmaz számossága nem lehet nagyobb mint megszámlálható. (Ezt a feladatot Keleti Tamás javaslatára tűzték ki az idei nemzetközi, egyetemisták közötti versenyen Bulgáriában.)

2b.) (Egyszerűbb, de hasonló feladat.) Nevezzük Y -nak a sikon egy pontból más-más irányba induló három szakasz únióját. Igazoljuk, hogy diszjunkt Y -ok tetszőleges rendszere megszámlálható.

3.) Lássuk be, hogy egy végesen generált idempotens félcsoport véges.

Definiciók: A félcsoport olyan halmaz, melyen van egy kétváltozós, asszociativ művelet. A félcsoport idempotens, ha annak minden a elemére a^{2} = a.

3b.) Hány eleme lehet maximum egy öt elemmel generált idempotens félcsoportnak? Hogy néz ki egy szabad idempotens félcsoport?

4.) Adjunk meg olyan végtelen hosszú 0–1 sorozatot, amelyikben egyetlen (nem üres) részsorozat sem ismétlődik háromszor közvetlenül egymás után. (Így például egy a 00101011 jelekkel kezdődő sorozat nem jó, mert ebben a 01 háromszor ismétlődik.)

4b.) Van-e végtelen sorozat három betűből, amelyikben egyetlen (nem üres) részsorozat sem ismétlődik kétszer egymás után?