Az A. 720. feladat (2018. március)

A. 720. Egy pozitív egész számot elevennek nevezünk, ha van \(\displaystyle 10^{10^{100}}\)-nál nagyobb prímosztója. Bizonyítsuk be, hogy ha \(\displaystyle S\) eleven pozitív egészekből álló végtelen halmaz, akkor létezik olyan végtelen \(\displaystyle T\) részhalmaza, melynek bármely véges nemüres részhalmazában az elemek összege eleven szám.

(5 pont)

A beküldési határidő 2018. április 10-én LEJÁRT.

Megoldási ötletek. Hogy alkalmas végtelen \(\displaystyle T\subset S\)-t találjunk, természetesen \(\displaystyle S\)-nek megfelelő véges \(\displaystyle T_1\subsetneq T_2\subsetneq \dots\) részhalmazainak láncának létezését igazoljuk, majd \(\displaystyle T=\bigcup_{i=1}^\infty T_i\) választással élünk. (Magyarul, \(\displaystyle T\) rekurzióval lesz megadva.)

Legyen \(\displaystyle E\) az eleven számok halmaza és \(\displaystyle E^c\) a nem eleven számok halmaza. Jegyezzük meg: \(\displaystyle E^c\) az \(\displaystyle m\) darab \(\displaystyle p\le 10^{10^{100}}\) prímből képezhető szorzatokat tartalmazza.

Legtermészetesebb ötlet lenne belátni, hogy bármely \(\displaystyle \{a_1<\dots<a_k\}\subset S\)-hez van \(\displaystyle a_{k+1}\in S\) (\(\displaystyle a_{k+1}>a_k\)), melyre \(\displaystyle \{a_1,\dots,a_k,a_{k+1}\}\)-ben minden véges összeg \(\displaystyle \in E\). Ez azonban nem működik: adott \(\displaystyle a_1\in S\)-hez lehet, hogy csak olyan \(\displaystyle a_2\in S\) választható, melyre \(\displaystyle a_1+a_2\in E^c\) (bizonyításáért lásd a 2. megjegyzést).

Ehelyett próbálkozhatunk egyszerre \(\displaystyle N\) darab \(\displaystyle T=\{a_{i_1},a_{i_2},\dots\}\) halmazjelölt indításával: elég, ha az \(\displaystyle N\) jelölt közül egyetlent sikerül végtelen sokszor meghosszabbítani.

Megoldás. Képzeljünk el \(\displaystyle N=2^m+1\) darab dobozt. A dobozokban egymás után helyezzük el \(\displaystyle S\)-nek az \(\displaystyle a_1,a_2,\dots\) elemeit, ügyelve arra, hogy

\(\displaystyle \bullet\) minden dobozban az elemek összegei eleven számok,

\(\displaystyle \bullet\) \(\displaystyle a_{j+1}>a_1+a_2+\dots+a_j\): ez, mint indukcióval látható, biztosítja, hogy az \(\displaystyle a_1,a_2,\dots\) számok és véges összegeik páronként különbözőek legyenek.

Állítás. Ha már ily módon az \(\displaystyle a_1,\dots,a_k\in S\) számokat elhelyeztük, akkor alkalmas \(\displaystyle a_{k+1}\in S\)-et is elhelyezhetünk megfelelő módon valamelyik dobozban.

Bizonyítás. Tegyük fel indirekt, hogy ez nem lehetséges, és jelölje \(\displaystyle \mathcal{A}\) az \(\displaystyle a_1,a_2,\dots,a_k\)-ból képezhető \(\displaystyle (2^k-1)\)-féle összeg halmazát. Ekkor ha \(\displaystyle a_{k+1}\) nem helyezhető el egyik dobozban sem, megadható

\(\displaystyle \sigma_1,\sigma_2,\dots,\sigma_N\in \mathcal{A}\)

(minden doboz ad legalább egyet) úgy, hogy

\(\displaystyle a_{k+1}+\sigma_1,a_{k+1}+\sigma_2,\dots,a_{k+1}+\sigma_N\in E^c.\)

