Kezdőlap


Cím:	Mire jó (időnként) a dolgok elbonyolítása? 2. rész
Szerző(k):	Freud Róbert
Füzet:	1995/január, 1 - 6. 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.

^{$^{*}$}
Egyes feladatok megoldását teljes részletességgel megadjuk, máshol csak megoldásvázlatot közlünk, ilyenkor érdemes a hiányzó lépéseket önállóan végiggondolni. A megoldások során többször hivatkozunk majd a múltkori cikkben szereplő útmutatásokra is.

1a.

(\binom{k}{0}) (\binom{n}{r}) + (\binom{k}{1}) (\binom{n}{r - 1}) + (\binom{k}{2}) (\binom{n}{r - 2}) + ... + (\binom{k}{r}) (\binom{n}{0}) = ?

Megoldás. Hány

r

elemű részhalmaza van az

1,2, ..., n + k

számok halmazának? A válasz nyilván

(\binom{n + k}{r})

. Számoljuk most össze ezeket az

r

elemű részhalmazokat aszerint, hogy hány

n

-nél nagyobb szám van bennük. Ha az

n

-nél nagyobb elemek száma

j

, akkor ezt a

j

elemet az

n + 1, ..., n + k

számok közül

(\binom{k}{j})

-féleképpen vehetjük, a többi

r - j

elemet pedig az

1, ..., n

számok közül

(\binom{n}{r - j})

-féleképpen választhatjuk. Ezt minden lehetséges

j

-re összegezve éppen a fenti összeg adódik. Ennek egyszerűbb alakja tehát

(\binom{n + k}{r})

1b.

(\binom{0}{k}) (\binom{r}{n}) + (\binom{1}{k}) (\binom{r - 1}{n}) + (\binom{2}{k}) (\binom{r - 2}{n}) + ... + (\binom{r}{k}) (\binom{0}{n}) = ?

Megoldás. Az

1,2, ..., r + 1

számok

k + n + 1

elemű részhalmazait aszerint számoljuk össze, hogy melyik bennük a nagyság szerint

k + 1

-edik elem. Eredmény:

(\binom{r + 1}{k + n + 1})

*	a) $k^{k} - (\binom{k}{1}) {(k - 1)}^{k} + (\binom{k}{2}) {(k - 2)}^{k} - (\binom{k}{3}) {(k - 3)}^{k} + ... = ?$

*	b) $k^{k - 1} - (\binom{k}{1}) {(k - 1)}^{k - 1} + (\binom{k}{2}) {(k - 2)}^{k - 1} - (\binom{k}{3}) {(k - 3)}^{k - 1} + ... = ?$

*	c) $k^{k + 1} - (\binom{k}{1}) {(k - 1)}^{k + 1} + (\binom{k}{2}) {(k - 2)}^{k + 1} - (\binom{k}{3}) {(k - 3)}^{k + 1} + ... = ?$

*	d) $(\binom{k + n - 1}{n}) - (\binom{k}{1}) (\binom{k + n - 2}{n}) + (\binom{k}{2}) (\binom{k + n - 3}{n}) - (\binom{k}{3}) (\binom{k + n - 4}{n}) + ... = ?$

Megoldás. Az a), b) és c) összeg mindegyike

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

(1)

alakú. Vizsgáljuk most a következő kérdést: a

k + 1

alapú számrendszerben hány olyan

n

-jegyű szám van, amelyben nincs 0 számjegy, de minden nemnulla számjegy legalább egyszer előfordul. Ezt a feladatot a logikai szitaformula (lásd pl. a múltkori cikket) segítségével oldhatjuk meg. A

H

alaphalmaz azon

n

-jegyű számokból áll, amelyekben nem szerepel a 0. Összesen

k^{n}

ilyen szám van. A

H_{i}

részhalmazt azok a számok alkossák, amelyekből az

i

számjegy hiányzik (

i = 1,2, ..., k

). Könnyen adódik, hogy a logikai szitaformula ebben az esetben egyrészt éppen az (1) összeg, másrészt azon

n

-jegyű számok számát adja meg, amelyekből ,,egyik számjegy sem hiányzik'', azaz minden számjegy legalább egyszer előfordul. Mivel

n \leq k + 1

-re az ilyen számok száma közvetlenül is egyszerűen meghatározható, így megkaptuk ezeknek az összegeknek az egyszerű alakját. Eredmények: a)

k!

