Feladatmegoldó speciálkollégium

V.

1) Kiszínezhetjük-e a koordináta sík egész koordinátájú pontjait piros és kék színnel úgy, hogy minden vizszintes egyenesen véges sok piros és minden függőleges egyenesen véges sok kék pont legyen?

2) Egy 1001 személyből álló társaságban bármely 11 személyből álló részhalmazában legalább 2 személy ismeri egymást. Bizonyítsuk be, hogy a társaságban létezik legalább 101 olyan személy, melyek mindegyike legalább 100 személyt ismer a társaságban.

3) Legyen M a sík egy nem korlátos konvex részhalmaza. Bizonyítsuk be, hogy M tartalmaz egy félegyenest.

4) Adott 3 automata, amelyek egész számokból álló számpárokat fogadnak el. A beadott számpárokat visszaadják és ezenkivül egy új számpárt produkálnak. Az első automatába az (a, b) számpárt rakva az új pár (a + 1, b + 1) lesz. A másodikba rakva a fenti párt (\frac{a}{2}, \frac{b}{2})-t kapunk vissza (ez a gép csak akkor müködik, hogy ha a beadott számpár mindkét eleme páros). A harmadik automatába két számpárt kell beadni úgy, hogy az egyik második eleme megegyezzen a másik első elemével. Ha ez az automata megkapja az (a, b) és (b, c) párt akkor a (a, c) párt adja ki. Kaphatunk-e egy (1, 50) párt, hogy ha kezdetben egyetlen párunk van:

(5, 19).

5) Van n ismeretlen szám. Meg akarjuk találni melyik a legkisebb és melyik a legnagyobb közülük. Ennek megoldásához kérdéseket tehetünk fel. Egy kérdésben két kiválasztott szám közötti nagyságrendi viszonyt érdeklődjük meg. Adjunk meg olyan eljárást ami minél kevesebb kérdéssel megtalálja a maximumot.

6) Legyen A egy n-elemű halmaz. A elemeit betűknek nevezzük. A betűk egy sorozatát (lehetséges ismétlődéssel) szavaknak nevezzük. Egy s = s_{1}s_{2} … s_{n} szóról tudjuk, hogy bármely két egymásutáni betűje különböző. Ezenkivül nincsenek olyan i < j < k < l indexek, hogy s_{i} = s_{k} ≠ s_{j} = s_{l} legyen. Mi az s szó maximális hossza? Mit mondhatunk s = s_{1}s_{2} … s_{n} hosszáról, hogy ha a s_{i} ≠ s_{i+1} és nem léteznek olyan i < j < k < l < m indexek, hogy s_{i} = s_{k} = s_{l} ≠ s_{j} = s_{m}.

Megbeszélés: (csütörtök), 4 óra, Riesz terem

Hajnal Péter