Van der Waerden-tétel

kombinatorikai állítás

Van der Waerden tétele a kombinatorikus számelmélet és általában a kombinatorika egyik fontos tétele.

A tétel szerint, ha egynél nagyobb természetes számok, akkor van olyan (legkisebb) természetes szám, hogy a következő állítás igaz: akárhogyan osztjuk osztályba az halmazt, valamelyik osztály tartalmaz tagú számtani sorozatot.

Bizonyítás szerkesztés

Az állítás igazolása k-ra vonatkozó indukcióval történik. A k=2 eset nyilvánvaló: ha az 1-től r+1-ig terjedő természetes számokat r osztályba osztjuk, a skatulyaelv szerint valamelyik osztá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  .

Tegyük fel, hogy k-ra már tudjuk az eredményt és   létezését szeretnénk igazolni. Ehhez készítsük el a következő   sorozatot:   és ha   megvan, legyen  , ahol   és  . s-re indukcióval igazoljuk a következő állítást: ha az   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,  , hogy az  -k utolsó tagja közös, e tagot elhagyva pedig minden   egyszínű és e színek különbözők.

Ha ezt beláttuk, akkor   választható  -nek.

Többdimenziós általánosítás szerkesztés

A tétel többdimenziós változatát Gallai Tibor igazolta.

Történet szerkesztés

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 osztá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 szerkesztés

Irodalom szerkesztés

  • B. L. van der Waerden: Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk., 15(1927), 212-216.
  • B. L. van der Waerden: Ötlet és meggondolás a matematikában. A Baudet-sejtés bizonyítása, Matematikai Lapok, 22(1971), 25-30.