; b) 0; c)

(k + 1)! k / 2

.
A d) rész az előző feladat analogonja variáció helyett kombinációval: hányféleképpen lehet

k

-féle csokoládéból

n

darabot vásárolni úgy, hogy mindegyik fajtából vásárolunk legalább egyet. A szitaformulás leszámlálás éppen a keresett összeg, ugyanakkor most bármely

n

-re van közvetlen megoldás is: mindegyik fajtából elveszünk egyet és a maradék

n - k

darabot tetszőlegesen választjuk. Az eredmény tehát:

(\binom{n - 1}{n - k})

3a.

(\binom{n}{0}) - (\binom{n}{2}) + (\binom{n}{4}) - (\binom{n}{6}) + ... = ?

Megoldás. Ez az összeg az

{(1 + i)}^{n}

komplex szám valós része, ha a binomiális tétel szerint hatványozunk. Ugyanezt a trigonometrikus alakkal a Moivre-formula szerint elvégezve

2^{n / 2} cos (n π / 4)

adódik.

3b.

(\binom{n}{0}) + (\binom{n}{3}) + (\binom{n}{6}) + (\binom{n}{9}) + ... = ?

Megoldás. A megoldás kulcsa az, hogy a

k

-adik komplex egységgyökök

r

-edik hatványainak az összege

k

, ha

k | r

, és 0 minden más

r

esetén (lásd pl. a múltkori cikket). Ezt

k = 3

-ra alkalmazva, a kérdéses összeg

3

-szorosa megegyezik az

S = {(1 + 1)}^{n} + {(1 + ρ_{1})}^{n} + {(1 + ρ_{2})}^{n}

kifejezésnek a binomiális tétel szerinti kifejtésével, ahol

1, ρ_{1}

és

ρ_{2}

a harmadik egységgyökök. Ez utóbbi kifejezés a következő alakba írható:

\begin{matrix} \begin{matrix} S & = 2^{n} + {(cos \frac{π}{3} + i sin \frac{π}{3})}^{n} + {(cos \frac{π}{3} - i sin \frac{π}{3})}^{n} = \\ = 2^{n} + (cos \frac{n π}{3} + sin \frac{n π}{3}) + (cos \frac{n π}{3} - sin \frac{n π}{3}) = 2^{n} + 2 cos \frac{n π}{3} . \end{matrix} \end{matrix}

Ennek alapján a feladatbeli összeg értéke

(2^{n} + 2 cos \frac{n π}{3}) / 3

.
Hasonló módon kezelhető általában is a

T_{k} = (\binom{n}{0}) + (\binom{n}{k}) + (\binom{n}{2 k}) + (\binom{n}{3 k}) + ...

összeg, csak az eredmény kicsit bonyolultabbá válik:

\begin{matrix} \begin{matrix} (2) k \cdot T_{k} = \sum_{j = 1}^{k} {(1 + ρ_{j})}^{n} = \\ = {(2 cos \frac{π}{k})}^{n} [cos \frac{n π}{k} + i sin \frac{n π}{k}] + {(2 cos \frac{2 π}{k})}^{n} [cos \frac{2 n π}{k} + i sin \frac{2 n π}{k}] + \\ + ... + {(2 cos \frac{k π}{k})}^{n} [cos \frac{k n π}{k} + i sin \frac{k n π}{k}], \end{matrix} \end{matrix}

ahol

ρ_{1}, ..., ρ_{k}

k

-adik egységgyökök. Ne tévesszen meg bennünket, hogy maga az eredmény is egy (elég ijesztőnek tűnő) összeg, ugyanis ennek a tagszáma már nem függ

n

-től, és így bármely konkrét

k

(és általános

n

) esetén ,,kényelmesen'' kiszámolható (amint ezt

k = 3

-ra a 3a) feladatnál el is végeztük).

3c.

{(cos \frac{π}{5})}^{n} sin \frac{n π}{5} + {(cos \frac{2 π}{5})}^{n} sin \frac{2 n π}{5} + ... + {(cos \frac{5 π}{5})}^{n} sin \frac{5 n π}{5} = ?

Megoldás. A (2)-ben szereplő komplex szám képzetes részének

2^{- n}

-szereséről van szó

k = 5

mellett, ami 0, hiszen a

T_{5}

összeg nyilvánvalóan valós.

