Van der Waerden-tétel

A Wikipédiából, a szabad enciklopédiából

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

A tétel szerint, ha k,r egynél nagyobb természetes számok, akkor van olyan (legkisebb) W(k,r) természetes szám, hogy a következő állítás igaz: akárhogyan osztjuk r részre az \{1,2,\dots,W(k,r)\} halmazt, valamelyik rész tartalmaz k tagú számtani sorozatot.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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észre osztjuk, valamelyik rész tartalmaz két elemet, ezek pedig kéttagú számtani sorozatot alkotnak. Tehát W(2,r)=r+1.

Tegyük fel, hogy k-ra már tudjuk az eredményt és W(k,r) létezését szeretnénk igazolni. Ehhez készítsük el a következő f(0),f(1),\dots,f(r) sorozatot: f(0)=1 és ha f(s) megvan, legyen f(s+1)=2MN, ahol N=f(s) és M=W(k,r^N). s-re indukcióval igazoljuk a következő állítást: ha az \{1,\dots,f(s)\} 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, A_1,\dots,A_s, hogy az A_i-k utolsó tagja közös, e tagot elhagyva pedig minden A_i egyszínű és e színek különbözők.

Ha ezt beláttuk, akkor W(k+1,r) választható f(r)-nek.

Többdimenziós általánosítás[szerkesztés | forrásszöveg szerkesztése]

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

Történet[szerkesztés | forrásszöveg szerkesztése]

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észre 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 | forrásszöveg szerkesztése]

Irodalom[szerkesztés | forrásszöveg szerkesztése]

  • 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.