Kezdőlap


Feladat:	Gy.2073	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1983/április, 160 - 162. oldal		PDF \| MathML
Témakör(ök):	Kombinatorikai leszámolási problémák, Gyakorlat
Hivatkozás(ok):	Feladatok: 1982/október: Gy.2073

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 szóban forgó számok közül elegendő azokat vizsgálnunk, amelyek nem tartalmazzák a $0$ számjegyet, ugyanis a pontosan kilencjegyű megfelelő számok száma 9! = 362 880, vagyis a legalább tízjegyű, adott tulajdonságú számok valamennyien ennél nagyobb sorszámúak lesznek.
Ha a legnagyobb helyi értékű számjegyet rögzítjük, akkor a további nyolc helyre az összes lehetséges sorrendben beírva a maradék nyolc számjegyet; összesen $8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 8! = 40 320$ -féle kilencjegyű számot kapunk. Ha tehát az első helyen $1$ -es áll, akkor a kezdő 40 320 darab számot kapjuk meg, ha $2$ -es, akkor a következő 40 320-at, azaz a 40 321-ediktől 80 640-edikig, ha pedig $3$ -as, akkor a 80 641-ediktől a 120 960-adikig kapjuk meg a számokat. Látható, hogy a keresett, 100 000-edik helyen álló szám első jegye $3$ -as. A továbbiakban azt kell megvizsgálnunk, hogy az 1, 2, 4, 5, 6, 7, 8, 9 jegyek mindegyikét pontosan egyszer tartalmazó nyolcjegyű számok közül melyik a $100 000 - 80 640 = 19 360$ -adik, nagyság szerint.
Ha most egy nyolcjegyű számban rögzítjük az első jegyet, akkor a további hét jegy minden lehetséges sorrendjének megfelelően $7! = 5040$ különböző számot kapunk. 19 360 = $3 \cdot 5040 + 4240$ , tehát a második helyen szóba jövő számjegyek közül sorrendben a negyediket kiválasztva kaphatjuk meg a 19 360-adik nyolcjegyű számot. Ez a számjegy most az $5$ -ös. Tovább haladva az 1, 2, 4, 6, 7, 8, 9 jegyekből álló hétjegyű számok közül kell megkeresnünk a $4240$ -ediket.
Egy hétjegyű szám első jegyét rögzítve $6! = 720$ -féle számot kapunk. $4240 = 5 \cdot 720 + 640$ , így a még szóba jöhető számjegyek közül a hatodikat, a $8$ -ast kell kiválasztanunk a harmadik helyre. Most az 1, 2, 4, 6, 7, 9 jegyekből álló hatjegyű számok közül kell megkeresnünk a $640$ -ediket.
Egy hatjegyű szám első jegyét rögzítve $5! = 120$ -féle számot kapunk. $640 = 5 \cdot 120 + 40$ , azaz a még lehetséges jegyek közül a hatodikkal ‐ a $9$ -essel ‐ kezdődők között lesz a $640$ -edik. A még megmaradt 1, 2, 4, 6, 7 számokból álló ötjegyű számok között kell megtalálnunk a $40$ -ediket.
Az első jegyet rögzítve $4! = 24$ -féle számot kaphatunk. $40 = 1 \cdot 24 + 16$ , tehát a még felhasználható számjegyek közül a második, a $2$ -es áll a következő helyen. A továbbiakban az 1, 4, 6, 7 számjegyekből álló négyjegyű számok között kell megkeresnünk a $16$ -odikat. Tovább haladva $16 = 2 \cdot 3! + 4$ , így most a fenti négy jegy közül a harmadikat kell választanunk, és az 1, 4, 7 számokból álló háromjegyű számok közül van szükségünk a $4$ -edikre. $4 = 2 \cdot 2!$ , vagyis a $4$ -edik szám első jegye a fenti három jegy közül a második, a $4$ -es, az utolsó két jegy pedig $7$ és $1$ .
A keresett szám tehát 358 926 471.