\begin{matrix} \begin{matrix} \frac{1}{(x_{1} - x_{2}) (x_{1} - x_{3}) ... (x_{1} - x_{r})} + \frac{1}{(x_{2} - x_{1}) (x_{2} - x_{3}) ... (x_{2} - x_{r})} + ... + \\ + \frac{1}{(x_{r} - x_{1}) (x_{r} - x_{2}) ... (x_{r} - x_{r - 1})} = ? \end{matrix} \end{matrix}

Megoldás. Ha

x_{1}, ..., x_{r}

különböző számok és

y_{1}, ..., y_{r}

tetszőleges, akkor pontosan egy olyan legfeljebb

r - 1

-edfokú

f

polinom létezik, amelyre

f (x_{i}) = y_{i}

. Több ilyen polinom azért nem létezhet, mert akkor a különbségük egy olyan legfeljebb

r - 1

-edfokú polinom lenne, amelynek mind az

r

darab

x_{i}

gyöke, azonban egy polinomnak legfeljebb annyi gyöke lehet, mint amennyi a fokszáma.
Az, hogy ilyen tulajdonságú

f

polinom valóban létezik, többféleképpen is igazolható. Az alábbiakban egy konstrukciót mutatunk erre. Először azt a speciális esetet oldjuk meg, amikor az előírt értékek

y_{1} = 1, y_{2} = ... = y_{r} = 0

. Ekkor a polinomnak tartalmaznia kell minden

j > 1

-re az

(x - x_{j})

gyöktényezőt, tehát a fokszámkorlátozás miatt csak a szorzatuk konstansszorosa lehet.
A konstans szorzó értéke az

y_{1} = 1

feltétel miatt

\prod_{j > 1} 1 / (x_{1} - x_{j})

, maga a polinom tehát

L_{1} (x) = \prod_{j > 1} (x - x_{j}) / (x_{1} - x_{j})

. Hasonlóan kapjuk bármely

i

-re azt a legfeljebb

r - 1

-edfokú

L_{i}

polinomot, amely az

x_{i}

helyen az 1 értéket veszi fel, a többi

x_{j}

helyen pedig a 0-t:

L_{i} (x) = \prod_{j \neq i} (x - x_{j}) / (x_{i} - x_{j})

. Ezután az általános esetben a keresett polinom a következőképpen kapható meg (Lagrange-féle interpolációs formula):

\begin{matrix} f (x) = \sum_{i = 1}^{r} y_{i} L_{i} (x) = \sum_{i = 1}^{r} y_{i} \prod_{j \neq i}^{} (x - x_{j}) / (x_{i} - x_{j}) . \end{matrix}

Tekintsük most azt a speciális esetet, amikor minden

y_{i} = 1

. Egyrészt alkalmazhatjuk az interpolációs formulát, másrészt viszont nyilván

f \equiv 1

. A kétféle felírásban

x^{r - 1}

együtthatóját összehasonlítva kapjuk, hogy a feladatban kérdezett összeg 0.

\begin{matrix} \sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k}) {(\frac{1}{4})}^{k} {(\frac{5}{12})}^{n - 2 k} = ? \end{matrix}

\sum

jel azt jelenti, hogy a mögötte álló kifejezés értékét a megadott

k

értékekre kell összegezni.

⌊ z ⌋

z

szám (alsó) egész részét jelöli.)

Megoldás. Tegyük fel, hogy egy szerencsejátékban

1 / 4

valószínűséggel 2 pontot nyerünk,

5 / 12

valószínűséggel 1 pontot nyerünk, és a fennmaradó

1 / 3

valószínűséggel a játékból kiesünk. (Amíg nem estünk ki, addig folytathatjuk a játékot.)
Ekkor a kérdéses

p_{n}

összeg éppen annak a valószínűségét jelenti, hogy pontosan

n

pontot össze tudunk gyűjteni (és akkor megállunk). Ugyanis

n

pont úgy jön össze, hogy

k

-szor 2 pontot nyerünk és

n - 2 k

-szor 1 pontot (és közben nem estünk ki), ahol

0 \leq k \leq ⌊ n / 2 ⌋

.
Másrészt

n

pontot úgy érünk el, hogy előtte

n - 2

pontunk volt, és 2 pontot nyertünk, vagy pedig előtte

n - 1

pontunk volt, és 1 pontot nyertünk; ez pedig éppen azt jelenti, hogy

p_{n}

eleget tesz a

