Feladatmegoldó speciálkollégium X.

1) Legyen P_{1}, P_{2}, P_{3}, Q_{1}, Q_{2}, Q_{3} egy konvex n-szög 6 csúcsa, a körüljárás szerinti sorrendben felsorolva. Bizonyítsuk be, hogy nem lehetséges, hogy a P_{1}Q_{2}, P_{1}Q_{3}, P_{2}Q_{1}, P_{3}Q_{3} és P_{3}Q_{1} szakaszok mindegyike egységtávolságnyi.

2) Adott a síkon egy önmagát nem metsző töröttvonal. A töröttvonal két szakaszát metszőnek nevezzük, ha nem szomszédosak és az egyik egyenese átmegy a másik egy belső pontján. Bizonyítsuk be, hogy a töröttvonal szakaszaiból alkotott párok között páros sok metsző van.

3) Adott a síkon n pont. Kiválasztunk közülük néhány párt és vesszük az összekötő szakaszaikat. Ezt úgy tesszük, hogy a kapott szakaszokra igaz lesz, hogy bármely két szakasznak pontosan egy közös pontja legyen (ez egy közös végpont vagy a két szakasz metsze’spontja). Bizonyítsuk be, hogy a kijelölt szakaszok száma nem lehet több a kiinduló pontok számánál.

4) Egy szám kerekítettje olyan egész szám, amely ettől a számtól 1nél kevesebbel tér el. Bizonyítsuk be, hogy n darab pozitív számot kerekíthetünk úgy, hogy az n kerekített szám összege az eredeti számok összegétől legfeljebb \frac{1}{2}-del térjen el.

5) Poliéder éleit két színnel színezzük. Bizonyítsuk be, hogy lesz olyan lap, amely monokromatikus (minden éle ugyanolyan színű) vagy pedig két egyszínű ívből áll.

6) Adott egy S halmaz. S egy színezett részhalmaza egy A ⊂ S halmaz és A minden eleméhez a piros vagy kék szín hozzárendelése (egy f :→ { kék, piros} függvény). Két színezett halmaz kompatibilis, ha halmazelméleti metszetükön a színezéseik megegyeznek. Adott A és B az S halmaz színezett részhalmazainak két halmaza. Tudjuk, hogy A elemei s-eleműek, B elemei t-eleműek és bármely A ∈ A és B ∈ B esetén A és B nem kompatibilisek. S egy f két színezéséről (f :→ { kék, piros}) tudjuk, hogy A ∪ B valamelyik elemével kompatibilis. Az S két színezését nem ismerjük, de szeretnénk eldönteni, hogy a vele kompatibilis színezett halmaz A-ban illetve B-ben van. Ehhez kérdéseket tehetünk fel. Egy kérdés s ∈ S, amire az s elem f-beli színét kapjuk válaszként. Hány kérdéssel érhetünk célt?

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

Hajnal Péter