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  |  MathML
Témakör(ök):	Feladat, Kombinációk, Teljesgráfok, Teljes indukció módszere
Hivatkozás(ok):	Feladatok: 2010/március: B.4257

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 $R_3\left(\mathrm{5,4}\right)$, vagyis a legkisebb olyan $n=R_3\left(\mathrm{5,4}\right)$ 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 $R_3\left(a\mathrm{,}b\right)$ értéke. ${}^{*}$ Megmutatjuk, hogy $\begin{array}{c}{\displaystyle R_3\left(a\mathrm{,}b\right)\le R_2\left(R_3\left(a-\mathrm{1,}b\right)\mathrm{,}{R}_3\left(a\mathrm{,}b-1\right)\right)+1.}\end{array}$ Legyen $R_2\left(R_3\left(a-\mathrm{1,}b\right)\mathrm{,}{R}_3\left(a\mathrm{,}b-1\right)\right)+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. $R_2\left(R_3\left(a-\mathrm{1,}b\right)\mathrm{,}{R}_3\left(a\mathrm{,}b-1\right)\right)$ azt jelenti, hogy a $k-1$ csúcsú gráfban vagy van $R_3\left(a-\mathrm{1,}b\right)$ csúcs, amiben bármely él kék, vagy van $R_3\left(a\mathrm{,}b-1\right)$ csúcs, amiben bármely él piros. Nézzük először azt az esetet, amikor van $R_3\left(a-\mathrm{1,}b\right)$ csúcs, amiben bármely él színe kék. Ha van $R_3\left(a-\mathrm{1,}b\right)$ 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 $R_3\left(a-\mathrm{1,}b\right)$ csúcs, amiben bármely él kék. Ekkor van $R_3\left(a\mathrm{,}b-1\right)$ csúcs, amiben bármely él piros. Ha van $R_3\left(a\mathrm{,}b-1\right)$ 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 $\begin{array}{c}{\displaystyle R_3\left(a\mathrm{,}b\right)\le R_2\left(R_3\left(a-\mathrm{1,}b\right)\mathrm{,}{R}_3\left(a\mathrm{,}b-1\right)\right)+1.}\end{array}$ Ismert tétel, hogy $\begin{array}{c}{\displaystyle R_2\left(a\mathrm{,}b\right)\le \left(\genfrac{}{}{0ex}{}{a+b-2}{a-1}\right)+1.}\end{array}$ Bebizonyítom, hogy $R_3\left(a\mathrm{,3}\right)=a$. Ehhez először megmutatom, hogy $R_3\left(a\mathrm{,3}\right)\ge a$. Ha ugyanis $R_3\left(a\mathrm{,3}\right)$ kisebb lenne $a$-nál, akkor ez azt jelentené, hogy $R_3\left(a\mathrm{,3}\right)$ csúcs esetén mindenképpen van piros színű hármas, ami nyilván nem igaz; így $R_3\left(a\mathrm{,3}\right)\ge 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 $R_3\left(a\mathrm{,3}\right)\le a$, ezért valóban $R_3\left(a\mathrm{,3}\right)=a$. Mindezeket felhasználva: $\begin{array}{c}{\displaystyle R_3\left(\mathrm{5,4}\right)\le R_2\left(R_3\left(\mathrm{4,4}\right)\mathrm{,}{R}_3\left(\mathrm{5,3}\right)\right)+\mathrm{1,}}\end{array}$ és tudjuk, hogy $R_3\left(\mathrm{5,3}\right)=5$. Valamint $\begin{array}{c}{\displaystyle R_3\left(\mathrm{4,4}\right)\le R_2\left(R_3\left(\mathrm{3,4}\right)\mathrm{,}{R}_3\left(\mathrm{4,3}\right)\right)+1.}\end{array}$ Mivel $R_3\left(\mathrm{3,4}\right)=R_3\left(\mathrm{4,3}\right)=4$, emiatt $\begin{array}{c}{\displaystyle R_3\left(\mathrm{4,4}\right)\le \left(\genfrac{}{}{0ex}{}{4+4-2}{4-1}\right)+1=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+1=\mathrm{21,}}\end{array}$ így $\begin{array}{c}{\displaystyle R_3\left(\mathrm{5,4}\right)\le R_2\left(\mathrm{21,5}\right)+1\le \left(\genfrac{}{}{0ex}{}{21+5-2}{21-1}\right)+1=\left(\genfrac{}{}{0ex}{}{24}{4}\right)+1=10\mathrm{627,}}\end{array}$ 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 $\begin{array}{c}{\displaystyle R_2\left(a\mathrm{,}b\right)\le \left(\genfrac{}{}{0ex}{}{a+b-2}{a-1}\right)+1}\end{array}$ összefüggés például az $a+b$ szerinti indukcióval látható be, a binomiális együtthatókra teljesülő $\begin{array}{c}{\displaystyle \left(\genfrac{}{}{0ex}{}{a+b-2}{a-1}\right)=\left(\genfrac{}{}{0ex}{}{a+b-3}{a-2}\right)+\left(\genfrac{}{}{0ex}{}{a+b-3}{a-1}\right)}\end{array}$ 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 $R_2\left(a\mathrm{,}b\right)$ 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.