p_{n} = (1 / 4) p_{n - 2} + (5 / 12) p_{n - 1}, n > 1

rekurziónak. A múltkori útmutatásban már szerepelt, hogy egy ilyen típusú

a_{n} = α a_{n - 1} + β a_{n - 2}

rekurzió megoldása

a_{n} = c_{1} x_{1}^{n} + c_{2} x_{2}^{n}

alakú, ha

x_{1}

és

x_{2}

x^{2} - α x - β = 0

egyenlet különböző gyökei,

c_{1}

és

c_{2}

pedig a kezdeti

a_{0}

és

a_{1}

értékekből határozható meg (lásd pl. Poros Tibor cikkében, KöMaL 1993/8‐9). Ennek alapján

p_{n} = (9 / 13) \cdot {(3 / 4)}^{n} + (4 / 13) \cdot {(- 1 / 3)}^{n}

.
(Ez a feladat könnyített formában szerepelt az 1992. évi Országos Középiskolai Tanulmányi Versenyen: ott meg volt adva az azonosság, és azt kellett igazolni. Ez persze jelentős könnyítés, hiszen ,, ha már tudjuk, hogy mit kell bizonyítani'', akkor például teljes indukcióval is célhoz érhetünk, bár az nem mutatja meg a dolgok ,,miért''-jét.)

6a.

\sum_{n = 1}^{\infty} \frac{d (n)}{n^{2}} = ?

ahol

d (n)

n

pozitív osztóinak a száma.

Megoldás. Szorozzuk meg a

\sum_{k = 1}^{\infty} 1 / k^{2}

végtelen sort önmagával. Mivel pozitív tagokból álló (tehát abszolút konvergens) sorról van szó, ezért ‐ mint már a múltkori útmutatásban is említettük ‐ jogosak a véges összegeknél megszokott szabályok: ,,minden tagot minden taggal összeszorzunk'', és a kapott szorzatokat tetszőleges sorrendben csoportosíthatjuk és összegezhetjük.
A tagok szorzásánál csupa

(1 / k^{2}) \cdot (1 / r^{2}) = 1 / n^{2}

alakú szorzat jön létre, éspedig

1 / n^{2}

-es eredmény annyiszor keletkezik, ahányféleképpen az

n

felírható

n = k \cdot r

alakban. Az ilyen lehetőségek száma éppen

d (n)

. Vagyis a két sor szorzata nem más, mint a feladatban kérdezett összeg. Ennek megfelelően az eredmény

{(π^{2} / 6)}^{2} = π^{4} / 36

6b.

\sum_{n = 1}^{\infty} \frac{φ (n)}{2^{n} - 1} = ?

ahol

φ (n)

1,2, ..., n

számok között az

n

-hez relatív prímek száma.

Megoldás. Az

| x | < 1

-re abszolút konvergens végtelen sorokkal némi (megengedett) bűvészkedés után

\begin{matrix} \sum_{n = 1}^{\infty} φ (n) \frac{x^{n}}{1 - x^{n}} = \sum_{n = 1}^{\infty} φ (n) \sum_{j = 1}^{\infty} x^{j n} = \sum_{s = 1}^{\infty} x^{s} \sum_{d | s}^{} φ (d) = \sum_{s = 1}^{\infty} s x^{s} = \frac{x}{{(1 - x)}^{2}} . \end{matrix}

Az első lépésben az

x^{n} / (1 - x^{n})

törtet ,,elbonyolítottuk'' egy végtelen mértani sorrá. A második lépésben átrendeztük az összegeket és

x

hatványai szerint csoportosítottuk. A harmadik lépésben a

\sum_{d | s} φ (d) = s

azonosságot használtuk: ennek igazolásához tekintsük az

1 / s,2 / s, ..., s / s

törteket. Ezek száma nyilván

s

, ugyanakkor a következő bonyolultabb módon is összeszámolhatók: egyszerűsítsük mindegyiket, amennyire csak lehet, ekkor olyan

d

nevezőjű törteket kapunk, ahol

d | s

, és a

d

nevező éppen

φ (d)

-szer lép fel. Végül az utolsó lépés igazolásához a

\sum_{s = 1}^{\infty} s x^{s}

sort végtelen sok végtelen mértani sor összegévé rendezzük át:

