Kezdőlap


Cím:	Az Abel-féle átrendezésről
Szerző(k):	Pataki János
Füzet:	1990/április, 145 - 153. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Bevezetés

Különböző problémákban gyakran találkozhatunk

\begin{matrix} a_{1} b_{1} + a_{2} b_{2} + ... + a_{n} b_{n} \end{matrix}

alakú összegekkel, illetve végtelen sor, vagy integrál alakú általánosításukkal. Az ilyen összegek átalakítása vagy becslése fontos feladat: ennek egy hasznos eszközét, az Abel-féle átrendezést és az ennek következményeként adódó egyenlőtlenséget szeretném bemutatni. Egy példától eltekintve nem térek ki a nagyon fontos analízisbeli alkalmazásokra, és hely hiányában nem írok az Abel átrendezésnek, mint skalárszorzattartó transzformációnak lineáris algebrai megközelítéséről sem.
A módszer akkor használható, ha az összeg " tényezősorozatairól'', az

a_{i}

és

b_{i}

sorozatokról rendelkezünk bizonyos információkkal ‐ ismerjük, vagy legalábbis becsülni tudjuk például egyikük részletösszegeit.
A cikk során használni fogom a

\sum

jelölést, illetve a binomális együtthatókat. Alapvető tulajdonságaik kitűnő összefoglalása található például Donald E. Knuth: A számítógépprogramozás művészete című kiváló könyvének első kötetében.

I. Két azonosság

Kezdjük a

\sum

jelölés egyik leghasznosabb tulajdonságával, amelyet az összegzés fölcserélhetőségének nevezünk. Ez az azonosság bizonyos típusú kéttényezős szorzatok összegének az egyes tényezőkből készíthető részletösszegekkel való kapcsolatát fejezi ki.
Legyenek

a_{i}

és

b_{i}

valós számok,

i = 1,2, ..., n

, és készítsük el az

a_{i} b_{j}

alakú szorzatok

S

összegét, ahol

1 \leq j \leq i \leq n

. Az összeg szerkezete az ábrán látható:

S

az ábrán "

x

''-szel megjelölt ‐ az átlóbeli és az alatta levő ‐ mezők sorának és oszlopának szélén álló számok szorzatának összege.
Ekkor

\begin{matrix} \sum_{i = 1}^{n} a_{i} \sum_{j = 1}^{i} b_{j} = \sum_{j = 1}^{n} b_{j} \sum_{i = j}^{n} a_{i}, \end{matrix}

(1)

azaz az összegzések sorrendje felcserélhető, miközben változnak a belső összegzés határai.

\begin{matrix} b_{1}b_{2}b_{3}...b_{n} \\ a_{1} & × & ... \\ a_{2} & × & × & ... \\ a_{3} & × & × & × & ... \\ × & × & × & × \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \\ × & × & × & × \\ a_{n} & × & × & × & ×...× & × \end{matrix}

Az (1) azonosság ‐ meglehetősen nyilvánvaló ‐ bizonyítása leolvasható az ábráról: a bal oldalon soronként, a jobb oldalon pedig oszloponként haladva adjuk össze az

S

összeg tagjait. Az (1) azonosság egyszerűsége ellenére rendkívül hasznos.

Feladat. Jelölje

Q (n)

n

-nél nem nagyobb számok négyzetösszegét. Írjuk fel zárt alakban a

\begin{matrix} \sum_{i = 1}^{n} Q (i), illetve a \sum_{i = 1}^{n} i Q (i) \end{matrix}

összegeket.

Az (1) azonosság most már lehetővé teszi, hogy a

\begin{matrix} P = \sum_{i = 1}^{n} x_{i} y_{i} \end{matrix}

összegben áttérhessünk az egyik rész ‐ mondjuk az

y_{i}

sorozat ‐ részletösszegeire. Írjuk ehhez

x_{j}

-t összeg alakban:

\begin{matrix} x_{j} = (x_{j} - x_{j + 1}) + (x_{j + 1} - x_{j + 2}) + ... + (x_{n - 1} - x_{n}) + x_{n} . \end{matrix}

