A B. 4257. feladat (2010. március)

B. 4257. 11 000 űrhajósból álló csoportot készítettek fel a Mars-utazásra. Tudjuk, hogy bármely 4 űrhajós közül kiválasztható 3 olyan, akik megfelelő személyzetet alkotnak a leszálló modulhoz. Bizonyítsuk be, hogy kiválasztható 5 űrhajós úgy, hogy közülük bármelyik 3 megfelelő személyzet legyen.

(5 pont)

A beküldési határidő 2010. április 12-én LEJÁRT.

Megoldás. Vizsgáljuk meg először, hogy kiválasztható-e 4 jó űrhajós, vagyis 4 olyan űrhajós, hogy közülük bármelyik 3 megfelelő személyzetet alkosson. Vegyünk egy tetszőleges $\displaystyle A$ űrhajóst. Két másik űrhajóst kössünk össze egy piros madzaggal, ha $\displaystyle A$-val együtt megfelelő személyzetet alkotnak, ellenkező esetben pedig kék madzaggal kössük össze őket. Ha van 4 űrhajós, melyek közül bármely kettő kék madzaggal van összekötve, akkor vegyünk ezek közül hármat, legyenek ezek $\displaystyle B,C,D$. Az $\displaystyle A,B,C,D$ űrhajósok közül csak $\displaystyle B,C,D$ alkothat megfelelő személyzetet, tehát a feladat feltétele szerint nekik mindenképpen megfelelő személyzetet kell alkotniuk. Vagyis ha 4 űrhajós közül bármelyik kettő kék madzaggal van összekötve, akkor közülük bármelyik 3 megfelelő személyzet lesz. Ha pedig van 4 űrhajós, melyek közül bármely kettő piros madzaggal van összekötve, akkor a feladat feltételének megfelelően válasszunk ki közülük hármat, akik megfelelő személyzetet alkotnak, legyenek most ezek $\displaystyle B,C,D$. Ekkor az $\displaystyle A,B,C,D$ űrhajósok közül bármely 3 megfelelő személyzetet alkot.

Jelölje tehát $\displaystyle R(a,b)$ azt a legkisebb $\displaystyle n$ természetes számot, amelyre igaz, hogy ha egy $\displaystyle n$ csúcsú teljes gráf minden élét piros vagy kék színűre festjük, akkor vagy lesz benne egy $\displaystyle a$ csúcsú teljes részgráf, amelyiknek minden éle piros, vagy pedig egy $\displaystyle b$ csúcsú teljes részgráf, amelyiknek minden éle kék. A fenti okoskodás szerint, ha az $\displaystyle A$ űrhajós mellé kiválasztunk $\displaystyle R(4,4)$ további űrhajóst, akkor közöttük lesz 4 jó űrhajós. Más szóval, bármely $\displaystyle R(4,4)+1$ űrhajós között lesz 4 olyan, hogy közülük bármely 3 jó személyzetet alkot.

Nyilván $\displaystyle R(2,n)=R(n,2)=n$, és nem nehéz megmutatni, hogy $\displaystyle a,b\ge 3$ esetén $\displaystyle R(a,b)\le R(a,b-1)+R(a-1,b)$, hiszen ha egy $\displaystyle R(a,b-1)+R(a-1,b)$ szögpontú teljes gráf minden élét piros vagy kék színűre festjük, akkor egy csúcsát kiválasztva, abból vagy kiindul legalább $\displaystyle R(a,b-1)$ kék színű él, vagy pedig kiindul legalább $\displaystyle R(a-1,b)$ piros színű él. Ebből az egyenlőtlenségből $\displaystyle a+b$ szerinti teljes indukcióval adódik, hogy

$\displaystyle R(a,b)\le {a+b-2\choose a-1}={a+b-2\choose b-1}.$

Ezek szerint $\displaystyle R(4,4)+1\le 21$. Tekintsünk most $\displaystyle R(21,5)+1\le {24\choose 4}+1=10627<11000$ űrhajóst. Vegyünk megintcsak egy tetszőleges $\displaystyle A$ űrhajóst, két másik űrhajóst pedig kössünk össze egy piros madzaggal, ha $\displaystyle A$-val együtt megfelelő személyzetet alkotnak, ellenkező esetben meg kékkel. Ha van 5 űrhajós, melyek közül bármely kettő kék madzaggal van összekötve, akkor a már látott gondolatmenet szerint közülük bármely 3 jó személyzetet kell, hogy alkosson. Ha nincs 5 ilyen űrhajós, akkor viszont kell lennie 21 olyan űrhajósnak, melyek közül bármely kettő piros madzaggal van összekötve. Mint láttuk, ezek között van 4 jó űrhajós, akik mellé még $\displaystyle A$-t kiválasztva kapunk 5 jó űrhajóst.

Statisztika:

13 dolgozat érkezett.
5 pontot kapott:	Damásdi Gábor, Éles András, Énekes Péter, Kiss 902 Melinda Flóra, Mester Márton, Mészáros András, Perjési Gábor, Weisz Ágoston.
4 pontot kapott:	Dudás 002 Zsolt.
0 pontot kapott:	4 versenyző.

A KöMaL 2010. márciusi matematika feladatai