\begin{matrix} \begin{matrix} x + 2 x^{2} + 3 x^{3} + 4 x^{4} + ... = (x + x^{2} + x^{3} + ...) + (x^{2} + x^{3} + x^{4} + ...) + \\ + (x^{3} + x^{4} + ...) + ... = \frac{x}{1 - x} + \frac{x^{2}}{1 - x} + ... = \frac{1}{1 - x} \cdot \frac{x}{1 - x} = \frac{x}{{(1 - x)}^{2}} . \end{matrix} \end{matrix}

A feladatban kérdezett összeget az

x = 1 / 2

helyettesítéssel kapjuk. Eredmény: 2.

6c.

\sum_{n = 1}^{\infty} μ (n) ⌊ \frac{x}{n} ⌋ = ?

(x > 1)

, ahol

μ (n)

a Möbius-függvény:

μ (1) = 1

μ (n) = {(- 1)}^{r}

, ha az

n

szám

r

különböző prím szorzata és minden más esetben

μ (n) = 0

Megoldás. Logikai szita arra, hogy

x

-ig hány olyan pozitív egész van, amely egyetlen prímmel sem osztható: ilyen egyedül az 1, tehát az összeg értéke 1.

1 - 1 / 3 + 1 / 5 - 1 / 7 + ... = ?

Megoldásvázlat: Számoljuk össze a

\sqrt[]{n}

sugarú körben levő rácspontok számát. Ez egyrészt ,,körülbelül'' a kör területe, azaz

n π

, másrészt úgy is megkaphatjuk, hogy az

x^{2} + y^{2} = t

egyenlet egész megoldásainak a számát minden

t \leq n

-re összegezzük.
Az

x^{2} + y^{2} = t

egyenlet egész megoldásainak a száma

4 (d_{1} (t) - d_{3} (t))

, ahol

d_{1} (t)

, ill.

d_{3} (t)

jelöli a

t

szám

4 k + 1

, ill.

4 k + 3

alakú pozitív osztóinak a számát.
Ennek alapján a rácspontok számára ,,körülbelül'' a feladatbeli összeg

4 n

-szerese adódik, azaz a keresett érték

π / 4

. Részletesen lásd Laczkovich Miklós cikkében, KöMaL 1983/3.
A fenti végtelen sor összegét elsőként Leibniz határozta meg nagyon szellemes, de egészen más módon, erre nem térünk ki. Megjegyezzük még, hogy hatványsorok segítségével a feladat ,,könnyen'' megoldható:

arctg x

hatványsora

\begin{matrix} arctg x = x - \frac{x^{3}}{3} + \frac{x^{5}}{5} - \frac{x^{7}}{7} + ... (- 1 \leq x \leq 1) . \end{matrix}

x = 1

helyettesítéssel éppen a feladatban kérdezett összeget kapjuk, amelynek értéke tehát

arctg 1 = π / 4

(\binom{2 n}{n}) - (\binom{2 n - 1}{n}) (\binom{n}{1}) + (\binom{2 n - 2}{n}) (\binom{n}{2}) - ... + {(- 1)}^{n} (\binom{2 n - n}{n}) (\binom{n}{n}) = ?

Megoldás. Még egy szita: Hány olyan

n

elemű részhalmaza van az

1,2, ...,2 n

számoknak, amely éppen az

1,2, ..., n

számokból áll? Eredmény: 1.
(Ez a feladat ‐ bizonyítandó azonosság formájában ‐ szerepelt az 1991. évi Országos Középiskolai Tanulmányi Versenyen. Az eredmény megadása itt nem jelentett igazi könnyítést, mert egyrészt elég könnyen megsejthető néhány

n

érték kipróbálásával, másrészt a teljes indukció nemigen működik.)

Kedves Diákok!
Ha kedvet kaptak némi további ,,bonyolításhoz'', akkor gyártsanak hasonló csúnya összegeket, amelyek ilyen módszerekkel szép alakra hozhatók, és küldjék be a szerkesztőségnek 1995. május 31-ig (cím: KöMaL Szerkesztőség, Budapest, 114. Pf. 68. 1525) a borítékra írják rá, hogy ,,Elbonyolítás''). A legszebb (pontosabban legcsúnyább) feladványokat kitűzzük a pontversenyben.

Freud Róbert

^{$^{*}$}A feladatok a KöMaL 1994/10 számában jelentek meg. A cikkek a szerzőnek a TIT Szabadegyetem és a Fővárosi Pedagógiai Intézet 1994. február 8-án elhangzott tanártovábbképző előadása alapján készültek.