Ha bevezetjük az

x_{n + 1} = 0

jelölést, akkor az utolsó "csonka'' tag is különbség alakú,

(x_{n} - x_{n + 1})

, maga a

P

összeg pedig így a

\begin{matrix} P = \sum_{j = 1}^{n} y_{j} \sum_{i = j}^{n} (x_{i} - x_{i + 1}) \end{matrix}

alakba írható. Az (1) azonosság szerint felcserélve az összegzés sorrendjét:

\begin{matrix} \sum_{i = 1}^{n} x_{i} y_{i} = \sum_{i = 1}^{n} (x_{i} - x_{i + 1}) \sum_{j = 1}^{i} y_{j} . \end{matrix}

(2)

A most talált (2) alakot nevezzük a

P

összeg Abel-féle átrendezésének.
(Niels Henrik Abel (1802‐1829) egy norvégiai kisvárosban született egy hétgyermekes szegény lelkipásztor fiaként. Tizennyolc éves korában apja meghalt, ettől kezdve ő tartotta el a családot. Egy évvel később oldotta meg azt a problémát, amely 300 évig állt ellen a legkiválóbb matematikusoknak: bebizonyította, hogy az általános ötödfokú egyenlet nem oldható meg a négy alapművelet és a gyökvonás segítségével.
Rövid életében a matematika más területein is maradandót alkotott, azonban életében igen kevéssé ismerték el munkásságát. Cauchy például egyszerűen elveszítette Abelnek egy hozzá küldött tanulmányát, ami csak a szerző halála után került elő, és 1841-ben publikálták. Abel sikertelenül próbált egyetemi álláshoz jutni, két nappal azután nevezték ki a berlini egyetemre, hogy tüdőbajban meghalt Norvégiában. Munkássága és eredményei az élő matematika szerves és eleven részét alkotják.)

Feladatok 1. Bizonyítsuk be a (2) azonosság szimmetrikus párját, amelyben az

y_{i}

sorozat kezdőszeletei helyett a " zárószeletek'' jelennek meg.

\begin{matrix} \sum_{i = 1}^{n} x_{i} y_{i} = \sum_{i = 1}^{n} (x_{i} - x_{i - 1}) \sum_{j = i}^{n} y_{j} (x_{0} = 0) . \end{matrix}

'

)

2. Legyen az

(a_{n}) d

differenciájú számtani, a

(b_{n})

pedig

q

hányadosú mértani sorozat. Írjuk fel az

\begin{matrix} a_{1} b_{1} + a_{2} b_{2} + ... + a_{n} b_{n} \end{matrix}

összeget zárt alakban

a_{1}

b_{1}

d

q

és

n

segítségével.

3. Bizonyítsuk be ‐ teljes indukció használata nélkül ‐ , hogy az első

n

darab négyzetszám

Q (n)

összege

\begin{matrix} Q (n) = n (\binom{n + 1}{2}) - (\binom{n + 1}{3}) . \end{matrix}

II. Ismerkedés az azonossággal

Az első látásra bizony elég mesterkéltnek tűnő (2), (

2'

) átrendezések meglepően magától értetődő alakot öltenek, ha a

P

összeget annak egy végtelen változatával, az integrállal helyettesítjük, tehát a

\begin{matrix} P^{*} = \int_{a}^{b} f (x) g (x) d x \end{matrix}

integrált akarjuk kiszámolni. Az egyik tényező ‐

g (x)

‐ "részletösszegei'' az

\int_{a}^{x} g (t) d t

alakú integrálok, ezek ismerete most azt jelenti, hogy ismerjük a

g

egy

G

integrálfüggvényét.
Ha az

\begin{matrix} I = \sum_{i = 1}^{n} f (x_{i}) g (x_{i}) Δ_{i} (x_{1} = a, x_{n} = b) \end{matrix}

integrálközelítő összegre alkalmazzuk az Abel-féle átrendezést, akkor

\begin{matrix} I = \sum_{i = 1}^{n} [f (x_{i}) - f (x_{i + 1})] \sum_{j = 1}^{i} g (x_{j}) Δ_{j} \end{matrix}

