Feladat: 1978. évi Nemzetközi Matematika Diákolimpia 23. feladata Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1978/október, 54 - 55. oldal  PDF  |  MathML 
Témakör(ök): Indirekt bizonyítási mód, Teljes indukció módszere, Teljesgráfok, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 1978/szeptember: 1978. évi Nemzetközi Matematika Diákolimpia 23. feladata

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 6⋅329=1974<1978, azért valamelyik országból, A-ból legalább 330 tagnak kellett jönnie, legyenek sorszámaik

a1<a2<...<a330.
Tekintsük az a2-a1,a3-a1,...,a330-a1, sorszámú tagokat. Ezek egyike sem lehet A-beli, hiszen akkor volna a feltételnek megfelelő három tag. Így mind a 329 tag a megmaradt 5 ország valamelyikéből jött, és mivel 5⋅65=325<329, közülük egy országból, B-ből legalább 66-an jöttek, sorszámuk legyen
b1<b2<...<b66.
Nézzük most a b2-b1,b3-b1,...,b66-b1 sorszámú tagokat. Ezek egyike sem jöhetett a B országból, ám az A országból sem. Ugyanis ha a bi-bj=(am-a1)-(an-a1)=am-an sorszámú tag A-beli lenne, ismét találnánk három, a feltételnek megfelelő tagot. Így a fenti 65 tag 4 országból jött, így valamelyik országból, C-ből legalább 17-en jöttek, sorszámuk
c1<c2<...<c17.
Az előzőekhez hasonlóan a c2-c1,c3-c1,...,c17-c1 sorszámú tagok csak három országból jöhettek, így a D országból legalább 6-an voltak:
d1<d2...<d6.
A d2-d1,d3-d1,...,d6-d1| sorszámú tagok közül legalább 3 jött az E országból
e1<e2<e3,
végül az f1=e2-e1, illetve f2=e3-e2 sorszámú tagok csak a hatodik, F országból jöhettek. Ám ekkor az f2-f1 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
kn=n!(1+11!+12!+...+1n!)+1

csúcsú teljes gráf éleit n 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 n=1-re nyilván igaz, mivel k1=3. Tekintsünk most egy kn+1 szögpontú gráfot és annak tetszőleges csúcsát. Ebből a csúcsból kn+1-1 él indul ki, minden él (n+1) szín valamelyikével színezve. Mivel (n+1)⋅(kn-1)=kn+1-2<kn+1-1, azért biztosan van kn 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 kn végpont közötti élek csak n 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 1978 csúcsú gráfot, melynek csúcsai 1-től 1978-ig vannak megszámozva. Az i és j 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 |i-j| sorszámú tag melyik országból jött. Mivel k6=1958<1978, azért van egyszínű háromszög, a csúcsok száma legyen i<j<k. Ekkor a j-i,k-j és a k-i sorszámú tagok ugyanabból az országból valók, és (j-i)+(k-j)=(k-i), ahogyan azt kívántuk.
 

Megjegyzések. 1. Elképzelhető, hogy j-i=k-j. 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 n ország esetén ha a társaságnak legalább kn tagja van, létezik a kérdezett tulajdonságú tag. Igazolható, hogy ha g(n)-nel jelöljük a legkisebb olyan tagszámot, amelyre ilyen tulajdonságú társaság létezik, akkor
3n+12≤g(n)≤n!(1+11!+...+11!)+1.
Azt is tudjuk, hogy g(1)=3,g(2)=5,g(3)=14.g(4) pontos értéke nem ismeretes.