Minden lehetséges \(\displaystyle a_{k+1}\)-hez rendelhető egy-egy ilyen \(\displaystyle (\sigma_1,\dots,\sigma_N)\) sorozat, de ez a sorozat véges sokféle lehet. Indirekt feltevésünk miatt végtelen sok ilyen \(\displaystyle a_{k+1}\in S\) van, így skatulya-elv szerint van \(\displaystyle s_1,s_2,\dots,s_N\in\mathcal{A}\) (páronként különbözőek) úgy, hogy végtelen sok \(\displaystyle a\in S\)-re

Ez azonban csak véges sokféle \(\displaystyle a\) pozitív egészre teljesülhet. Az A.717. feladat trükkjét alkalmazva, írjunk fel minden \(\displaystyle n\) pozitív egészt \(\displaystyle n=dx^2\) alakban, ahol \(\displaystyle d\) négyzetmentes (semely prím négyzetével sem osztható). Ha \(\displaystyle n\in E^c\), akkor \(\displaystyle d\) értéke \(\displaystyle 2^m\)-féle lehet, így \(\displaystyle E^c\) lefedhető

\(\displaystyle 2^m\quad \text{darab} \quad \mathcal{N}_d=\{d\cdot 1^2,d\cdot 2^2,\dots\}\)

alakú halmazzal. Ha tehát \(\displaystyle (\star)\) valamely \(\displaystyle a\)-val fennáll, akkor skatulya-elv szerint lesz \(\displaystyle i<j\), melyre \(\displaystyle a+s_i,a+s_j\in \mathcal{N}_d\) valamelyik \(\displaystyle d\)-re. Figyeljük meg azonban, hogy \(\displaystyle \mathcal{N}_d\)-ben a nagyságbeli sorrendben szomszédos elemek különbsége végtelenhez tart, így alkalmas \(\displaystyle K_d\) küszöbre nincs két \(\displaystyle K_d\)-nél nagyobb, \(\displaystyle \le \max\mathcal{A}\) eltérésű eleme. Létezik így olyan \(\displaystyle K=\max K_d\) küszöb, melyre nincs a \(\displaystyle 2^m\) darab \(\displaystyle \mathcal{N}_d\) halmazunk egyikének sem két \(\displaystyle K\)-nál nagyobb, \(\displaystyle \le \max \mathcal{A}\) eltérésű eleme. Ekkor \(\displaystyle a>K\) esetén \(\displaystyle (\star)\) nem állhat fenn. Ez pedig ellentmond az indirekt feltevésünknek. \(\displaystyle \blacksquare\)

Így a dobozokban elhelyeztünk egy \(\displaystyle a_1,a_2,\dots\) végtelen sorozatot; skatulya-elv szerint valamely doboz alkalmas végtelen \(\displaystyle T\) halmazt szolgáltat.

Megjegyzés. 1. Ez a feladat kapcsolódik a Ramsey-féle problémakörhöz (érdeklődőknek: katt ide). A Ramsey-tétel és Van der Waerden-tétel bizonyítása is kapcsolódik módszerünkhöz olyan értelemben, hogy ügyesen megadott algoritmussal/indukciós feltevéssel igazolja bizonyos rendszerezett struktúra létezését.

2. Szeretnénk \(\displaystyle a_1\in E\)-t találni, melyhez végtelen sok \(\displaystyle a_2\in E\) létezik, melyre \(\displaystyle a_1+a_2\in E^c\). Tegyük fel indirekt, hogy ez nem lehet, vagyis minden \(\displaystyle a\in E\)-hez véges sok kivétellel minden \(\displaystyle b\in E\)-re \(\displaystyle a+b\in E\). Az A.708. feladat módszerével kapjuk, hogy egy ilyen tulajdonságú halmazra \(\displaystyle E=\{dx:x\in E_0\}\), ahol \(\displaystyle E_0\) olyan halmaz, mely véges sok kivétellel minden természetes számot tartalmazza. De jelen esetben \(\displaystyle E\) elemeinek legnagyobb közös osztója \(\displaystyle 1\), míg \(\displaystyle E^c\) végtelen, így a javasolt módszer bizonyítottan nem működhet.

3. Köszönet illeti Balka Richárdot a megoldással kapcsolatos értékes meglátásaiért.

Statisztika:

5 dolgozat érkezett.
5 pontot kapott:	Bukva Balázs, Gáspár Attila, Imolay András, Matolcsi Dávid, Schrettner Jakab.

A KöMaL 2018. márciusi matematika feladatai