Kezdőlap


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

A dolgok elbonyolítása a matematikai feladatmegoldás természetes velejárója. A problémák megoldása során általában nem rögtön a legegyszerűbb utat járjuk be, hanem gondolataink sokszori vargabetűje után érünk csak célhoz. Később persze megpróbáljuk a megoldást csiszolni, a lényeges lépéseket kihámozni, esetleg rövidebb utat keresni. Azonban egy szép, letisztult megoldást is csak akkor tudunk igazán megbecsülni, ha előtte keményen megdolgoztunk és megszenvedtünk egy ,,csúnyáért''.
Természetesen általában nem a bonyolult, hanem az egyszerű megoldásokra törekszünk. Ezzel együtt egy elbonyolításnak szerencsés esetben lehet olyan haszna, hogy így véletlenül egy új és hatékony módszert fedezünk fel, amely egyébként rejtve maradt volna; az adott feladat megoldásához erre a módszerre ugyan nem lett volna szükség, de valamely más kérdésnél csakis ennek segítségével boldogulhatunk.
Néha azonban még az is kifejezetten hasznos, ha valamit szándékosan bonyolítunk el. A bonyolult megoldást ugyanis az egyszerűvel összevetve kezelhetetlennek látszó kifejezésekre sikerül egyszerű alakot találnunk.
Az alábbi kifejezések legtöbbje úgy keletkezett, hogy egy problémát szándékoltan nagyon-nagyon ügyetlenül oldottunk meg. Az ,,ügyes'' megoldással szemben megkaphatjuk ezeknek a kifejezéseknek az egyszerűbb alakját. Az igazi nehézség természetesen annak a felismerése, hogy a szóban forgó kifejezés melyik probléma ,,elbonyolításából'' származik. Egyes feladatoknál ugyan nem pontosan ez a helyzet, de valamennyi megoldásnak a kulcsa valamely probléma kétféle megoldásának az összevetése.
A feladatok a matematika különböző területeire vezetnek el (kombinatorika, albegra, analízis, számelmélet, valószínűségszámítás); a megadott kifejezésekről azonban nem mindig könnyű ráismerni még a megfelelő témakörre sem. Maguk a feladatok is változó nehézségűek, néhánynak a megoldása komolyabb előkészítést és/vagy előismeretet igényel. Ezért senki se keseredjel el, he egyesekkel egyáltalán nem boldogul. A feladatok kitűzése után némi általános útmutatást adunk, azonban ez is csak minimális fogódzót jelent. A megoldásokat a következő számban közöljük.
Addig is mindenkinek jó szórakozást és eredményes elbonyolítást kívánunk.
1. a)

\begin{matrix} (\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}) = ? \end{matrix}

\begin{matrix} (\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}) = ? \end{matrix}

(Ha

0 \leq j < t

, akkor

(\binom{j}{t}) = 0

(\binom{0}{0})

értéke definínió szerint 1.)
2. a)

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

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

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

\begin{matrix} (\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}) + ... = ? \end{matrix}

3. a)

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

\begin{matrix} (\binom{n}{0}) + (\binom{n}{3}) + (\binom{n}{6}) + (\binom{n}{7}) + ... = ? \end{matrix}

\begin{matrix} {(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} = ? \end{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}

\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.)
6. Legyen

d (n)

n

pozitív osztóinak a száma,

φ (n)

1,2, ..., n

számok között az

n

-hez relatív prímek száma, és

μ (n)

a Möbius-függvény:

μ (1) = 1

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

, ha az

n

szám

r

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

μ (n) = 0

.
a)

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

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

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

\begin{matrix} 1 - 1 / 3 + 1 / 5 - 1 / 7 + ... = ? \end{matrix}

\begin{matrix} (\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}) = ? \end{matrix}

Útmutatás az elbonyolításhoz

Az alábbiakban nem konkrét útmutatásokat adunk a feladatokhoz, hanem inkább röviden jelzünk néhány olyan fogalmat, tételt, ill. módszert, amely hasznos lehet és esetleg jó ötleteket sugallhat.
A) Logikai szitaformula
Egy

N

elemű

H

halmaz részhalmazai

H_{1}, H_{2}, ... H_{t}

