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