Feladatmegoldó speciálkollégium

XIII.

1) Egy kelet-nyugati irányú út egy kanyargós folyón többször áthalad. A folyó délnyugaton ered és végül (némi kanyargás után) keletre tart. Az úton lévő hídakat egy nyugatról keletre tartó utazás alatt megszámozzuk 1-től n-ig az áthaladás szerinti sorrend alapján. Ezek után a folyón végigutazunk az eredettől és feljegyezzük a hídak számát, a találkozás szerinti sorrend alapján. Így az n szám egy permutációját kapjuk. Bizonyítsuk be, hogy ebben a permutációban a páratlan helyeken páratlan számok állnak.

2) Egy n megfigyelőállomással rendelkező sarkkutató expedició állomásai között legfeljebb k olyan van, amelyek között semelyik kettő nincs egymással közvetlen telefon-összeköttetésben. Továbbá nincs köztük három olyan, amelyek mindegyike mindegyikkel közvetlen összeköttetésben van. Bizonyítsuk be, hogy ekkor a közvetlen telefonösszeköttetések száma nem lehet nagyobb, mint \frac{nk}{2}.

3) Egy kör kerületén felveszünk n pontot úgy, hogy az általuk meghatározott húrok közül semelyik három sem menjen át egy közös belső ponton. Határozzuk meg az összes húr behúzásával keletkező tartományok számát.

4) Legyen {u_{n}}_{n=0}^{∞} a következő rekurzióval definiált 0 − 1 sorozat.

u_{0} = 0  ,  u_{2n} = u_{n}  ,  u_{2n+1} = 1 − u_{n}.

Bizonyítsuk be, hogy ezen sorozat minden 0 elemét egy 0, illetve 1 elemmel helyettesítjük (ebben a sorrendben) és ezzel egy időben minden 1 elemet egy 1, illetve 0 számokkal helyettesítjük, akkor visszakapjuk az eredeti sorozatot.

5) 5n pont között behúzunk 10n^{2} + 1 szakaszt és ezek mindegyikét kiszínezzük két szín valamelyikére. Bizonyítsuk be, hogy található olyan háromszög, amely oldalai ugyanolyan szinűek.

6) Egy négyzetrács csúcsai között nincs három, amelyek egy szabályos háromszög csúcsait alkotnák. Tetszőleges ϵ > 0 esetén létezik olyan szabályos háromszög, amely csúcsaihoz legalább ϵ távolságra egy-egy rácspont található.

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

Hajnal Péter