Feladat: 3.29.
Bizonyítsuk be Schur tételének következő két speciális esetét: a) Ha az első öt pozitív egész számot két csoportba osztjuk, akkor az egyik csoportban van megoldása az x+y=z egyenletnek. Azaz van három szám valamelyik csoportban, amelyek közül az egyik a másik kettő összege. (Az x=y esetet is megengedjük.) Vagy másképp fogalmazva: valamelyik csoportban van két szám, amelyek különbsége is ugyanabban a csoportban van. b) Egy versenyen 3 ország összesen 16 versenyzője indult. Bizonyítandó, hogy van egy olyan versenyző, akinek helyezése megegyezik két másik honfitársa helyezési számának az összegével, vagy kétszer akkora, mint egy honfitársa helyezési száma. c)* Egy nemzetközi társaságnak 1978 tagja van 6 különböző országból. A tagokat 1-től 1978-ig számozták meg. Mutassuk meg, hogy van legalább egy olyan tag, akinek a sorszáma megegyezik két honfitársa sorszámának az összegével, vagy kétszer akkora, mint egy honfitársa sorszáma. (IMO 1978/6.) d)* Igazoljuk Schur tételét az általános formájában: Schur-tétel. Ha n elég nagy és az első n pozitív számot k csoportba osztjuk, akkor valamelyik csoportban van megoldása az x+y=z egyenletnek, vagyis valamelyik csoportban van három szám, amelyek közül az egyik a másik kettő összege.
 

Megoldás: 3.29
a) Ha egy szám az egyik csoportban van, akkor a kétszerese a másikban, különben kész vagyunk. Ezért az 1 és a 4 az egyik csoportban van, a 2 a másikban. Ha a 3 az 1 és 4-gyel van egy csoportban akkor ők hárman megfelelőek. Ha a 3 a 2-essel van egy csoportban, akkor mindkét csoportban olyan két elem van, amelyek összege 5, tehát az 5-öt bármelyikbe tesszük, ő és a másik két szám megfelelő.

b) A feladat állítása egyenértékű azzal az állítással, hogy a versenyzők között van kettő, akik honfitársak és helyezési számuk különbsége egy honfitársuk helyezési számával egyezik (ez utóbbi lehet a kettőjük közül való is).

Tegyük fel, hogy az állítás nem igaz. A skatulyaelv szerint van egy ország - ezt nevezük az első országnak -, amelyikből legalább hat versenyző indult. Legyen ezeknek a versenyzőknek a helyezése a1 < a2 <…< a6 . Ekkor az indirekt feltevésünk értelmében az ai - aj helyezésű versenyzők nem lehetnek az első orszából valók, így az

a2 - a1 , a3 - a1 , a4 - a1 , a5 - a1 , a6 - a1

helyezési számú versenyzők sem. Ők tehát csak a második vagy harmadik országból valók lehetnek. De akkor van közöttük három, akik ugyanabból az országból valók, például a másodikból valók a b1 < b2 < b3 helyezésű versenyzők. Nézzük a b2 - b1 , b3 - b2 és a b3 - b1 helyezésű versenyzőket. Indirekt feltevésünk szerint egyikük sem lehet a második országból. De nem lehet az első országból sem, hiszen minden bi felírható aj - a1 alakban, s így a különbségük felírható aj - ak alakban. E három versenyző tehát a harmadik országból való, ám az első kettő helyezési számának különbsége éppen a harmadik helyezési száma. Ez az ellentmondás bizonyítja állításunkat.

c) A feladat állítása egyenértékű azzal az állítással, hogy a társaságban van két tudós, akik honfitársak és sorszámuk különbsége egy honfitársuk sorszámával egyezik.

Tegyük fel, hogy az állítás nem igaz. Van egy ország - ezt nevezzük az első országnak -, amelyikből legalább 330-an vannak (skatulyaelv). Ha ezek sorszámai

a1 < a2 <…< a330 ,

akkor az indirekt feltevés szerint az ak - ai sorszámú tudósok egyike sem lehet az első országból való. Így az

a2 - a1 , a3 - a1 ,…, a330 - a1

sorszámú tudósok egyike sem A-beli, vagyis a többi öt ország egyikébe való. A skatulyaelv szerint van közöttük 66, akik egyazon országból valók - ezt az országot nevezzük a második országnak -, legyenek ezek a

b1 < b2 <… b66

sorszámú tudósok. Ekkor indirekt feltevésünk szeirnt a bj - bk sorszámú tudósok egyike sem lehet a második orszábeli tudós. De nem lehet az első országbeli sem, ugyanis minden bj - bk valamilyen l és m-re al - am alakú. Tehát a

b2 - b1 , b3 - b1 ,…, b66 - b1

sorszámú tudósok nem lehetnek sem az első, sem a második országból valók. Ez 65 tudós.

A gondolatmenetet folytatva kapunk 17 tudóst, akik egy harmadik országból valók. Ha ezek c1 < c2 <…< c17 , akkor ismét mondhatjuk, hogy a ck - cj sorszámú tudósok sem lehetnek sem e harmadik országból, sem az első kettőből valók. (Ugyanis minden ilyen különbség felírható két b különbségeként, s azok viszont két a különbségeként.) Kaptunk 16 tudóst, akik csak a maradó három országból lehetnek, és helyezési számuk különbsége is csak e három országból érkező versenyzőé lehet. Innentől a feladat megfelel a b) feladatnak.

Mielőtt d)-t bebizonyítanánk, adunk egy elegánsabb bizonyítást a)-ra, mert a gondolatmenet a d) részben is használató lesz (és segítségével c)-re is új bizonyítást nyerünk).

Legyen adva az első öt számnak egy felosztása két csoportra. Vegyük azt a gráfot, amelynek pontjai az 1,2,3,4,5,6 számok. Az i és a j között futó élt színezzük 1-essel, ha |i-j| az első csoportban van, és 2-essel, ha |i-j| a második csoportban van. Két szám különbsége legalább 1, legfeljebb 5, így minden élt kiszínezünk 1-essel vagy 2-essel. A 3.3. feladat szerint ebben a gráfban van három pont, amelyek között futó élek azonos színűek. Legyen ez a három pont a>b>c. Ezek szerint |a-b|=a-b, |b-c|=b-c és |c-a|=a-c azonos csoportban van. Márpedig az első kettő összege éppen a harmadik szám. d) A bizonyítás ugyanúgy megy, csak a 3.3. feladat helyett a 3.16. feladatot kell használni: ha egy 1+k!(1/0!+1/1!+…+1/k!) pontú teljes gráf éleit k színnel színezzük, akkor van benne egyszínű háromszög. Vagyis ha n legalább ekkora, akkor a Schur-tétel állítása teljesül: a gráf pontjai a)-hoz hasonlóan az 1,2,…,n számok, az i és j között futó élt annyiadik színűre színezzük, amennyiedik csoportban |i-j| van. Ekkor van egyszínű háromszög, és innen az a) rész befejezése ,,működik".