Kezdőlap


Feladat:	F.2782	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Balogh József , Benczúr Péter , Erben Péter , Harcos Gergely , Heszberger Zalán , Imreh Csanád , Király Róbert , Kiss István , Magó Kálmán , Miklós György , Nagy Benedek , Pócs Miklós , Podoski Károly
Füzet:	1991/március, 97 - 99. oldal		PDF \| MathML
Témakör(ök):	Diofantikus egyenletek, Paraméteres egyenlőtlenségek, Egészrész, törtrész függvények, Kettes alapú számrendszer, Feladat
Hivatkozás(ok):	Feladatok: 1990/február: F.2782

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.

Megoldás. Minden valós szám legalább akkora, mint az egészrésze; így, ha $x$ megoldása az egyenletnek, akkor

\begin{matrix} x \leq 1 + \sum_{k = 1}^{n} \frac{x}{2^{k}} = 1 + \frac{x}{2} \cdot \frac{2^{n} - 1}{2^{n} - n} = x + 1 - \frac{x}{2^{n}}, \end{matrix}

azaz

x \leq 2^{n}

. A

2^{n}

nyilván megoldása az egyenletnek, ezért a továbbiakban csak azzal az esettel foglalkozunk, amikor

x < 2^{n}

. Az

x

szükségképpen egész, hiszen az egyenlet jobb oldala egész számok összege. Tegyük fel először, hogy

x \geq 0

, és írjuk fel

x

-et a kettes számrendszerben:

\begin{matrix} x = \sum_{i = 0}^{n - 1} a_{i} 2^{i} (a_{i} = 0 vagy 1) . \end{matrix}

A feladat feltétele szerint

\begin{matrix} \sum_{i = 0}^{n - 1} a_{i} 2^{i} = x = 1 + \sum_{k = 1}^{n - 1} [\frac{x}{2^{k}}] = 1 + \sum_{k = 1}^{n - 1} \sum_{i = k}^{n - 1} a_{i} 2^{i - k} . \end{matrix}

Az összegzések sorrendjét felcserélve:

\begin{matrix} x = 1 + \sum_{i = 1}^{n - 1} a_{i} \sum_{}^{i}_{k = 1} 2^{i - k} = 1 + \sum_{i = k}^{n - 1} a_{i} (2^{i} - 1) = x + 1 - \sum_{i = 0}^{n - 1} a_{i}, \end{matrix}

azaz

x

pontosan akkor megoldás, ha

Σ_{i = 0}^{n - 1} a_{i} = 1

, vagyis

x

2

hatványa. Az egyenlet nemnegatív megoldásai ennek alapján:

1, 2, 4, ..., 2^{n - 1}, 2^{n}

.
A negatív megoldásokat is a kettes számrendszerbeli alakjukban keressük: legyen

\begin{matrix} x = - 2^{t} (1 + \sum_{i = 1}^{m} b_{i} 2^{i}) = - 2^{t} \cdot y, \end{matrix}

ahol feltehető, hogy

m \geq n

(azaz

b_{m}

lehet

0

is). Ha

n \leq t

, akkor az

x

-re fennálló egyenlet a következő:

\begin{matrix} x = 1 + \sum_{k = 1}^{n} \frac{x}{2^{k}} = 1 + x - \frac{x}{2^{n}}, \end{matrix}

ahonnan

x = 2^{n}

, és ez nem negatív. Így

n > t

, és ezzel a feladatbeli egyenlet jobb oldala:

\begin{matrix} 1 + \sum_{k = 1}^{t} \frac{x}{2^{k}} + \sum_{v = 1}^{n - t} [- \frac{y}{2^{v}}] = x + 1 - \frac{x}{2^{t}} + \sum_{v = 1}^{n - t} - 1 - \sum_{i = v}^{m} b_{i} 2^{i - v} = \\ = x + 1 + y + t - n - \sum_{i = 1}^{m} b_{i} \sum_{v = 1}^{m i n {i, n - t}} 2^{i - v} = \\ = x + 1 + y + t - n - \sum_{i = 1}^{n - t - 1} b_{i} \sum_{v = 1}^{i} 2^{i - v} - \sum_{j = n - t}^{m} b_{j} \sum_{v = 1}^{n - t} 2^{j - v} = \\ = x + 1 + y + t - n - \sum_{i = 1}^{n - t - 1} b_{i} (2^{i} - 1) - \sum_{j = n - t}^{m} b_{j} (2^{i} - 2^{j - n + t}) = \\ = x + 2 + t - n + \sum_{i = 1}^{n - t - 1} b_{i} + [\frac{y}{2^{n - t}}], \end{matrix}

ezért

\begin{matrix} [\frac{y}{2^{n - t}}] = n - t - 2 - \sum_{i = 1}^{n - t - 1} b_{i} . \end{matrix}

Mivel

y

pozitív, a megoldás pontosan akkor létezik, ha

\begin{matrix} n - t - 2 \geq \sum_{i = 1}^{n - t - 1} b_{i}, \end{matrix}

vagyis ha a

b_{1}, b_{2}, ..., b_{n - t - 1}

számjegyek között legalább egy nulla van és

t \leq n - 2

. Ekkor pedig

\begin{matrix} y = 2^{n - t} (n - t - 2 - \sum_{i = 1}^{n - t - 1} b_{i}) + (1 + \sum_{i = 1}^{n - t - 1} b_{i} 2^{i}), \end{matrix}

tehát a negatív megoldások

\begin{matrix} x = - 2^{n} (n - t - 2 - \sum_{i = 1}^{n - t - 1} b_{i}) - 2^{t} (1 + \sum_{i = 1}^{n - t - 1} b_{i} 2^{i}), \end{matrix}

ahol

0 \leq t \leq n - 2 (t

egész), és a

b_{1}, b_{2}, ..., b_{n - t - 1}

számok közül tetszés szerint néhány (de legalább egy)

0

, a többi

1

Megjegyzés. Szembetűnő a pozitív és a negatív megoldások erősen eltérő alakja, amelyet főleg az a tény indokol, hogy az egészrész-függvény nem páratlan. Míg a pozitív megoldások könnyen áttekinthetők, a negatív egészekről már nem dönthető el ,,ránézéssel'', hogy megoldásai-e a feladatbeli egyenletnek. Például a

- 17

nem megoldás ‐ semmilyen

n

mellett sem ‐ jóllehet a kettes számrendszerbeli alakjában

(- 10001)

van

0

jegy. A

- 7

viszont

n = 4

-re megoldás, bár a kettes számrendszerben felírva csupa

1

-esből áll. További különbség az is, hogy

2^{k}

minden

k

-nál nem kisebb

n

-re megoldás, egy negatív szám viszont legfeljebb egy

n

érték mellett lehet megoldás, hiszen ekkor az

S_{n} = 1 + Σ_{k = 1}^{n} [x / 2^{k}]

összegek sorozata (

n

növekedtével) szigorúan monoton fogyó.