adódik. A részletösszegek a

G (x_{i}) = \int_{a}^{x_{i}} g (t) d t

integrált közelítik, az

f (x_{i}) - f (x_{i + 1})

a differenciák pedig differenciálható

f

esetén a Lagrange-középértéktétel szerint

f' (y_{i}) (x_{i} - x_{i + 1})

alakúak, ahol

x_{i} < y_{i} < x_{i + 1}

. Így az

\begin{matrix} I^{*} = - \sum_{i = 1}^{n - 1} f' (y_{i}) (x_{i + 1} - x_{i}) G (x_{i}) + f (x_{n}) G (x_{n}) \end{matrix}

összeg ugyancsak a

P^{*}

integrált közelíti. Az összeg első tagja másfelől

- \int_{a}^{b} f' (x) G (x) d x

integrálközelítő összege, és ezzel előttünk áll a parciális integrálás jól ismert formulája:

\begin{matrix} \int_{a}^{b} f (x) G' (x) d x = {[f (x) G (x)]}_{a}^{b} - \int_{a}^{b} f' (x) G (x) d x . \end{matrix}

(f (x_{n}) \cdot G (x_{n}) = f (b) \cdot G (b)

és a most használt

G

integrálfüggvényre

G (a) = 0)

.
A parciális integrálás mögött tehát a kezelhető részletösszegekre való áttérést lehetővé tevő Abel-féle átrendezés is felfedezhető.

A következőkben egy érdekes polinomazonosságot bizonyítunk az Abel-féle átrendezés segítségével. Ezt felhasználva távolról sem magától értetődő összefüggésekhez jutunk binomiális együtthatók között.
Legyen

k \geq 0

egész szám. Ekkor tetszőleges pozitív egész

n

-re

\begin{matrix} \sum_{i = 0}^{k} (\binom{n - i}{k - i}) {(1 + x)}^{i} = \sum_{i = 0}^{k} (\binom{n + 1}{k - i}) x^{i} . \end{matrix}

(3)

Megjegyzés. A (3) azonosságban szereplő

(\binom{a}{b})

binomiális együtthatók értéke a szokásos értelmezés szerint nulla, ha

b < 0

, vagy

a < b

, ezenkívül

(\binom{0}{0}) = 0^{0} = 1

. Jelölje a bal oldalon álló polinomot

f_{k} (x)

. Ekkor

f_{0} (x) = 1

. A

k

-ra vonatkozó teljes indukcióval megmutatjuk, hogy

f_{k} (x) = (\binom{n + 1}{k}) + x \cdot f_{k - 1} (x)

, és innen az állítás már következik.
A bal oldalon a (2) Abel-átrendezésből

\begin{matrix} f_{k} (x) = \sum_{i = 0}^{k} [{(1 + x)}^{i} - {(1 + x)}^{i + 1}] \sum_{j = 0}^{k} (\binom{n - j}{k - j}) . \end{matrix}

'

)

(

Itt most

{(1 + x)}^{k + 1}

helyére 0-t kell írni!

)

Felhasználva a jól ismert

(\binom{a + 1}{b}) = (\binom{a}{b}) + (\binom{a - 1}{b - 1}) + ... (\binom{a - b}{0})

azonosságot, (3

'

) jobb oldalán a részletösszegek zárt alakja:

\begin{matrix} \sum_{j = 0}^{k} (\binom{n - j}{k - j}) = (\binom{n + 1}{k}) - (\binom{n - i}{k - i - 1}) . \end{matrix}

Innen

\begin{matrix} f_{k} (x) = (\binom{n + 1}{k}) {\underset{︸}{\sum_{i = 0}^{k} [{(1 + x)}^{i} - {(1 + x)}^{i + 1}]}}_{1}^{} - \sum (\binom{n - i}{k - i - 1}) [{(1 + x)}^{i} - {(1 + x)}^{i + 1}] = \\ = (\binom{n + 1}{k}) + \sum_{i = 0}^{k - 1} (\binom{n - i}{k - i - 1}) x \cdot {(1 + x)}^{i} = (\binom{n + 1}{k}) + x \cdot f_{k - 1} (x), \end{matrix}

