Kezdőlap


Feladat:	A.311	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Csóka Endre , Kunszenti-Kovács Dávid , Pach Péter Pál , Paulin Roland , Rácz Béla András
Füzet:	2004/március, 162 - 165. oldal		PDF \| MathML
Témakör(ök):	Algebrai egyenlőtlenségek, Egészrész, törtrész függvények, Nehéz feladat
Hivatkozás(ok):	Feladatok: 2003/február: A.311

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.

A feladatra két megoldást mutatunk; mindkét megoldás felhasználja az $[x] + [y] \leq [x + y]$ egyenlőtlenséget, amely tetszőleges $x$ , $y$ valós számok esetén teljesül.

I. megoldás. Bebizonyítjuk a következő ‐ a feladat állításánál általánosabb ‐ tételt:
Ha az

a_{1} \leq ... \leq a_{n}

valós számokra

a_{1} + 2 a_{2} + ... + n a_{n} = 0

és

x

tetszőleges valós szám, akkor

\begin{matrix} a_{1} [x] + a_{2} [2 x] + ... + a_{n} [n x] \geq 0. \end{matrix}

(2)

Abban az esetben, amikor

a_{1} = - 1

a_{2} = - \frac{1}{2}

...

a_{n - 1} = - \frac{1}{n - 1}

és

a_{n} = 1 - \frac{1}{n}

, a tétel éppen a feladat állítását adja.
A tételt teljes indukcióval igazoljuk. Az

n = 1

esetben a feltétel szerint

a_{1} = 0

, és az

a_{1} [x] \geq 0

egyenlőtlenség triviálisan teljesül. Tegyük most fel, hogy

n

valamely értékére az állítás igaz; ebből bebizonyítjuk az

1

-gyel nagyobb értékre is. Legyenek tehát

a_{1} \leq ... \leq a_{n + 1}

olyan valós számok, amelyekre

a_{1} + 2 a_{2} + ... + (n + 1) a_{n + 1} = 0

és

x

tetszőleges valós szám. Alakítsuk át (2) baloldalát a következőképpen:

\begin{matrix} \sum_{i = 1}^{n + 1} a_{i} [i x] = & \frac{a_{n + 1}}{n} \sum_{i = 1}^{n} ([(n + 1) x] - [i x] - [(n + 1 - i) x]) + & (3) \\ + \sum_{i = 1}^{n} (a_{i} + \frac{2 a_{n + 1}}{n}) [i x] . \end{matrix}

A feltételekből következik, hogy

a_{n + 1}

nemnegatív; ellenkező esetben ugyanis a rendezés miatt

a_{1}, ..., a_{n + 1}

mindegyike negatív lenne, de akkor

a_{1} + 2 a_{2} + ... + (n + 1) a_{n + 1}

nem lehetne

0

. Az

[a] + [b] \leq [a + b]

egyenlőtlenségből következik, hogy

[(n + 1) x] - [i x] - [(n + 1 - i) x] \geq 0

; az összeg első fele tehát nemnegatív. Az összeg második feléről az indukciós feltevés felhasználásával igazoljuk ugyanezt. Legyen tetszőleges

1 \leq i \leq n

esetén

b_{i} = a_{i} + \frac{2 a_{n + 1}}{n}

. Ezekre a számokra teljesül, hogy

b_{1} \leq ... \leq b_{n}

, és

\begin{matrix} \sum_{i = 1}^{n} i b_{i} = \sum_{i = 1}^{n} i (a_{i} + \frac{2 a_{n + 1}}{n}) = \sum_{i = 1}^{n} i a_{i} + \frac{2}{n} (1 + 2 + ... + n) a_{n + 1} = \sum_{i = 1}^{n + 1} i a_{i} = 0. \end{matrix}

Ezért, az indukciós feltevés alapján,

\begin{matrix} \sum_{i = 1}^{n} (a_{i} + \frac{2 a_{n + 1}}{n}) [i x] = \sum_{i = 1}^{n} b_{i} [i x] \geq 0. \end{matrix}

A (3) azonosság jobb oldalán tehát csupa nemnegatív számot adtunk össze, ezzel igazoltuk, hogy

\sum_{i = 1}^{n + 1} a_{i} [i x] \geq 0

II. megoldás. Az

[x] + [y] \leq [x + y]

egyenlőtlenség többszöri alkalmazásával kapjuk, hogy ha az

a_{1}, ..., a_{k}

pozitív egész számok összege

n

, akkor

\begin{matrix} [a_{1} x] + ... + [a_{k} x] \leq [n x] . \end{matrix}

(4)

Jelöljük

P_{n}

-nel az olyan véges hosszúságú, pozitív egészekből álló számsorozatok halmazát, amelyekben az elemek összege

n

