Feladat: B.4257 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Damásdi Gábor ,  Éles András ,  Énekes Péter ,  Kiss Melinda Flóra ,  Mester Márton ,  Mészáros András ,  Perjési Gábor ,  Weisz Ágoston 
Füzet: 2011/március, 155 - 157. oldal  PDF file
Témakör(ök): Feladat, Kombinációk, Teljesgráfok, Teljes indukció módszere
Hivatkozás(ok):Feladatok: 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.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

 
Megoldás. Az űrhajósok legyenek egy (a közönséges értelemben teljes) gráf csúcsai. A csúcshármasokat színezzük ki két színnel, kékkel és pirossal. Azt kell megmutatni, hogy ha a csúcsok száma legalább 11 000, akkor vagy van 5 olyan csúcs, amelyben bármelyik hármas színe kék, vagy van 4 olyan csúcs, amelyben egyik hármas színe sem kék. Tehát az a kérdés, hogy legfeljebb mennyi R3(5,4), vagyis a legkisebb olyan n=R3(5,4) szám, amelyre ha egy n csúcsú gráfban két színnel ‐ kékkel és pirossal ‐ színezzük a hármasokat, akkor vagy van 5 olyan csúcs, amelyek közül bármely hármas kék, vagy van 4 olyan csúcs, amelyben bármely hármas színe piros. Általában az a kérdés, hogy legfeljebb mennyi R3(a,b) értéke.
* Megmutatjuk, hogy
R3(a,b)R2(R3(a-1,b),R3(a,b-1))+1.
Legyen R2(R3(a-1,b),R3(a,b-1))+1=k. Tekintsünk egy k csúcsú teljes gráfot, és abban a csúcshármasok halmazának tetszőleges színezését. Vegyünk ki egy csúcsot, az legyen A. A megmaradt k-1 csúcsú gráfban a B és C csúcsokat összekötő él színe legyen kék, ha az ABC csúcshármas színe kék, és legyen piros, ha az ABC csúcshármas színe piros. R2(R3(a-1,b),R3(a,b-1)) azt jelenti, hogy a k-1 csúcsú gráfban vagy van R3(a-1,b) csúcs, amiben bármely él kék, vagy van R3(a,b-1) csúcs, amiben bármely él piros.
Nézzük először azt az esetet, amikor van R3(a-1,b) csúcs, amiben bármely él színe kék. Ha van R3(a-1,b) csúcs, akkor ez azt jelenti, hogy közülük vagy van a-1 csúcs úgy, hogy bármely hármas színe kék, vagy van b csúcs úgy, hogy bármely hármas színe piros. Tegyük fel, hogy nem volt a-1 csúcs úgy, hogy közülük bármely hármas színe kék. Ekkor volt olyan b csúcs, hogy bármely hármas színe piros, ezért az eredeti gráfban is van b olyan csúcs, hogy bármely hármas színe piros. Ha pedig volt a-1 olyan csúcs, hogy bármely hármas színe kék, akkor ezekhez a csúcsokhoz vegyük hozzá A-t. Mivel az a-1 csúcs között bármelyik hármas színe kék, és bármely él színe kék, emiatt ha hozzávesszük A-t, akkor az bármelyik pontpárral egy kék hármast alkot, tehát az a csúcs közül bármely hármas színe kék. Ekkor az eredeti gráfban is volt a olyan csúcs, amiben bármely hármas színe kék. Így igaz, hogy az eredeti k csúcsú gráfban vagy van a olyan csúcs, hogy bármely hármas színe kék, vagy van b olyan csúcs, hogy bármely hármas színe piros.
Most nézzük azt ez esetet, amikor nincs R3(a-1,b) csúcs, amiben bármely él kék. Ekkor van R3(a,b-1) csúcs, amiben bármely él piros. Ha van R3(a,b-1) csúcsunk, akkor azok közül vagy van a csúcs úgy, hogy bármely hármas színe kék, vagy van b-1 csúcs úgy, hogy bármely hármas színe piros. Ha van a csúcs úgy, hogy bármely hármas színe kék, akkor az eredeti k csúcsú gráfban is van a csúcs, úgy, hogy bármely hármas színe kék. Ha nincs a olyan csúcs, hogy bármely hármas színe kék, akkor van b-1 olyan csúcs, hogy bármely hármas színe piros. Ezekhez vegyük hozzá A-t. Mivel a b-1 csúcs közül bármely hármas színe piros, és bármely él színe is piros, emiatt az A bármely pontpárral piros hármast alkot. Ekkor az eredeti k csúcsú gráfban van b olyan pont, hogy bármely hármas színe piros. Ekkor is igaz, hogy vagy van a csúcs, hogy bármely hármas színe kék, vagy van b csúcs, hogy bármely hármas színe piros. Tehát valóban
R3(a,b)R2(R3(a-1,b),R3(a,b-1))+1.

Ismert tétel, hogy
R2(a,b)(a+b-2a-1)+1.
Bebizonyítom, hogy R3(a,3)=a. Ehhez először megmutatom, hogy R3(a,3)a. Ha ugyanis R3(a,3) kisebb lenne a-nál, akkor ez azt jelentené, hogy R3(a,3) csúcs esetén mindenképpen van piros színű hármas, ami nyilván nem igaz; így R3(a,3)a. Viszont a csúcs esetén vagy van piros hármas, vagy pedig az a csúcsból képezhető valamennyi hármas kék, tehát R3(a,3)a, ezért valóban R3(a,3)=a.
Mindezeket felhasználva:
R3(5,4)R2(R3(4,4),R3(5,3))+1,
és tudjuk, hogy R3(5,3)=5. Valamint
R3(4,4)R2(R3(3,4),R3(4,3))+1.
Mivel R3(3,4)=R3(4,3)=4, emiatt
R3(4,4)(4+4-24-1)+1=(63)+1=21,
így
R3(5,4)R2(21,5)+1(21+5-221-1)+1=(244)+1=10627,
vagyis már 10 627 pontnál is igaz, hogy vagy van 5 olyan pont, ahol bármely hármas kék, vagy van 4 olyan csúcs, hogy bármely hármas színe piros. Tehát elég 11 000 űrhajós ahhoz, hogy a feladat követelményei teljesüljenek.
 

Megjegyzés. A megoldásban felhasznált
R2(a,b)(a+b-2a-1)+1
összefüggés például az a+b szerinti indukcióval látható be, a binomiális együtthatókra teljesülő
(a+b-2a-1)=(a+b-3a-2)+(a+b-3a-1)
azonosság segítségével. Az állítás például megtalálható Lovász László: Kombinatorikai problémák és feladatok c. könyvében (az állítás a 101. oldalon levő 1.(a) feladatban, a megoldás pedig az 577. oldalon olvasható.)


*Legalább R2(a,b) számú csúcsot tartalmazó teljes gráfban ha két színnel, kékkel és pirossal színezzük az éleket, vagy van a db olyan csúcs, amelyek közül bármely kettő kék, vagy van b db olyan csúcs, amelyek közül bármely kettő piros.