Feladatmegoldó speciálkollégium VIII.

1) Egy könyvespolcon 102 könyv van egymás mellett. Egy “lépésen” azt értjük, hogy két szomszédos könyvet felcserélünk (a többit változatlanul hagyjuk). Minimálisan hány lépéssel érhető el az, hogy a két szélső könyv helyet cseréljen?

2) Egy parlamentben mindenkinek legfeljebb három ellensége van. Bizonyítsuk be, hogy a parlament két házra osztható úgy, hogy bármelyik házon belül mindenkinek legfeljebb egy ellensége legyen.

3) Egy kör kerületén jelöljünk ki n pontot. Legyen k ≤ \frac{n}{2}. A körön k egymás után következő kijelölt pontot intervallumnak nevezünk. Bizonyítsuk be, hogy ha adottak intervallumok úgy, hogy legyen páronként közös pontjuk, akkor az intervallumok száma legfeljebb k.

4) Hány pontot szükséges kijelölni egy konvex n-szög belsejében, hogy a sokszög csúcsai által alkotott háromszögek mindegyikének belsejében legyen kijelölt pont.

5) Adott n egyenes a síkon (semelyik három sem halad át egy közös ponton és nincs köztük két párhuzamos). Az egyenesek tartományokra osztják a síkot. Bizonyítsuk be, hogy a tartományokba írhatunk nem 0, legfeljebb n abszolút értékű egészeket úgy, hogy minden egyenesre teljesüljön, hogy bármely oldalán a számok összege 0 legyen.

6) A koordinátasíkon vegyük fel az y = x és y = x + k egyeneseket, ahol k tetszőleges egész. Ez a két egyenes közre fog egy sávot. Ebben a sávban kössük össze a két egyenest egy rácsegyenesekre (azaz x = a, illetve y = b egyenletű egyenesekre, ahol a és b egészek) illeszkedő, jobbra és lefelé haladó lépcsős törötvonallal. A két egyenesen és az összekötő töröttvonalon lévő egész koordinátájú pontokhoz írjuk oda az 1 számot. A két egyenes közti sáv egész koordinátájú pontjait is számozzuk meg úgy, hogy a következő szabály teljesüljön: Ha az (a, b), (a, b+1), (a+1, b) és (a, b + 1) pontokhoz rendre az α, β, γ és δ számokat írtuk, akkor αδ − βγ = 1 legyen. Bizonyítsuk be a következő állításokat:

a) A fenti szabály szerint a sáv egész koordinátájú pontjaihoz egyértelműen rendelhetők számok és ezek pozitív egészek lesznek.

b) A sávba írt számok periodikusan ismétlődnek, azaz egy alkalmas p egész számra az (x, y) ponthoz írt szám ugyanaz lesz, mint az (x+p, y+p)- hez írt szám.

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

Hajnal Péter