Kezdőlap


Feladat:	1991. évi Nemzetközi Matematika Diákolimpia 23. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Harcos Gergely
Füzet:	1991/november, 341 - 343. oldal		PDF \| MathML
Témakör(ök):	Számsorozatok, Kettes alapú számrendszer, Irracionális számok és tulajdonságaik, Konstruktív megoldási módszer, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1991/szeptember: 1991. évi Nemzetközi Matematika Diákolimpia 23. feladata

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.

I. megoldás. Tetszőleges $k \in N$ esetén, ha $k$ diadikus alakja

\begin{matrix} k = \bar{a_{n} a_{n - 1} ... a_{0}}_{◯ 2} = \sum_{s = 0}^{n} a_{s} \cdot 2^{s} (a_{i} = 0 vagy 1; i = 0, ..., n), \end{matrix}

akkor legyen

\begin{matrix} y_{k} = \sum_{s = 0}^{n} a_{s} \cdot 2^{- a s}, \end{matrix}

ahol

a > 1

a feladatban rögzített valós szám. Legyen most

i, j \in N, i \neq j

, továbbá

i

és

j

kettes számrendszerbeli alakja

\begin{matrix} i = \bar{b_{n} b_{n - 1} ... b_{0}}_{◯ 2} és j = \bar{c_{m} c_{m - 1} ... c_{0}}_{◯ 2} . \end{matrix}

Feltehető, hogy

i > j

, és ekkor

n \geq m

. Tegyük fel továbbá, hogy

r

az a természetes szám, amelyre

i

és

j

diadikus alakja az utolsó

r

db jegyben megegyezik, de

(r + 1)

-edik jegyében ‐ hátulról olvasva ‐ már különbözik:

\begin{matrix} r = {min}_{}^{} {s | b_{s} \neq c_{s}, 1 \leq s \leq n}, \end{matrix}

(m < s \leq n

esetén legyen

c_{s} = 0)

. Ekkor

\begin{matrix} | i - j | = i - j \geq 2^{r}, \end{matrix}

(1)

és

a > 1

miatt

\begin{matrix} | y_{i} - y_{j} | & = | \sum_{s = 0}^{n} b_{s} \cdot 2^{- a s} - \sum_{s = 0}^{m} c_{s} \cdot 2^{- a s} | = | \sum_{s = r}^{n} b_{s} \cdot 2^{- a s} - \sum_{s = r}^{n} c_{s} \cdot 2^{- a s} | \geq \\ \geq 2^{- a r} - 2^{- a (r + 1)} - 2^{- a (r + 2)} - ... - 2^{- a n} > 2^{- a r} (1 - \sum_{s = 1}^{\infty} 2^{- a s}) = \\ = 2^{- a r} (1 - 2^{- a} \frac{1}{1 - 2^{- a}}) = 2^{- a r} (1 - \frac{1}{2^{a} - 1}) = 2^{- a r} \cdot \frac{2^{a} - 2}{2^{a} - 1} . \end{matrix}

Ezt

(1)

-gyel egybevetve:

\begin{matrix} | y_{i} - y_{j} | \cdot | i - j |^{a} > 2^{- a r} \cdot \frac{2^{a} - 2}{2^{a} - 1} \cdot {(2^{r})}^{a} = \frac{2^{a} - 2}{2^{a} - 1}, \end{matrix}

ami azt jelenti, hogy az

\begin{matrix} x_{k} = \frac{2^{a} - 1}{2^{a} - 2} y_{k} (k = 0,1, ...) \end{matrix}

sorozat

i, j \in N; i \neq j

esetén

\begin{matrix} | x_{i} - x_{j} | \cdot | i - j |^{a} > 1, \end{matrix}

továbbá

(y_{k})

korlátos volta miatt

(x_{k})

is korlátos:

\begin{matrix} 0 \leq x_{k} = \frac{2^{a} - 1}{2^{a} - 2} y_{k} < \frac{2^{a} - 1}{2^{a} - 2} \cdot \sum_{s = 0}^{\infty} 2^{- a s} = \frac{2^{a}}{2^{a} - 2} . \end{matrix}

Ezzel a feladatot megoldottuk.

II. megoldás. Konstrukciót adunk az

a = 1

esetre ‐ ez nyilván megfelelő

a > 1

esetére is.
Alapötletünk a következő: Tegyük fel, hogy

γ

