„Van der Waerden-tétel” változatai közötti eltérés

[ellenőrzött változat][ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló
Nincs szerkesztési összefoglaló
1. sor:
'''Van der Waerden tétele''' a [[kombinatorikus számelmélet]] és általában a [[kombinatorika]] egyik fontos tétele.
 
A tétel szerint, ha <math>k,r</math> egynél nagyobb természetes számok, akkor van olyan (legkisebb) <math>W(k,r)</math> természetes szám, hogy a következő állítás igaz: akárhogyan osztjuk <math>r</math> részreosztályba az <math>\{1,2,\dots,W(k,r)\}</math> halmazt, valamelyik részosztály tartalmaz <math>k</math> tagú számtani sorozatot.
 
== Bizonyítás ==
 
Az állítás igazolása ''k''-ra vonatkozó indukcióval történik. A ''k''=2 eset nyilvánvaló: ha a az 1-től ''r''+1-ig terjedő természetes számokat ''r'' részreosztályba osztjuk, a [[skatulyaelv]] szerint valamelyik részosztály tartalmaz két elemet, ezek pedig kéttagú számtani sorozatot alkotnak. Másfelől, 1-től ''r''-ig az egész számokat külön-külön osztályba sorolva nincs egy osztályba tartozó, kéttagú számtani sorozat. Tehát <math>W(2,r)=r+1</math>.
 
Tegyük fel, hogy ''k''-ra már tudjuk az eredményt és <math>W(k,r)</math> létezését szeretnénk igazolni. Ehhez készítsük el a következő <math>f(0),f(1),\dots,f(r)</math> sorozatot: <math>f(0)=1</math> és ha <math>f(s)</math> megvan, legyen <math>f(s+1)=2MN</math>, ahol <math>N=f(s)</math> és <math>M=W(k,r^N)</math>. ''s''-re indukcióval igazoljuk a következő állítást: ha az <math>\{1,\dots,f(s)\}</math> számokat ''r'' színnel színezzük, akkor vagy van ''k''+1 hosszú egyszínű számtani sorozat, vagy van ''s'' olyan ''k''+1 hosszú számtani sorozat, <math>A_1,\dots,A_s</math>, hogy az <math>A_i</math>-k utolsó tagja közös, e tagot elhagyva pedig minden <math>A_i</math> egyszínű és e színek különbözők.
 
Ha ezt beláttuk, akkor <math>W(k+1,r)</math> választható <math>f(r)</math>-nek.
16. sor:
== Történet ==
 
[[Issai Schur]] eredeti kérdése úgy hangzott, igaz-e, hogy minden ''k'' természetes számhoz van olyan ''N'' természetes szám, hogy ha az 1,…,''N'' számokat két részreosztályba osztjuk, valamelyik mindenképpen tartalmaz ''k''-tagú számtani sorozatot. Az általános eredményt [[Bartel Leendert van der Waerden]] 1927-ben igazolta.
 
== Lásd még ==