Kezdőlap


Feladat:	F.1809	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1972/október, 60 - 62. oldal		PDF \| MathML
Témakör(ök):	Sorozat határértéke, Rekurzív eljárások, Kombinációk, Klasszikus valószínűség, Feladat
Hivatkozás(ok):	Feladatok: 1972/február: F.1809

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 lehetséges események száma 10!, ennyiféleképpen permutálhatjuk a leveleket az egy sorban lerögzített borítékok előtt a betevés céljára.
Kedvező eseménynek azt tekintjük, ha a levelek közül valamelyik 5 a saját borítékjába jut, a többi 5 levél viszont úgy helyezkedik el a maradó 5 borítékban ‐ vagyis éppen a nekik szánt 5 borítékban ‐, hogy egyik sem a saját borítékjában van benne. A helyesen borítékolt 5 levél $(\binom{10}{5})$ különböző módon választható meg. Minden ilyen esetben lényegében ugyanaz a további feladat áll előttünk: a hátralevő 5 levél ‐ jelöljük őket röviden az 1, 2, 3, 4, 5 számokkal ‐ olyan sorrendjei, permutációi számának megállapítása a rendre hozzájuk tartozó 1, 2, 3, 4, 5 sorszámú borítékok előtt ‐ röviden: helyeken ‐, amelyekben minden egyes szám részére egy-egy hely tiltott és megfordítva minden egyes hely részére egy-egy szám tiltott, pl. az 1-es szám bárhol állhat, csak az 1. helyen nem, és az 1. helyen bármi állhat, csak az 1-es szám nem, és így tovább.
Nevezzük általában az $1, 2, ..., n$ számok ilyen sorrendjeit e számok abszolút permutációinak, jelöljük a számukat $A_{n}$ -nel. Tegyük fel, hogy $A_{1}$ , $A_{2}$ , $A_{3}$ és $A_{4}$ értékét már ismerjük, megmutatjuk, hogy ezekből $A_{5}$ értéke kiszámítható.
Állítsuk az 5-öst valamelyik kisebb sorszámú helyre, mondjuk a 4-ikre. (Ezzel természetesen a 4-es számra is teljesül a követelmény.) Ha most a 4-est az 5. helyre írjuk be ‐ vagyis a 4 és 5 helyet cserél ‐, ezáltal feladatunk leszűkül az 1, 2, 3 számok abszolút permutálására, az ilyenek száma tehát $A_{3}$ .
Ha pedig a 4-est nem az 5. helyre tesszük, akkor az 1, 2, 3, 4 számok abszolút permutációit kell képeznünk az 1., 2., 3. és 5. helyeken (a 4-es részére más szempont miatt tilos az 5. hely, ti. azért, mert az olyan permutációkat már elintéztük), ide tehát $A_{4}$ számú sorrend tartozik.
Amíg tehát az 5-ös a 4. helyen áll, $A_{3} + A_{4}$ abszolút permutációt kapunk, és ha az 5-ös szám sorra veszi a részére megengedett 4 helyet, akkor $A_{5} = 4 (A_{3} + A_{4})$ -et.
Ugyanezzel a gondolatmenettel $A_{4} = 3 (A_{2} + A_{3})$ és $A_{3} = 2 (A_{1} + A_{2})$ , másrészt nyilvánvalóan $A_{1} = 0$ és $A_{2} = 1$ . Ezek szerint $A_{3} = 2, A_{4} = 9$ és $A_{5} = 44$ , tehát a levél elkeveredési problémában $(\binom{10}{5}) \cdot 4$ 4 a kedvezőnek tekintett esetek száma.
A keresett valószínűség pedig

\begin{matrix} p = \frac{1}{10!} (\binom{10}{5}) \cdot 44 = \frac{10! \cdot 44}{10! 5! 5!} = \frac{44}{120^{2}} = \frac{11}{3600} = 0, 0031. \end{matrix}

(Másképpen: 3600 találomra vett próbálkozás közül 11-szer, azaz 1000-ből 3-szor várható a kívánt típusú elrendeződés.)

Megjegyzések. 1. Hasonlóan azoknak az eseteknek a

k

száma, amelyekben pontosan

j

a jól borítékolt levelek száma:

