Feladatmegoldó speciálkollégium

XII.

1) A sík pontjait kiszínezzük két színnel. Legyen t és k két tetszőleges pozitív valós szám. Bizonyítsuk be, hogy

(i) található olyan háromszög, amelynek mindhárom csúcsa ugyanolyan színű és területe t,

(ii) található olyan háromszög, amelynek mindhárom csúcsa ugyanolyan színű és kerülete k.

2) m dobozban labdák vannak. Több lépésen keresztül további labdákat helyezhetünk el a dobozokba. Egy lépés során kiválasztunk n dobozt és ezek mindegyikébe egy-egy labdát teszünk.

(i) Bizonyítsuk be, hogy (n, m) = 1 esetén elérhetjük, hogy minden dobozban ugyanannyi labda legyen.

(ii) Bizonyítsuk be, hogy (n, m) ≠ 1 esetén megadható olyan kiindulási helyzet, amelyből nem érhetjük el, hogy minden dobozban ugyanannyi labda legyen.

3) Egy 3 × 3-as sakktábla négy sarkában egy-egy ló áll. A felső sorban lévő két ló fekete, míg az alsó sorban álló két ló fehér. A lovakkal elkezdünk (lóugrásban) lépni úgy, hogy minden pillanatban egy mezőn legfeljebb egy ló állhat. Elérhetjük-e, hogy a két fehér ló két átlós sarokban álljon, míg a fekete lovak a másik átló két sarok-mezejében legyenek?

4) n hosszú 0−1 sorozatokat készítünk úgy, hogy bármely sorozatban legfeljebb két karakter megváltoztatásával ne kaphassunk meg egy másik sorozatunkat. Bizonyítsuk be, hogy legfeljebb \frac{2^{n}}{n+1} sorozatunk lehet.

5) 1989 város között 4000 út vezet (minden út két várost köt össze). Bizonyítsuk be, hogy van olyan körút, amely legfeljebb 20 városon keresztül vezet (egy körút folyamán oda kell visszaérkezni ahonnan indultunk és egyik városból sem mehetünk ki azon az úton ahol bejöttünk).

6) Egy n × n-es mátrix elemei 0-k és 1-esek. Tudjuk, hogy nincs olyan négy darab egyes, amelyek a következő konfigurációt alkotják: 1 1 1 1 . A négy egyes tehát két sorba és három oszlopba esik, azt azonban nem tesszük fel, hogy ezek közvetlenül egymás utáni sorok vagy oszlopok. Hány 1-es lehet maximálisan a mátrixunkban?

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