és ezt akartuk bizonyítani.

Feladatok 1. Bizonyítsuk be, hogy

\sum_{i = 0}^{k} (\binom{n - i}{k - i}) 2^{i} = \sum_{i = 0}^{k} (\binom{n + 1}{i})

(Ez volt a KÖMAL F. 2526. feladata; 1986. 8‐9 szám).

{(- 1)}^{k} (\binom{n}{k}) = \sum_{i = 0}^{k} {(- 1)}^{i} (\binom{n + 1}{i})

\sum_{i = 0}^{A} (\binom{i}{B}) (\binom{A - i}{C}) = (\binom{A + 1}{B + C + 1})

\sum_{i = 0}^{A} {(- 1)}^{i} (\binom{i}{B}) (\binom{C}{A - i}) = {(- 1)}^{B} (\binom{C - B - 1}{A - B})

(

A \geq B

C > B

III. Az Abel-féle egyenlőtlenség

Gyakran nem ismerjük pontosan a

P = \sum_{i = 1}^{n} x_{i} y_{i}

összeg részletösszegeit, de egy hasonló sorozat elemeivel össze tudjuk ezeket hasonlítani. Ilyenkor használható az alábbi Abel-féle egyenlőtlenség:
Ha

x_{1} \geq x_{2} \geq ... \geq x_{n} \geq 0

, (tehát az

x_{i}

sorozat nemnegatív és monoton fogyó,) másfelől az

y_{i}

sorozat részletösszegei felülről becsülhetők a

z_{i}

sorozat részletösszegeivel, azaz

\begin{matrix} \sum_{j = 1}^{i} y_{j} \leq \sum_{j = 1}^{i} z_{j} (i = 1, 2, ..., n), \end{matrix}

akkor a

P

összeg felülről becsülhető:

\begin{matrix} \sum_{i = 1}^{n} x_{i} y_{i} \leq \sum_{i = 1}^{n} x_{i} z_{i} . \end{matrix}

(4)

Bizonyítás. Ha

d_{i} = z_{i} - y_{i}

, akkor a (4)-gyel ekvivalens

\begin{matrix} 0 \leq \sum_{i = 1}^{n} x_{i} d_{i} \end{matrix}

egyenlőtlenség jobb oldala az Abel-átrendezés szerint

\begin{matrix} \sum_{i = 1}^{n} (x_{i} - x_{i + 1}) \sum_{j = 1}^{i} d_{j}, \end{matrix}

ebben az összegben pedig minden egyes tag két nemnegatív szám szorzata.

(

A (4) egyenlőtlenséget használtuk a Gy. 2576. gyakorlat megoldásakor, lásd ezen számunk 164. oldalán.

)

Feladat. Bizonyítsuk be a (4) egyenlőtlenség szimmetrikus megfelelőjét, tehát ha

\begin{matrix} 0 \leq x_{1} \leq x_{2} \leq ... \leq x_{n}, és \sum_{j = i}^{n} y_{j} \leq \sum_{j = i}^{n} z_{j} (i = 1, 2, ..., n), \end{matrix}

'

)

akkor ugyancsak fennáll (4).

\begin{matrix} * \end{matrix}

Az Abel-féle egyenlőtlenség első alkalmazásaként bizonyítsuk be a sok nevezetes egyenlőtlenséggel kapcsolatos Szűcs Adolf féle egyenlőtlenséget. Ez utóbbi azt mondja ki, hogy ha

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

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

valós számok, a

c_{1}

c_{2}

...

c_{n}

pedig a

b_{1}

b_{2}

...

b_{n}

sorozat egy tetszőleges permutációja, akkor

\begin{matrix} a_{1} b_{n} + a_{2} b_{n - 1} + ... + a_{n} b_{1} \leq a_{1} c_{1} + ... + a_{n} c_{n} \leq a_{1} b_{1} + ... + a_{n} b_{n}, \end{matrix}

tehát az

a_{1} c_{1} + ... + a_{n} c_{n}

szorzat akkor a legnagyobb, ha a

