Feladatmegoldó speciálkollégium IX.

1) Egy matematikai lap n számú (n ≥ 2) feladatot közöl. Ugyancsak n számú olvasó mindegyike két feladat megoldását küldi be oly módon, hogy az n számú feladat mindegyikére két különböző megoldás (összesen tehát 2n megoldás) érkezik be. A szerkesztő minden beküldőnek egy megoldását (összesen tehát n megoldást) akar közölni lapjában. Lehetséges-e ez mindig?

Bizonyítsuk be, hogy ha az n számú megoldást a feltételeknek megfelelően k-féleképpen lehet kiválasztani, akkor k = 2^{ν}, ahol ν egy pozitív egész számot jelent!

2) Adott a síkon 22 pont úgy, hogy semelyik 3 sincs egy egyenesen. Bizonyítsuk be, hogy a pontok párba állíthatók (11 párunk lesz, amelyek 11 szakaszt határoznak meg) úgy, hogy a 11 szakasz közül 10-et felhasználva 5 metsző szakaszpárt alkothassunk.

3) Adott 1000 lineáris függvény: f_{k}(x) = p_{k}x + q_{k}, (k = 1, 2,…, 1000). Bizonyítsuk be, hogy ezen függvények kompoziciójának egy adott pontban vett helyettesítési értéke f(x_{0}) = f_{1000}(f_{999}(f_{998}(… f_{2}(f_{1}(x_{0})) …))) kiszámítható legfeljebb 30 lépéssel. Egy lépésben párhuzamosan több müveletet is elvégezhetünk: az előző lépések valamelyikében már kiszámított számokból, illetve a p_{k}, q_{k} számokból párokat alkothatunk és egy alapmüveletet végezhetünk az egyes párok elemeivel.

4) Egy társaságban bármely két ismerősnek nincs közös ismerőse. Másrészt bármely két résztvevő esetén, ha nem ismerik egymást, akkor pontosan két közös ismerősük van. Bizonyítsuk be, hogy a társaságban mindenkinek ugyanannyi ismerőse van.

Mit mondhatunk társaság létszámáról?

5) Egy G gráfról szeretnénk eldönteni, hogy van-e benne olyan pont, amely semelyik másikkal sincs összekötve. Az eldöntéshez kérdéseket tehetünk fel G-ről. Egy kérdésben tetszőleges két pontról kérdezhetjük meg, hogy össze vannak-e kötve. Hány kérdés kell ahhoz, hogy biztosan el tudjuk dönteni a problémát.

6) Legyen n természetes szám és 0 ≤ k ≤ n − 1 egész. Ekkor legyen

S_{n,k} = {(x_{1},…, x_{n}) : 0 ≤ x_{i} ≤ 1, k ≤ ∑_{i=1}^{n} x_{i} ≤ k + 1},

T_{n,k} = {(x_{1},…, x_{n}) : 0 ≤ x_{i} ≤ 1, |{i : x_{i} > x_{i+1}}| = k}.

Bizonyítsuk be, hogy vol (S_{n,k}) = vol (T_{n,k}), ahol vol (A) az A test térfogata. Megbeszélés: Április 18. (csütörtök), 4 óra, Riesz terem

Hajnal Péter