A Roth-tétel és a tiltott sorozatok
- Link másolása
- X (Twitter)
- Tumblr
Klaus Friedrich Roth (1925–2015) brit matematikus tíz éve halt meg, és 100 évvel ezelőtt éppen ezen a napon született. Többek között a számelmélet egyik alapvető problémájában, a diofantikus közelítések területén ért el áttörő sikert. Legismertebb eredménye a róla elnevezett Roth-tétel, az algebrai számok approximációjának alapvető tétele. Algebrai szám az olyan szám, ami gyöke, azaz megoldása egy racionális együtthatójú polinomnak. A tétel kimondja, hogy az irracionális algebrai számok nem közelíthetők túl sokféleképpen racionális számokkal, vagyis rosszul approximálhatók. Természetesen a „rosszul” fogalma volt az, amit sokáig tartott jól megfogni.
Roth ugyanakkor más területen is ért el jelentős eredményeket. Erdős Pál és Turán Pál 1936-os sejtése szerint (bár Erdős 1961-ben megjegyezte, hogy a problémát 1930 körül Issai Schur is felvetette) bármely pozitív természetes sűrűségű egész számokból álló halmaz végtelen sok 3-tagú számtani sorozatot tartalmaz. Ezt Klaus Roth 1952-ben bebizonyította, később Szemerédi Endre általánosította tetszőlegesen hosszú számtani sorozatokra. A természetes vagy aszimptotikus sűrűség a természetes számok egy végtelen részhalmazának az átlagos sűrűségét próbálja megragadni a diszkrét számegyenesen. A páratlan számok természetes sűrűsége például értelemszerűen 1/2.
Roth és Szemerédi munkássága együtt képezi a modern aritmetikai kombinatorika alapját, amely számos további kutatás kiindulópontja lett. Alábbi feladványunk is ehhez köthető, de bárki által megoldható.
Roth utóbbi tétele arról szól, hogy elég nagy és sűrű halmazokban mindig lesz 3-tagú számtani sorozat, de hogy konkrétan mennyit tudunk úgy kiválasztani maximum, hogy ne legyen, az egy nehéz probléma, nincs rá általános konstrukció és zárt képlet, éppen ezért, más megfogalmazásban, tulajdonképpen ennek a határértékéről szól a tétel. Az alábbi példában n = 27 esetén nézzük meg, hogy hogyan lehet 1-től n-ig úgy számokat kiválasztani, hogy ne legyen köztük 3-tagú számtani sorozat.
269. feladvány: Számtani sorozat nélkül
Vegyük 1-től 27-ig a pozitív egész számokat. Ki lehet-e belőlük választani 8-at úgy, hogy ne legyen köztük három tagú számtani sorozat?
Tipp
Gondolkodjunk 3-as számrendszerben!
Megoldás
Többet is ki lehet, de van egy szép és egyszerű konstrukció, amely a 3-as számrendszert használja. Először is vegyük észre, hogy mindegy, hogy 1-től 27-ig, vagy 0-tól 26-ig tekintjük a kezdő halmazt, mert a számtani sorozatok eltolhatók.
Írjuk le az 0-tól 26-ig tartó számokat 3-as számrendszerben, és válasszuk ki azokat a számokat, amelyekben egyáltalán nincs 2-es számjegy, azaz csak 0-k és 1-ek szerepelnek bennük. Ez pontosan az alábbi nyolc szám lesz: 000 (=0), 001 (=1), 010 (=3), 011 (=4), 100 (=9), 101 (=10), 110 (=12), 111 (=13).
Ha ezek közül bármelyik három számot kiválasztjuk, soha nem fognak számtani sorozatot alkotni. A 3-tagú számtani sorozat tagjaira ugyanis teljesül, hogy a középső szám a másik kettő átlaga, azaz a + c = 2b. Viszont egy csupa 0 és 1-et tartalmazó szám kétszerese csupa 0-t és 2-t fog tartalmazni (nem lesz túlcsordulása). Könnyen belátható, hogy egy ilyen szám nem állhat elő két másik hasonló típusú, de egymástól különböző szám összegeként. Ha ugyanis az utolsó jegye 2b-nek 0, akkor a-nak és c-nek is 0, ha pedig 2, akkor a-nak és c-nek is 1, és egyik esetben sincs túlcsordulás, vagyis ugyanez elmondható az előző számjegyről is, és ilyen módon minden számjegye egyező kell legyen a-nak és c-nek.
Ha szereted a fejtörőket, tekintsd meg korábbi feladványainkat is! Ha megjegyzésed lenne, vagy feladványt javasolnál, írj az eszventura@qubit.hu e-mail címre! Ha pedig tetszik a rovat, ezt a Vendégkönyvben kifejezésre juttathatod.
Az Ész Ventura feladványügyi rovat gazdája: Gáspár Merse Előd fizikus, kognitív kutató, társasjáték-fejlesztő és bűvész.
