Feladatmegoldó speciálkollégium XI.

1) A tér pontjait kiszínezzük három színnel. Bizonyítsuk be, hogy valamely színosztály pontjai között az összes lehetséges távolság előfordul.

2) Két operációt végezhetünk egy adott természetes számon: az egyik operáció a megkétszerezés, a másik az 1-gyel való megnövelés. Hányszor kell alkalmazni ezen operációkat ahhoz, hogy a 0 számból megkapjuk az n számot.

3) Egy a · a méretű négyzetben adott néhány, legfeljebb 1 területű alakzat. Tudjuk, hogy bármely, az alapnégyzet oldalaival párhuzamos egyenes legfeljebb egy alakzatba metsz bele. Bizonyítsuk be, hogy az alakzatok területének összege legfeljebb a lehet.

4) Egy n gyerekből álló csoport m darab 2 fős csapatot állít össze (a csapatok nevei: C_{1}, C_{2},…, C_{m}; a csapatok különbözőek, de egy gyerek több csapatban is benne lehet). Bizonyítsuk be, hogy kiválasztható ⌈\frac{2m}{n}⌉ darab csapat, hogy indexük szerint rendezve a csapatokat, a szomszédosaknak legyen közös tagja.

5) Legyen b_{n} a következő relációval definiált sorozat:

b_{1} = 0 , b_{2} = 2 , b_{3} = 3 , b_{n+1} = b_{n−1} + b_{n−2} (n ≥ 3).

Bizonyítsuk be, hogy p prímszám esetén p|b_{p}.

6) Egy egyenesen pontjaink vannak. Minden pontnak van egy bal és egy jobb oldali szomszédja. Az ezekbe vezető irányok címkézve vannak a 0 − 1 számokkal. Ekkor egy pont és egy 0 − 1 sorozat definiál egy sétát az egyenesen. Legyen w = w_{1}w_{2} … w_{n} egy 0 − 1 sorozat (w_{i} ∈ {0, 1}). Tegyük fel, hogy a P pontban állunk, egyet jobbra lépünk és innen a w elemei által mutatott séta szerint sétálunk. Legyen Q az a pont ahová eljutottunk.

(i) Tegyük fel, hogy a fent leírt P-ből Q-ba vezető út során mindig jobbra léptünk. Ekkor visszajuthatunk Q-ból P-be, ha egyet balra lépünk és ezekután követjük a w^{∗} = w̄_{n}w̄_{n−1} … w̄_{1} sorozatot (w̄_{i} = 1 − w_{i}).

(ii) Adjunk példát az egyenes olyan cimkézésére, egy P pontra és egy w 0−1 sorozatra amelyekre teljesül, hogy bárhonnan indulva és a w^{∗} sorozatot követve nem juthatunk P-be. (Ekkor az (i) pontban leírt módszer Q-ból nem vezethet P-be.)

(iii) Tegyük fel, hogy P olyan pont, hogy valahonnan w^{∗}-t követve P-be juthatunk. Ekkor Q-ból visszajutunk P-be ha az (i) pontban leírt módszert követjük (és persze nem tesszünk fel semmit a P-ből Q-ba vezető útról).

Megbeszélés: Május 2. (csütörtök), 4 óra, Riesz terem Hajnal Péter