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