Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4257. (March 2010)

B. 4257. A group of 11 000 astronauts are trained for a Mars mission. Given that from any 4 of them it is possible to select a suitable crew of 3 members for the landing module, prove that it is possible to select 5 astronauts such that any 3 of them form a suitable crew.

(Kvant)

(5 pont)

Deadline expired on April 12, 2010.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

13 students sent a solution.
5 points: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 points:Dudás 002 Zsolt.
0 point:4 students.

Problems in Mathematics of KöMaL, March 2010