Kezdőlap


Feladat:	N.178	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bérczi Gergely , Lukács László , Végh A. László
Füzet:	1999/március, 164. oldal		PDF \| MathML
Témakör(ök):	Abszolútértékes egyenlőtlenségek, Számhalmazok, Teljes indukció módszere, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1998/május: N.178

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Jelölje $a_{0} < ... < a_{n - 1}$ az első $n$ darab olyan nemnegatív egészet, amelynek a hármas számrendszerbeli alakja csupa 0-s és 1-es számjegyekből áll. Ezekre fogjuk belátni, hogy teljesítik a feladat követelményeit.
Bebizonyítjuk, hogy e számok között nincs 3 különböző tagból álló számtani sorozat. Tegyük fel indirekte, hogy $2 a_{i} = a_{j} + a_{k}$ . Az $a_{j} + a_{k}$ kiszámításánál a műveleteket helyiértékenként végezhetjük el, hiszen nincs ,,átvitel''. Az eredmény minden helyiértéknél 0 vagy 2 lesz, $2 a_{i}$ jegyei ilyenek. De ez azt jelenti, hogy $a_{j}$ -ben egy helyiértéken 1-es akkor és csak akkor állhat, ha $a_{k}$ ugyanazon helyiértékén is 1-es áll. Ekkor $a_{j} = a_{k} = a_{i}$ , ami ellentmondás.
Tegyük fel, hogy $| a_{i} - a_{j} | > | a_{i} - a_{k} |$ ( $i \neq j \neq k \neq i)$ , azaz $| a_{i} - a_{j} | \geq | a_{i} - a_{k} | + 1$ . Ekkor

\begin{matrix} \frac{| a_{i} - a_{j} |}{| a_{i} - a_{k} |} \geq 1 + \frac{1}{| a_{i} - a_{k} |}, \end{matrix}

így elég lenne azt igazolni, hogy

| a_{i} - a_{k} | < n^{1,6}

; sőt, ehhez már az is elég, ha

a_{n - 1} \leq {(n - 1)}^{1,6}

teljesül, ugyanis

| a_{i} - a_{k} | \leq a_{n - 1}

.
Vegyük észre, hogy

a_{n - 1}

megkapható úgy, hogy

(n - 1)

-et felírjuk 2-es számrendszerben, és ezt 3-as számrendszerben olvassuk ki. Ebből adódik, hogy

a_{2^{m}} = 3^{m}

, és ha

0 \leq t < 2^{m}

, akkor

a_{2^{m} + t} = 3^{m} + a_{t}

.
Ezután

a_{n - 1} \leq {(n - 1)}^{1,6}

egyenlőtlenséget teljes indukcióval bizonyítjuk.
Ha

n = 1

vagy 2, akkor az állítás igaz. Tegyük fel, hogy igaz minden, az

n

-nél kisebb egészre; ekkor legyen

n - 1 = 2^{m} + t

, ahol

0 \leq t < 2^{m}

. Az indukciós feltevés szerint

a_{t} \leq t^{1,6}

; felhasználva, hogy

2^{1,6} > 3

és

0 < x < 1

esetén

1,6 x > x^{1,6}

\begin{matrix} \begin{matrix} {(n - 1)}^{1,6} = {(2^{m} + t)}^{1,6} = 2^{1,6 m} {(1 + \frac{t}{2^{m}})}^{1,6} > 2^{1,6 m} (1 + 1,6 \cdot \frac{t}{2^{m}}) > \\ > 2^{1,6 m} \cdot (1 + {(\frac{t}{2^{m}})}^{1,6}) = 2^{1,6 m} + t^{1,6} > 3^{m} + a_{t} = a_{2^{m} + t} = a_{n - 1} . \end{matrix} \end{matrix}

Több megoldás alapján