c_{1}

c_{2}

...

c_{n}

számok ugyanúgy vannak rendezve, mint az

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

sorozat, és akkor a legkisebb, ha ellenkezőleg.
Az egyenlőtlenségek bizonyításához egyszerűen vegyük észre, hogy a

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

feltételből nyilvánvalóan következik a

\begin{matrix} \sum_{j = i}^{n} b_{n + 1 - j} \leq \sum_{j = i}^{n} c_{j} \leq \sum_{j = i}^{n} b_{j}, \end{matrix}

és így alkalmazható az Abel-egyenlőtlenség (4

'

) alakja.
A Szűcs Adolf-egyenlőtlenségből többek között már bebizonyítható a számtani és mértani közepek közti nevezetes egyenlőtlenség is. Erről bővebben olvashatunk Hajós György‐Neukomm Gyula‐Surányi János: Matematikai Versenytételek II. c. könyvének 60‐64. oldalán.
(Az Abel-egyenlőtlenség egy másik alkalmazását láthatjuk a KÖMAL 1985/5. számában, a Gy.2201. megoldásában, a 210. oldalon.)

IV. Egy Erdős-probléma és a búvár feladata
Az eddigi példákban nem okozott túl nagy nehézséget az Abel-egyenlőtlenség feltételeinek a bizonyítása, de vannak esetek, amikor ez egyáltalán nem magától értetődő. Erdős Pál vetette fel az alábbi problémát:
Ha a pozitív egész számokból álló

A = {a_{1}, a_{2}, ..., a_{n}}

halmaz semelyik két részhalmazában nem egyenlő az elemek összege ‐ ilyenek pl. a 2 hatványai ‐ akkor az

A

elemei reciprokának összege kisebb kettőnél.
A probléma nehézségét mutatja, hogy első megoldása során a szerző egyáltalán nem elemi analízisbeli eszközöket használt, többek között azt a tényt, hogy a négyzetszámok reciprokainak összege

\frac{π^{2}}{6}

. Az alábbi megoldás igen hatásosan veti be az Abel-egyenlőtlenséget.
Először is jegyezzük meg, hogy mivel az

A

tetszőleges

i

elemű részhalmazából

2^{i} - 1

darab összeg készíthető, ezért ha ezek az összegek valamennyien különbözők, akkor legnagyobbikuk legalább ekkora, azaz

2^{i} - 1 = 1 + 2 + ... + 2^{i - 1}

.
Fennáll tehát minden

1 \leq i \leq n

-re, hogy

\begin{matrix} 1 + 2 + ... + 2^{i - 1} \leq a_{1} + a_{2} + ... + a_{i} . \end{matrix}

(

*

)

Ha most feltesszük, hogy

a_{1} < a_{2} < ... < a_{n}

, akkor nyilván

\begin{matrix} \frac{1}{a_{1}} > \frac{1}{2 a_{2}} > ... > \frac{1}{2^{n - 1} a_{n}} > 0. \end{matrix}

Ezek után nincs egyéb dolgunk, mint alkalmazni a (4) egyenlőtlenséget az

x_{i} = \frac{1}{2^{i - 1} a_{i}}

y_{i} = 2^{i - 1}

z_{i} = a_{i}

szereposztással:

\begin{matrix} \sum_{i = 1}^{n} \frac{1}{a_{i}} = \sum_{i = 1}^{n} x_{i} y_{i} \leq \sum_{i = 1}^{n} x_{i} z_{i} = \sum_{i = 1}^{n} \frac{1}{2^{i - 1}} = 2 - \frac{1}{2^{n - 1}}; \end{matrix}

még valamivel élesebb állítást is kapunk, mint amit bizonyítanunk kellett, és a 2 hatványai mutatják, hogy a kapott becslés tovább már nem javítható.
Befejezésül egy érdekes és nehéz feladat megoldását szeretném bemutatni. A feladat Herczeg Jánostól származik.
Adott

n

darab egységnyi térfogatú oxigénpalack, bennük a nyomások rendre

p_{1} \geq p_{2} \geq ... \geq p_{n} \geq 0