Megjegyzés. Ha az első kilenc pozitív egész mindegyikét pontosan egyszer tartalmazó számok halmazát

H

-val jelöljük, akkor a megoldásban lényegében arra van szükség, hogy összeszámoljuk, hogy az

a = a_{9} a_{8} ... a_{1}

H

-beli számra mennyi az

a

-nál kisebb

H

-beli számok száma. Ezek a számok aszerint csoportosíthatók, hogy melyik az a legelső helyiérték, ahol kisebb jegy áll bennük, mint

a

-ban. Ha ez az

i

-edik, akkor erre a helyre beírhatjuk az összes olyan,

a_{i}

-nél kisebb számot, amit az

i

-ediknél nagyobb helyiértékeken még nem használtunk fel, a további

i - 1

helyen pedig a megmaradt

(i - 1)

darab szám valamennyi

(i - 1)!

darab sorrendje lehetséges.
Ha tehát az első

9

természetes szám egy

a_{9} a_{8} ... a_{1}

sorrendjében

k_{i}

jelöli az

i

-nél kisebb indexű ‐ azaz a fenti sorban

a_{i}

mögött álló ‐,

a_{i}

-nél kisebb számok számát, akkor az

a

-nál kisebb

H

-beli számok száma

\begin{matrix} k_{9} \cdot 8! + k_{8} \cdot 7! + ... + k_{3} \cdot 2! + k_{2} \cdot 1! (k_{1} = 0) \end{matrix}

(1)

Arra a

H

-beli

a

számra van szükségünk, amelyre a fenti érték éppen 99 999. Ismeretes, hogy minden természetes szám felírható a fenti alakban, "faktoriális számrendszerben'', azaz minden

t

természetes számra van olyan

n

nem negatív egész, hogy

\begin{matrix} t = f_{n} \cdot n! + f_{n - 1} \cdot (n - 1)! + ... + f_{2} \cdot 2! + f_{2} \cdot 2! + f_{1} \cdot 1!,. \end{matrix}

(2)

Ha még azt is föltesszük, hogy

f_{i} ≦ i

, akkor a fenti felírás egyértelmű. Mivel pedig (1)-ben

k_{i} ≦ i - 1

, hiszen

a_{i}

mögött a sorban összesen

(i - 1)

darab szám áll, ezért a 99 999 szám (2) alakjában az együtthatók éppen a

k_{i}

számok. A megoldásban lényegében a 100 000 (2) alakban történő felírására került sor.

\begin{matrix} 99 999 = 2 \cdot 8! + 3 \cdot 7! + 5 \cdot 6! + 5 \cdot 5! + 1 \cdot 4! + 2 \cdot 3! + 1 \cdot 2! + 1 \cdot 1!, \end{matrix}

azaz

k_{9} = 2

k_{8} = 3

k_{7} = 5

k_{6} = 5

k_{5} = 1

k_{4} = 2

k_{3} = 1

és

k_{2} = 1

. Az első kilenc pozitív egésznek az

a_{9} a_{8} ... a_{1}

permutációja lesz a keresett szám, amelyben minden

1

-nél nagyobb

i

-re

a_{i}

mögött éppen

k_{i}

darab

a_{i}

-nál kisebb szám áll a sorban.
Nyilvánvaló, hogy ha az

i

-nél nagyobb indexű jegyeket már megkaptuk, akkor

a_{i}

a megmaradt

i

darab szám közül nagyság szerint a

(k_{i} + 1)

-edik lesz. Így nyerjük rendre a keresett jegyeket:

a_{9} = 3

a_{8} = 5

a_{7} = 8

a_{6} = 9

a_{5} = 2

a_{4} = 6

a_{3} = 4

a_{2} = 7

. Az egyetlen kimaradt jegy, az

1

-es lesz tehát

a_{1}

, vagyis a keresett szám

\begin{matrix} 358 926 471. \end{matrix}