. A sorozatok hosszára nincs megkötés,

P_{n}

tartalmazza az egyetlen elemből álló

(n)

sorozatot éppen úgy, mint az

n

elemből álló

(1,1, ...,1)

-et. Például

P_{3} = {(1,1,1), (1,2), (2,1), (3)}

.
A (4) egyenlőtlenséget

P_{n}

összes elemére felírhatjuk. A bizonyítandó (1)-et az így kapott egyenlőtlenségek lineáris kombinációjaként fogjuk előállítani.
Válasszuk ki

P_{n}

egy elemét a következőképpen: az első számot,

a_{1}

-et véletlenszerűen választjuk az

1, ..., n

számok közül; ezután a második számot,

a_{2}

-t véletlenszerűen választjuk az

1,2, ..., n - a_{1}

számok közül és így tovább egészen addig, amíg el nem érjük az

n

összeget. Más szóval, az

(a_{1}, ..., a_{k})

sorozat kiválasztásának valószínűsége

\begin{matrix} \begin{matrix} p (a_{1}, ..., a_{k}) & = \frac{1}{n \cdot (n - a_{1}) \cdot (n - a_{1} - a_{2}) \cdot ... \cdot (n - a_{1} - ... - a_{k - 1})} = \\ = \frac{1}{(a_{1} + ... + a_{k}) \cdot (a_{2} + ... + a_{n}) \cdot ... \cdot (a_{k - 1} + a_{k}) \cdot a_{k}} . \end{matrix} \end{matrix}

Az összes sorozat valószínűségének összege természetesen

1

. Minden egyes sorozatra szorozzuk meg a (4) egyenlőtlenséget

p (a_{1}, ..., a_{k})

-val és az így kapott egyenlőtlenségeket adjuk össze. Azt állítjuk, hogy eredményül éppen a bizonyítandó (1)-et kapjuk.
Az egyenlőtlenségek összegének jobboldalán éppen

[n x]

áll, mert a valószínűségek összege

1

. Azt, hogy a baloldalon

\sum_{j = 1}^{n} \frac{[j x]}{j}

áll, teljes indukcióval igazoljuk. Az

n = 1

esetben ez az állítás triviális, mert csupán egyetlen

1

-esből álló sorozat létezik és ezt

1

valószínűséggel választjuk ki. Legyen tehát

n > 1

és tegyük fel, hogy kisebb értékekre az állításunk igaz. Csoportosítsuk

P_{n}

elemeit az első elem szerint szerint, különválasztva az egyetlen

n

-esből álló sorozatot, majd alkalmazzuk az indukciós feltevést:

\begin{matrix} \sum_{(a_{1}, ..., a_{k}) \in P_{n}} p (a_{1}, ..., a_{k}) ([a_{1} x] + ... + [a_{k} x]) = \\ = & \sum_{a_{1} = 1}^{n - 1} \sum_{(a_{2}, ..., a_{k}) \in P_{n - a_{1}}} \frac{[a_{1} x] + ([a_{2} x] + ... + [a_{k} x])}{({\underset{︸}{a_{1} + ... + a_{k}}}_{n}^{}) \cdot (a_{2} + ... + a_{k}) \cdot ... \cdot a_{k}} + \frac{[n x]}{n} = \\ = & \sum_{a_{1} = 1}^{n - 1} \frac{[a_{1} x]}{n} \sum_{(a_{2}, ..., a_{k}) \in P_{n - a_{1}}} \frac{1}{(a_{2} + ... + a_{k}) \cdot ... \cdot a_{k}} + \\ + \frac{1}{n} \sum_{a_{1} = 1}^{n - 1} \sum_{(a_{2}, ..., a_{k}) \in P_{n - a_{1}}} \frac{[a_{2} x] + ... + [a_{k} x]}{(a_{2} + ... + a_{k}) \cdot ... \cdot a_{k}} + \frac{[n x]}{n} = \\ = & \sum_{a_{1} = 1}^{n - 1} \frac{[a_{1} x]}{n} \cdot 1 + \frac{1}{n} \sum_{a_{1} = 1}^{n - 1} \sum_{j = 1}^{n - a_{1}} \frac{[j x]}{j} + \frac{[n x]}{n} = \sum_{j = 1}^{n - 1} \frac{[j x]}{n} + \frac{1}{n} \sum_{j = 1}^{n - 1} \sum_{a_{1} = 1}^{n - j} \frac{[j x]}{j} + \frac{[n x]}{n} = \\ = & \sum_{j = 1}^{n - 1} (\frac{1}{n} + \frac{n - j}{n j}) [j x] + \frac{[n x]}{n} = \sum_{j = 1}^{n} \frac{[j x]}{j} . \end{matrix}

Ezzel az állítást igazoltuk.