. Célunk az, hogy a legkisebb,

p_{n}

nyomású palackban a lehető legnagyobbra növeljük a nyomást. Ehhez egy-egy lépésben a palackok tetszőleges csoportját összekapcsolhatjuk, aminek következtében az összekapcsolt palackok mindegyikében a résztvevő nyomások számtani közepe lesz az eredő nyomás. A palackok ezután szétkapcsolhatók, és új csoportok hozhatók létre.
A fő nehézséget a feladatban az okozza, hogy mivel az összekapcsolások sorozata tetszőleges sokáig folytatható, ezért ‐ ha csak nem kapcsoljuk egyszerre össze valamennyi palackot ‐ az

n

palackban létrehozható nyomások értékeinek halmaza nem véges, így egyáltalán nem biztos, hogy létezik a szóban forgó maximum. Másfelől az is elképzelhető, hogy az eljárás ‐ és a maximum értéke is, amennyiben létezik ‐ különböző kezdeti nyomásértékekre más és más módon függ azoktól.
Megmutatjuk, hogy nem ez a helyzet. A megoldás kulcsa most is az Abel-féle egyenlőtlenség, itt azonban távolról sem világos, hogyan teremthetők meg alkalmazásának feltételei.
Ha

m

darab palackot kapcsolunk össze, akkor a nyomás kiegyenlítődése úgy is felfogható, hogy minden egyes érintett palack tartalmát

m

egyenlő részre osztjuk, és ezeket a részeket osztjuk szét az

m

darab palack között. Próbáljuk meg ebben a modellben nyomon követni, hogy összekapcsolások egy sorozatának végrehajtása után az egyes oxigénrészecskék honnan kerültek pillanatnyi helyükre!
Jelöljük tehát

α_{i j}^{(k)}

-val, hogy a

k

-adik összekapcsolás után a

j

-edik palack tartalmának hányadrésze került az

i

-edik palackba. Ha például elsőre a 2., 4. és 5. palackot kapcsoltuk össze, akkor

α_{i j}^{(1)} = \frac{1}{3}

, ha

i

és

j

a 2, 4, 5 számok közül valók, egyébként 1 vagy 0 attól függően, hogy

i = j

, vagy sem.
Nyilván

0 \leq α_{i j}^{(k)} \leq 1

α_{i j}^{(0)} = 1

, ha

i = j

, egyébként pedig 0, és az is látszik, hogy ha az

i

-edik és

j

-edik palackot a

k

-adik összekapcsolásig még nem kapcsoltuk össze, akkor

α_{i j}^{(k)} = 0

.
Ezzel a jelöléssel modellünk szerint az

i

-edik palackban a

k

-adik összekapcsolás után

\begin{matrix} p_{i}^{(k)} = \sum_{j = 1}^{n} α_{i j}^{(k)} p_{j} \end{matrix}

(5)

lesz a nyomás.
Az

α_{i j}^{(k)}

együtthatók további vizsgálata vezethet el a feladat megoldásához. Először is, mivel az eljárás során minden egyes palack tartalma megvan valahol,

\begin{matrix} \sum α_{i j}^{(k)} = 1, j = 1, 2, ..., n . \end{matrix}

Megmutatjuk, hogy (5) jobb oldalán a

p_{j}

kezdeti nyomások együtthatóinak is 1 az összege, azaz rögzített

i

-re

\begin{matrix} \sum_{j = 1}^{n} α_{i j}^{(k)} = 1, \end{matrix}

(6)

(α_{i j}^{(k)})

mátrixban tehát az oszlopokon kívül a sorok összege is 1, úgynevezett bisztochasztikus mátrixszal van dolgunk.
A (6) egyenlőséget igazolhatnánk számolással is ‐ jó gyakorlás azok számára, akik ismerik a mátrixok szorzását ‐ itt azonban egy szemléletesebb gondolatmenetet követünk.
Vegyük észre, hogy az

α_{i j}^{(k)}

mennyiségek kizárólag az összekapcsolások sorozatától függenek, a kezdeti nyomásoktól nem. Ez azt jelenti, hogy ha a szóban forgó