. Jelölje

N_{i}

H_{i}

elemszámát,

N_{i j}

H_{i} \cap H_{j}

metszet elemszámát,

N_{i j k}

H_{i} \cap H_{j} \cap H_{k}

elemszámát stb. Ekkor az alábbi képlet megadja azon elemek számát, amelyeket egyetlen

H_{i}

sem tartalmaz:

\begin{matrix} N - N_{1} - ... - N_{t} + N_{12} + N_{13} + ... + N_{t - 1, t} - N_{123} - ... + {(- 1)}^{t} N_{12 ... t} . \end{matrix}

B) Komlpex számok
(i) A komplex számok hatványozásánál általában a trigonometrikus alak ad egyszerű eredményt, de remek elbonyolításra nyújt lehetőséget a binomiális tétel.
(ii) Nagyon szép azonosságok érvényesek azokra a komplex számokra, amelyek

k

-adik hatványa 1, ezek a

k

-adik egységgyökök:

ϱ_{j} = cos \frac{2 j π}{k} + i sin \frac{2 j π}{k}

j = 1,2, ..., k

. A

k

-adik egységgyökök

r

-edik hatványainak az összege

k

, ha

k | r

és 0 minden más

r

esetén. Ennek igazolásához írjuk be a

ϱ_{j} = ϱ_{1}^{j}

alakot, és használjuk a mértani sor összegképletét; ha

k ∤ r

, akkor

\begin{matrix} ϱ_{1}^{r} + ϱ_{2}^{r} + ... + ϱ_{k}^{r} = ϱ_{1}^{r} + ϱ_{1}^{2 r} + ... + ϱ_{1}^{k r} = ϱ_{1}^{r} \cdot \frac{ϱ_{1}^{k r} - 1}{ϱ_{1}^{r} - 1} = 0, \end{matrix}

hiszen

ϱ_{1}^{k} = 1

. Ha

k ∣ r

, akkor az összeg minden tagja 1, tehát ekkor az összeg értéke

k

.
C) Rekurziók
A legegyszerűbb típusú lineáris rekurzió egy olyan

a_{0}, a_{1}, ..., a_{n}, ...

végtelen sorozat, ahol

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

minden

n \geq 2

-re. Legismertebb példa erre a Fibonacci-számok, ahol

a_{0} = 0

a_{1} = 1

α = β = 1

. Egy ilyen rekurzió megoldása

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

alakú, ahol

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ékeiből határozhatók meg (részletesen lásd pl. Poros Tibor cikkében, KöMaL 1993/8‐9).
D) Végtelen összegek
A végtelen sorokkal általában vigyázni kell, mert a viselkedésük alapvetően megváltozhat, az a végesben megszokott szabályokat próbáljuk rájuk alkalmazni, pl. a tagok átrendezése vagy két sor ,,kézenfekvően adódó'' összeszorzása általában nem megengedett. Azonben abszolút konvergens sorokkal, azaz olyanokkal, amelyekben a tagok abszolút értékeiből képzett sor is konvergens, teljesen ugyanúgy bánhatunk, mintha véges összegek lennének: két ilyen sort úgy szorzunk össze, hogy ,,minden tagot minden taggal'' megszorzunk, és a kapott végtelen összeget tetszés szerint csoportosíthatjuk.
Az egyik legismertebb végtelen sor a négyzetszámok reciprokösszege, amelynek értéke

π^{2} / 6

. A mai cikket egy ehhez kapcsolódó történeti áttekintéssel zárjuk. Már Euler megmutatta a XVIII. században, hogy hasonló típusú formula érvényes minden páros kitevőjű hatványra is, ugyanakkor érdekes módon a páratlan kitevőjű hatványok reciprokösszegére ma sem ismeretes pontos képlet, sőt a köbszámoktól eltekintve azt sem tudjuk, hogy a szóban forgó reciprokösszeg irracionális-e vagy sem. A köbszámok reciprokösszegéről is csak 1978-ban(!) igazolta Apéry francia matematikus, hogy irracionális. Kár, hogy ezek az összegek csak bonyolultak és (minden bizonnyal) nem valami egyszerűnek az elbonyolított változatai.

Freud Róbert