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