k

darab összekapcsolást olyan palackokon hajtjuk végre, amelyekben kezdetben egyenlők a nyomások, akkor ugyanezek az

α_{i j}^{(k)}

együtthatók adódnak, másfelől most természetesen egyetlen palack nyomása sem változik,

p_{i}^{(k)} = p_{i} = p

. Az (5) egyenlőség két oldalán

p

-vel osztva megkapjuk (6)-ot.
Feladatunk tehát a

\begin{matrix} p_{n}^{(k)} = \sum_{j = 1}^{n} α_{n j}^{(k)} p_{j} \end{matrix}

mennyiség maximumának megtalálása. Mivel az együtthatók összege 1, azért csak egymás rovására növelhetők. Az Abel-egyenlőtlenség szerint azonban elegendő egy felső becslést találni az együtthatók részletösszegeire, hiszen a

p_{i}

sorozat monoton fogyó.
Belátjuk, hogy az

α_{n j}^{(k)}

együtthatók

s_{n m}^{(k)}

részletösszegeire

\begin{matrix} s_{n m}^{(k)} = \sum_{j = 1}^{m} α_{n j}^{(k)} \leq \frac{1}{2} + \frac{1}{4} + ... + \frac{1}{2^{m}} = 1 - \frac{1}{2^{m}}, \end{matrix}

(7)

m < n

, és mivel már láttuk, hogy

\begin{matrix} 1 = s_{n n}^{(k)} = \frac{1}{2} + \frac{1}{2^{2}} + ... + \frac{1}{2^{n - 1}} + \frac{1}{2^{n - 1}}, \end{matrix}

ezért az Abel-egyenlőtlenség szerint

\begin{matrix} p_{n}^{(k)} = α_{n 1}^{(k)} p_{1} + ... + α_{n n}^{(k)} p_{n} \leq \frac{1}{2} p_{1} + \frac{1}{4} p_{2} + ... + \frac{1}{2^{n - 1}} p_{n - 1} + \frac{1}{2^{n - 1}} p_{n} . \end{matrix}

(8)

A (8) egyenlőtlenség jobb oldalán álló nyomásérték viszont megvalósítható, ha a legkisebb nyomású palackot növekvő sorrendben rendre összekapcsoljuk a nála nagyobb nyomású palackokkal. Így a legkisebb nyomású palackban elérhető maximális nyomás

\begin{matrix} M_{n} = \frac{1}{2} p_{1} + \frac{1}{4} p_{2} + ... + \frac{1}{2^{n - 1}} p_{n - 1} + \frac{1}{2^{n - 1}} p_{n} . \end{matrix}

(

* *

)

Hátra van még a (7) egyenlőtlenségek bizonyítása. Mivel az

α_{n j}

együtthatók összege 1, elegendő alulról becsülni az

1 - s_{n m}^{(k)}

mennyiségeket; azt fogjuk bebizonyítani, hogy ha

0 \leq m \leq n

, akkor

\begin{matrix} 1 - s_{n m}^{(k)} = \sum_{j = m + 1}^{n} α_{n j}^{(k)} \geq \frac{1}{2^{m}} . \end{matrix}

(9)

Tekintsünk ehhez

n

darab oxigénpalackot, melyek közül az első

m

darab üres, a további

(n - m)

palackban pedig egységnyi a nyomás, és hajtsuk végre ezekre palackokra ugyanazokat az összekapcsolásokat, amelyeket az eredeti palackokra. A

k

-adik összekapcsolás után kapott nyomásokat most is változatlan

a_{i j}^{(k)}

együtthatókkal szolgáltatják az (5) formulák, de természetesen a

\begin{matrix} p_{1} = p_{2} = ... = p_{m} = 0, p_{m + 1} = p_{m + 2} = ... = p_{n} = 1 \end{matrix}

(10)

kezdeti nyomásokkal.
Most tehát az

i

-edik palack nyomása a

k

-adik összekapcsolás után

