Az A. 669. feladat (2016. április)

A. 669. Létezik-e a racionális számok halmazának olyan \(\displaystyle q_1,q_2,\ldots\) sorozatba rendezése, amelyhez nem léteznek olyan \(\displaystyle 1\le i_1<i_2<\ldots<i_6\) indexek, amelyekre a \(\displaystyle q_{i_1},q_{i_2},\ldots,q_{i_6}\) számok számtani sorozatot alkotnak?

Javasolta: Károlyi Gyula (Budajenő) és Komjáth Péter (Budapest)

(5 pont)

A beküldési határidő 2016. május 10-én LEJÁRT.

Megoldásvázlat. Megmutatjuk, hogy a racionális számok sorozatba rendezhetők úgy, hogy a sorozatnak ne legyen 6-tagú számtani részsorozata.

Lemma: Tetszőleges, racionális számokból álló \(\displaystyle H\) véges halmazt lehet úgy rendezni, hogy ne tartalmazzon háromtagú számtani részsorozatot.

Bizonyítás: Indukció \(\displaystyle H\) elemszáma szerint. \(\displaystyle |H|\le2\) esetén a lemma triviális. Tegyük tehát fel, hogy \(\displaystyle |H|\ge3\), és kisebb elemszám esetén a lemma igaz.

A \(\displaystyle H\) elemeire egy alkalmas, szigorúan növő, lineáris függvényt alkalmazva elérhetjük, hogy az elemek pozitív egészek legyenek; elég tehát a lemmát abban az esetben igazolni, ha \(\displaystyle H\) pozitív egészekből áll. Még azt is feltehetjük, hogy \(\displaystyle H\)-nak páros és páratlan eleme is van.

Legyen \(\displaystyle H_0\) és \(\displaystyle H_1\) a \(\displaystyle H\) páros, illetve páratlan elemeinek halmaza. Ezeket külön-külön rendezhetjük az indukciós feltevés szerint. A \(\displaystyle H\) rendezése legyen a következő: először felsoroljuk \(\displaystyle H_0\) elemeit a lemma szerinti rendezésben, majd \(\displaystyle H_1\) elemeit. Azt állítjuk, hogy ez egy megfelelő rendezés.

Tegyük fel indirekte, hogy \(\displaystyle (a,b,c)\) egy számtani részsorozata a megkonstruált rendezésnek. Az \(\displaystyle a\) és a \(\displaystyle c\) azonos paritású, tehát vagy mindkettő \(\displaystyle H_0\)-ban, vagy pedig mindkettő \(\displaystyle H_1\)-ben van. Ekkor viszont a rendezésben közöttük szereplő \(\displaystyle b\) is szintén a \(\displaystyle H_0\), illetve a \(\displaystyle H_1\) halmazban van, vagyis \(\displaystyle (a,b,c)\) részsorozata a \(\displaystyle H_0\), illetve a \(\displaystyle H_1\) halmaznak is, ez pedig ellentmond a \(\displaystyle H_0\) és \(\displaystyle H_1\) halmazok rendezésének. Ezzel a lemmát igazoltuk.

A feladat megoldása ezután a következő.

Legyen \(\displaystyle A_0=\emptyset\), és \(\displaystyle n=1,2,\ldots\) esetén legyen

\(\displaystyle A_n = \bigg\{ r=\frac{p}{q}: |r|\le 10^n, q\le 2^{2^n} \bigg\} \)

vagyis \(\displaystyle A_n\) azokból a \(\displaystyle [-10^n,10^n]\)-beli racionális számokból áll, amelyek nevezője legfeljebb \(\displaystyle 2^{2^n}\). Az világos, hogy ez egy növekvő halmazsorozat: \(\displaystyle A_0\subset A_1\subset A_2\subset\ldots\), és együttesen minden racionális számot tartalmaznak.

Azt állítjuk, hogy ha valamely \(\displaystyle A_n\) egy 6-tagú \(\displaystyle S=(a,b,c,d,e,f)\) számtani sorozatnak tartalmazza az első két tagját, azaz \(\displaystyle a,b\in A_n\), akkor a következő halmaz, \(\displaystyle A_{n+1}\) már a teljes \(\displaystyle S\)-et tartalmazza, azaz \(\displaystyle c,d,e,f\in A_{n+1}\). Ha \(\displaystyle a,b\in A_n\), akkor \(\displaystyle |a|,|b|\le 10^n\), így az \(\displaystyle S\) differenciája legfeljebb \(\displaystyle 2\cdot 10^n\), a többi elem abszolút értéke legfeljebb \(\displaystyle 10^n+4\cdot 2\cdot 10^n < 10^{n+1}\); ha \(\displaystyle a=\frac{p_1}{q_1}\) és \(\displaystyle b=\frac{p_2}{q_2}\), akkor \(\displaystyle S\) többi elemének nevezője legfeljebb \(\displaystyle q_1\cdot q_2 \le 2^{2^n}\cdot 2^{2^n}= 2^{2^{n+1}}\).

Most megadjuk a racionális számok egy olyan sorba rendezését, amely nem tartalmaz 6-tagú számtani részsorozatot.

Legyen \(\displaystyle A_0=\emptyset\). Rendezzük az \(\displaystyle A_1\setminus A_0\), \(\displaystyle A_2\setminus A_1\), \(\displaystyle A_3\setminus A_2\), \(\displaystyle A_4\setminus A_3\), ... véges halmazokat a lemma szerint. Először soroljuk fel \(\displaystyle A_1\) elemeit, utána az \(\displaystyle A_2\setminus A_1\), utána az \(\displaystyle A_3\setminus A_2\) elemeit, és így tovább:

Tegyük fel, hogy létezik egy olyan \(\displaystyle S=(a,b,c,d,e,f)\) 6-tagú számtani sorozat, amelynek tagjai ebben a sorrendben szerepelnek \(\displaystyle (*)\)-ban.

Legyen \(\displaystyle n\) az az index, amelyre \(\displaystyle b\in A_n\setminus A_{n-1}\). Ekkor \(\displaystyle a\in A_n\), mert \(\displaystyle a\) előbb van a rendezésben, mint \(\displaystyle b\). Mivel \(\displaystyle a,b\in A_n\), tudjuk, hogy \(\displaystyle c,d,e,f\in A_{n+1}\). továbbá, mivel a rendezésben \(\displaystyle b\not\in A_{n-1}\) és \(\displaystyle b\) megelőzi a \(\displaystyle c,d,e,f\) elemeket, \(\displaystyle c,d,e,f\not\in A_{n-1}\).

Ha \(\displaystyle d\in A_n\), akkor \(\displaystyle b,c,d\) mindegyike az \(\displaystyle A_n\setminus A_{n-1}\) halmazban van; ez viszont ellentmond az \(\displaystyle A_n\setminus A_{n-1}\) halmaz rendezésének.

Ha \(\displaystyle d\not\in A_n\), akkor \(\displaystyle d,e,f\) mindegyike az \(\displaystyle A_{n+1}\setminus A_n\) halmazban van; ez pedig ellentmond az \(\displaystyle A_{n+1}\setminus A_n\) halmaz rendezésének.

Mindkét esetben ellentondásra jutottunk; nincs tehát olyan 6-tagú számtani sorozat, amely az \(\displaystyle (*)\) szerint lenne rendezve.

Statisztika:

1 dolgozat érkezett.
2 pontot kapott:	1 versenyző.

A KöMaL 2016. áprilisi matematika feladatai