\begin{matrix} j = & 0, & 1, & 2, & 3, & 4, \\ k = & 1 334 961, & 1 334 960, & 667 485, & 222 480, & 55 650, \end{matrix}

\begin{matrix} j = & 5, & 6, & 7, & 8, & 9, & 10, \\ k = & 11 088, & 1890, & 240, & 45, & 0, & 1. \end{matrix}

Feltűnő, hogy a

j = 0

és

j = 1

számokhoz tartozó

k_{0} = A_{10}

és

k_{1} = 10 \cdot A_{9}

számok csak 1-gyel térnek el egymástól, tehát

A_{10} = 10 \cdot A_{9} + 1

. Ez nem véletlen, alább magyarázatát adjuk.

2. A megoldás gondolatmenete szerint

A_{n} = (n - 1) (A_{n - 1} + A_{n - 2})

. Írjuk fel ezt az egyenlőséget egymás alá

A_{2 n}

-re,

A_{2 n - 1} -re, ..., A_{3}

-ra, szorozzuk meg a páratlan indexűekre vonatkozó sorokat

(- 1)

-gyel:

\begin{matrix} A_{2 n} & = (2 n - 1) A_{2 n - 1} + (2 n - 1) A_{2 n - 2}, \\ - A_{2 n - 1} & = - (2 n - 2) A_{2 n - 2} - (2 n - 2) A_{2 n - 3}, \\ A_{2 n - 2} & = (2 n - 3) A_{2 n - 3} + (2 n - 3) A_{2 n - 4}, \\ ... ... & ... ... ... ... ... ... \\ - A_{5} & = - 4 A_{4} - 4 A_{3}, \\ A_{4} & = 3 A_{3} + 3 A_{2}, \\ - A_{3} & = - 2 A_{2} - 2 A_{1} . \end{matrix}

Összeadással, rendezéssel,

A_{1} = 0

és

A_{2} = 1

figyelembevételével

\begin{matrix} A_{2 n} = 2 n A_{2 n - 1} + 1, \end{matrix}

majd lényegében ugyanígy

\begin{matrix} A_{2 n + 1} = (2 n + 1) A_{2 n} - 1, \end{matrix}

azaz egységesen

\begin{matrix} A_{n} = n \cdot A_{n - 1} + {(- 1)}^{n} . \end{matrix}

3. Meglepő a hasonlóság eredményünk és a permutációk számára érvényes

P_{n} = n \cdot P_{n - 1}

összefüggés között. De mit tesz az a

{(- 1)}^{n}

tagocska, amit a kombinatorikában megszokott "nagy'' számok mellett hajlamosak vagyunk lekicsinyelni! Az első három tagban letöri

A_{n}

-et

P_{n}

-hez képest!

A_{2} = 2 \cdot A_{1} + {(- 1)}^{2}

esetében még ez a "nagyobbik'' a két tag közül, de már így is

A_{2}

csak fele a

P_{2}

-nek; ezután

A_{3} = 3 \cdot A_{2} - 1

esetében még jelentősen csökkent a

{(- 1)}^{3}

tag, és

A_{3} = P_{3} / 3

. A talált 1/3 az

A_{n} / P_{n}

arány legkisebb értéke.
Meg lehet mutatni ‐ az érkezett megoldások ezzel, vagy a hozzá vezető meggondolással dolgoztak, ‐ hogy minden

n

-re

\begin{matrix} A_{n} = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... + {(- 1)}^{n} \cdot \frac{n!}{n!}, \end{matrix}

ebből pedig

\begin{matrix} {lim}_{n \to \infty}^{} \frac{A_{n}}{P_{n}} = \frac{1}{e} = 0, 36 ..., \end{matrix}

ahol

e

a természetes logaritmus alapszáma.

4. A valószínűségszámítás "őskorában'', amikor még kizárólag szerencsejátékok kérdéseit vizsgálták, problémánk 13-as játék (franciául: jeu du treize) néven szerepelt: a francia kártya egy színének 13 lapja hányféleképpen rendezhető el úgy (vagy keverés után vakon egymás után rakva hányféleképpen adódhat), hogy egyik lap se álljon a maga számának megfelelő helyen (a fiú a 11., a dáma a 12., a királya 13 helyen).