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. I. megoldás. Tegyük fel, hogy az állítás nem igaz, ebből ellentmondásra fogunk jutni. Mivel , azért valamelyik országból, -ból legalább tagnak kellett jönnie, legyenek sorszámaik Tekintsük az , sorszámú tagokat. Ezek egyike sem lehet -beli, hiszen akkor volna a feltételnek megfelelő három tag. Így mind a tag a megmaradt ország valamelyikéből jött, és mivel , közülük egy országból, -ből legalább -an jöttek, sorszámuk legyen Nézzük most a sorszámú tagokat. Ezek egyike sem jöhetett a országból, ám az országból sem. Ugyanis ha a sorszámú tag -beli lenne, ismét találnánk három, a feltételnek megfelelő tagot. Így a fenti tag országból jött, így valamelyik országból, -ből legalább -en jöttek, sorszámuk Az előzőekhez hasonlóan a sorszámú tagok csak három országból jöhettek, így a országból legalább -an voltak: A sorszámú tagok közül legalább jött az országból végül az , illetve sorszámú tagok csak a hatodik, országból jöhettek. Ám ekkor az sorszámú tag sehonnan sem jöhetett volna, ellentmondás, ami éppen az állítást bizonyítja.
II. megoldás. A következő állítást igazoljuk teljes indukcióval: ha egy legalább | | csúcsú teljes gráf éleit színnel kiszínezzük, akkor biztosan lesz benne egyszínű háromszög (azaz három csúcs úgy, hogy köztük bármely él ugyanolyan színű).
Az állítás -re nyilván igaz, mivel . Tekintsünk most egy szögpontú gráfot és annak tetszőleges csúcsát. Ebből a csúcsból él indul ki, minden él szín valamelyikével színezve. Mivel , azért biztosan van egyszínű él is, mondjuk fekete (l. ábra). Tekintsük ezek végpontjait. Ha a végpontok között van fekete él, máris találtunk egyszínű (fekete) háromszöget. Ha nincs, akkor a végpont közötti élek csak különböző színnel vannak színezve, és ekkor az indukciós feltevésünk értelmében már itt lesz egyszínű háromszög. Tekintsünk most egy csúcsú gráfot, melynek csúcsai -től -ig vannak megszámozva. Az és csúcs közti élet hat különböző szín valamelyikével színezzük ki, attól függően, hogy az sorszámú tag melyik országból jött. Mivel , azért van egyszínű háromszög, a csúcsok száma legyen . Ekkor a és a sorszámú tagok ugyanabból az országból valók, és , ahogyan azt kívántuk. Megjegyzések. 1. Elképzelhető, hogy . Ekkor nem három, hanem csak két tag sorszámát kapjuk, de az egyik sorszám éppen kétszer akkora, mint a másik. 2. A második megoldásból az is kiolvasható, hogy ország esetén ha a társaságnak legalább tagja van, létezik a kérdezett tulajdonságú tag. Igazolható, hogy ha -nel jelöljük a legkisebb olyan tagszámot, amelyre ilyen tulajdonságú társaság létezik, akkor | | Azt is tudjuk, hogy pontos értéke nem ismeretes. |