olyan (irracionális) szám, amelynek minden

\frac{p}{q} (p, q \in Z; q > 0)

közelítő törtjére az eltérés

\begin{matrix} | γ - \frac{p}{q} | \geq \frac{1}{α q^{2}}, \end{matrix}

(2)

ahol

α > 0

valamilyen rögzített konstans. Ekkor tekintjük az

\begin{matrix} x_{k} = α \cdot {γ k} (k = 0,1, ...) \end{matrix}

sorozatot, ahol

{t} = t - [t]

t

szám törtrészét jelöli. Világos, hogy

(x_{k})

korlátos:

\begin{matrix} 0 < x_{k} < α, \end{matrix}

továbbá

i, j \in N; i \neq j

esetén (

i > j

feltehető)

\begin{matrix} | x_{i} - x_{j} | \cdot | i - j | = α \cdot | {γ i} - {γ j} | \cdot | i - j | = \end{matrix}

\begin{matrix}  \end{matrix}

=α⋅|(γi-γj)-([γi]-[γj])|⋅|i-j|,

ill. a

q = i - j (> 0), p = [γ i] - [γ j]

jelöléssel

p

és

q

egészek, tehát (2) szerint

\begin{matrix} | x_{i} - x_{j} | \cdot | i - j | = α \cdot | q γ - p | \cdot q = α q^{2} \cdot | γ - \frac{p}{q} | \geq 1, \end{matrix}

vagyis az

(x_{k})

sorozat megfelelő.
Az is látszik, hogy az

\begin{matrix} x'_{k} = x_{k} - \frac{α}{2} (k = 0,1, ...) sorozatra | x'_{k} | < \frac{α}{2}, továbbá \end{matrix}

\begin{matrix}  \end{matrix}

|x'i-x'j|⋅|i-j|=|xi-xj|⋅|i-j|≥1,

tehát az

x'_{k}

sorozat is megfelelő.
Ezek szerint csak a

(2)

-t kielégítő

γ

-t és

α

-t kell találnunk, sőt minél kisebb az

α

, annál jobb a sorozatunk korlátja.

(2)

-re talán

γ = \sqrt[]{2}

és

α = 3

adja a legegyszerűbb példát:

\begin{matrix} | \sqrt[]{2} - \frac{p}{q} | > \frac{1}{3 q^{2}} \end{matrix}

(3)

mindig fennáll. Ha ugyanis lenne olyan

\frac{p}{q}

közelítő tört, amelyre

\begin{matrix} | \sqrt[]{2} - \frac{p}{q} | \leq \frac{1}{3 q^{2}}, \end{matrix}

(4)

akkor

\begin{matrix} \sqrt[]{2} q - \frac{1}{3 q} \leq p \leq \sqrt[]{2} q + \frac{1}{3 q}, \end{matrix}

azaz négyzetre emelés és rendezés után

\begin{matrix} - \frac{2 \sqrt[]{2}}{3} + {(\frac{1}{3 q})}^{2} \leq p^{2} - 2 q^{2} \leq \frac{2 \sqrt[]{2}}{3} + {(\frac{1}{3 q})}^{2} \end{matrix}

lenne, amiből

\begin{matrix} | p^{2} - 2 q^{2} | \leq \frac{2 \sqrt[]{2}}{3} + {(\frac{1}{3 q})}^{2} \end{matrix}

következnék.

(4)

nyilván nem állhat fenn

q = 1

esetén, ezért

q \geq 2

, tehát

\begin{matrix} | p^{2} - 2 q^{2} | \leq \frac{2 \sqrt[]{2}}{3} + {(\frac{1}{3 \cdot 2})}^{2} = \frac{2 \sqrt[]{2} + \frac{1}{12}}{3} < 1. \end{matrix}

vagyis

\begin{matrix} p^{2} - 2 q^{2} = 0, \end{matrix}

hiszen

| p^{2} - 2 q^{2} |

nemnegatív egész.
Mivel

\sqrt[]{2}

irracionális, ezért

p^{2} - 2 q^{2} = 0

ellentmondást jelent, ami

(3)

-at igazolja.
Ezzel sikerült megadnunk olyan

(x_{k})

sorozatot, amelyre

\begin{matrix} | x_{k} | < \frac{3}{2}, és | x_{i} - x_{j} | \cdot | i - j | \geq 1 \end{matrix}

teljesül, ha

i, j \in N; i \neq j