\begin{matrix} α_{i 1}^{(k)} \cdot 0 + α_{i 2}^{(k)} \cdot 0 + ... + α_{i, m}^{(k)} \cdot 0 + α_{i, m + 1}^{(k)} \cdot 1 + ... + α_{i n}^{(k)} \cdot 1 = \\ = α_{i, m + 1}^{(k)} + ... + α_{i n}^{(k)} = 1 - s_{i m}^{(k)} \end{matrix}

éppen a (7)-beli részletösszegekkel. Maga a bizonyítandó (9) egyenlőtlenség pedig azt jelenti, hogy ha a kezdeti nyomásokat (10) szerint választjuk, akkor az

n

-edik palackban a nyomás nem süllyedhet

\frac{1}{2^{m}}

alá.
Érdekes módon az eredeti kérdés duálisát kell megválaszolnunk ‐ tudniillik hogy milyen kicsi lehet egy kezdetben nem üres palackban a nyomás ‐ nagyon speciális kezdeti értékek esetén.
Azt fogjuk belátni, hogy ha palackjaink közül

m

darab üres, a többiekben pedig egységnyi a nyomás, akkor a nem üres palackok nyomásának a minimuma nem lehet kisebb

\frac{1}{2^{m}}

-nél. Ebből az állítás következik, hiszen egy kezdetben nem üres palack nem ürülhet ki, ami azt is jelenti, hogy egy összekapcsolás során az üres palackok száma nem nőhet.
Ha egy összekapcsolásban nem vesz részt üres palack, akkor a fenti minimum nyilván nem csökken. Meg kell még vizsgálnunk, mi történik a pozitív nyomások

p

minimumával, ha üres palackok is részt vesznek az összekapcsolásban.
Tegyük fel tehát, hogy egy összekapcsolásban

r

darab nem üres és

t

darab üres palack vesz részt

(t \leq m)

. Ekkor az összekapcsolt palackokban az eredő nyomás legalább

\frac{r p}{r + t}

, a további nem üres palackokban pedig legalább

p

. Mivel nyilvánvalóan

\begin{matrix} \frac{r p}{r + t} \geq \frac{p}{2^{t}}, \end{matrix}

(11)

r

és

t

pozitív egészek, így ha egy összekapcsolás során az üres palackok száma

t

-vel csökken

(1 \leq t \leq m)

, akkor eközben a nem üres palackok nyomásának a minimuma legfeljebb

2^{t}

-ed részére csökkenhet. Mivel kezdetben

m

darab üres palack van, a nem üres palackok nyomásának a minimuma a kezdeti értéknek ‐ ami 1 volt ‐ legfeljebb az

\frac{1}{2^{m}}

-szerese, és ezt akartuk bizonyítani.

\begin{matrix} * \end{matrix}

Feladatok 1. Bizonyítsuk be, hogy a

(* *)

maximumot szolgáltató eljárás egyértelmű, azaz, ha nem az

(n, n - 1)

(n, n - 2)

...

(n, 2)

(n, 1)

kettősöket kapcsoljuk össze ebben a sorrendben, akkor az

n

-edik palackban sosem érhető el

M

(Természetesen, ha a kezdeti értékek között vannak egyenlők, akkor az ezekkel való összekapcsolás sorrendje felcserélhető, illetve ezek összekapcsolhatók egymással is.)

2. Bizonyítsuk be, hogy ha a palackokban a kezdeti nyomások

p_{1} \geq p_{2} \geq ... \geq p_{m} \geq ... \geq p_{n}

, akkor az

m

-edik palackban legfeljebb

\begin{matrix} M_{m} = \frac{1}{2} p_{1} + \frac{1}{4} p_{2} + ... + \frac{1}{2^{m - 1}} p_{m - 1} + \frac{1}{2^{m - 1}} p_{m} \end{matrix}

nyomás érhető el, és az ezt szolgáltató eljárás lényegében egyértelmű. (Az állítás nem teljesen triviális, hiszen a kérdés nem egyenértékű azzal, hogy csupán a

p_{1}

p_{2}

...

p_{m}

nyomású palackjaink vannak. A feladat éppen annak igazolását kívánja, hogy a kisebb nyomású palackoknak nem vehetjük hasznát.)