kombinatorikai állítás From Wikipedia, the free encyclopedia
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.
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.
A tétel többdimenziós változatát Gallai Tibor igazolta.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.