Van der Waerden-tétel

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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.