Kezdőlap


Feladat:	1960. évi Matematika OKTV I. forduló 1. feladata	Korcsoport: 18-	Nehézségi fok: átlagos
Füzet:	1960/szeptember, 8 - 10. oldal		PDF \| MathML
Témakör(ök):	Variációk, Kombinációk, Mértani sorozat, Rekurzív eljárások, OKTV
Hivatkozás(ok):	Feladatok: 1960/szeptember: 1960. évi Matematika OKTV I. forduló 1. feladata

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.

Előzetes megjegyzés. Számos versenyző azt határozta meg, hány az 1-es számjegyet tartalmazó szám ¹, van külön-külön az egy-, a két-, $...$ , a hatjegyű számok között, és a feladat kérdésére a választ e hat szám összegével adta meg. Ehhez hasonló, de egyszerűbb megoldás a következő.

I. megoldás: Legfeljebb hatjegyűek azok a számok, amelyek leírásához egy, vagy két, vagy

...

, vagy hat számjegy szükséges, más szóval hat számjegy elegendő. Mindezek pontosan hat jeggyel is írhatók, ha a 0 jegyet a többi jegyektől meg nem különböztetve kezdő számjegyként is megengedjük, és minden legfeljebb öt jeggyel írt szám elé annyi 0-t gondolunk írva, hogy jegyeinek száma hat legyen.
Jelöljük az 1-es jegyet tartalmazó legfeljebb

n

-jegyű számok számát

F_{n}

-nel. Így nyilván

F_{1} = 1

, mert az egyjegyű számok közül egy felel meg: az 1, és feladatunk

F_{6}

megállapítása. Tegyük fel, hogy

F_{n}

-et már ismerjük; ekkor

F_{n + 1}

-et a következő meggondolással kaphatjuk meg. Csoportosítsuk az 1-es jegyet tartalmazó legfeljebb

n + 1

jegyű számokat kezdő jegyük szerint. Az 1-essel kezdődők száma

10^{n}

, mert bennük a további

n

helyre tetszés szerint írhatunk jegyeket, mindegyikre a 10-féle jegy mindegyikét, egymástól függetlenül. ² A

0, 2, 3, 4, ...

9

-essel kezdődő

n + 1

jegyűek száma pedig minden csoportban

F_{n}

, hiszen ezeknek a hátralevő

n

jegyű részükben kell 1-est tartalmazniuk. Ezzel valamennyi megfelelő

n + 1

-jegyű számot figyelembe vettük, mindegyiket pontosan egyszer, tehát

\begin{matrix} F_{n + 1} = 10^{n} + 9 \cdot F_{n} . \end{matrix}

Ezzel ún. rekurzív³ képletet kaptunk

F_{n}

kiszámítására. Így

F_{2} = 10 + 9 \cdot F_{1} = 19

F_{3} = 100 + 9 \cdot 19 = 271

F_{4} = 1 000 + 9 \cdot 271 = 3 439

F_{5} = 10 000 + 9 \cdot 3 439 =

= 40 951

, végül

F_{6} = 100 000 + 9 \cdot 40 951 = 468 559

. ‐ Ezzel a kérdésre a választ megadtuk.

II. megoldás: Csoportosítsuk a szóban forgó számokat aszerint, hogy a legértékesebb helyen álló, más szóval balról első 1-es jegyük rendre az egyes, a tízes, a százas,

...

, a százezres helyen áll. Így hat csoport jön létre és minden számunk pontosan egy csoportba jut. Az előállításban az említett 1-es helyének kivételével mind az öt további helyet úgy kell betöltenünk, hogy az említett 1-es után bármely jegy állhat, előtte pedig bármely 1-től különböző jegy.
Az első csoport számainak az egyes értékű, vagyis balról az utolsó jegye 1-es, több 1-est nem tartalmaznak. Bennük a tízes értékű helyre az 1-estől különböző 9 jegy mindegyikét figyelembe kell vennünk. Bármelyiket véve tízesnek a százas értékű jegy ismét 9-féleképpen töltendő be, így a tízes és százas értékű helyeken

9 \cdot 9

-féle betöltés lehetséges. Ugyanígy a további három hely is 9-féleképpen tölthető be, tehát e csoport

9^{5}

számot tartalmaz.
A második csoportba tartozó számok tízes értékű jegye 1, a mögötte álló egyes értékű helyre mind a 10 jegyet írhatjuk, az előtte álló négy jegyet pedig ismét 9-féleképpen választhatjuk meg, így ebben a csoportban

9^{4} \cdot 10

számot kapunk. ‐ Tovább haladva csoportról csoportra eggyel-eggyel több hely tölthető be 9 helyett 10-féleképpen, így az 1-est tartalmazó számok száma a hat csoportból összesen:

\begin{matrix} N = 9^{5} + 9^{4} \cdot 10 + 9^{3} \cdot 10^{2} + 9^{2} \cdot 10^{3} + 9 \cdot 10^{4} + 10^{5} . \end{matrix}

Vegyük észre, hogy e hat tagú összeg tagjai mértani sorozatot alkotnak

10 / 9

hányadossal, így az összegképlettel

N = 468 559

III. megoldás: Kombinatorikai ismeretekre és a binomiális tételre támaszkodva a kérdéses számok számát az előzőkhöz hasonlóan a bennük fellépő 1-esek száma szerint csoportosított előállításuk alapján is megkaphatjuk, a számokat itt is hatjegyűre kiegészített alakjukban állítva elő. Az egyetlen 1-est tartalmazó számok 1-esét a 6 hely mindegyikén kell figyelembe vennünk, a többi 5 helyen pedig a további 9 jegyet minden lehetséges módon, tehát az ilyen számok száma

6 \cdot 9^{5}

. A pontosan két, három,

...

, hat 1-est tartalmazó számok 1-eseinek helyét rendre

\begin{matrix} (\binom{6}{2}), (\binom{6}{3}), (\binom{6}{4}), (\binom{6}{5}), (\binom{6}{6}) = 1 \end{matrix}

féleképpen választhatjuk meg és minden egyes megválasztás után a többi

4, 3, 2, 1

helyet

9^{4}, 9^{3}, 9^{2},9

-féleképpen tölthetjük be, ill. az utolsó esetben készen is vagyunk, nincs további betöltendő hely. Ezek alapján a keresett szám

\begin{matrix} N = 6 \cdot 9^{5} + (\binom{6}{2}) \cdot 9^{4} + (\binom{6}{3}) \cdot 9^{3} + (\binom{6}{4}) \cdot 9^{2} + (\binom{6}{5}) \cdot 9 + 1. \end{matrix}

Vegyük észre, hogy

N

ezen kifejezéséhez első tagként

9^{6}

-ot adva al

{(9 + 1)}^{6}

hatvány kifejtését kapjuk. Ennek alapján

\begin{matrix} N = {(9 + 1)}^{6} - 9^{6} = 10^{6} - 9^{6} = 1 000 000 - 531 441 = 468 559. \end{matrix}

IV. megoldás: A legutóbbi eredményhez egyszerűbben így juthatunk el. Tekintsük valamennyi hatjegyű és hatjegyűen írható számot, beleértve 0-t is a

000 000

alakban, ezek száma

999 999 + 1

, másképpen

10^{6}

, mert mind a hat helyre mind a 10 jegyet egymástól függetlenül sorra vesszük. A követelménynek megfelelő számokhoz úgy jutunk, ha elhagyjuk az 1-es jegyet nem tartalmazó számokat, más szóval mindazokat, amelyekben a 6 hely mindegyikén 1-estől különböző jegy áll. Ezek száma

9^{6}

, tehát

N = 10^{6} - 9^{6}

. (Eközben a 0-t is elhagytuk.)

Megjegyzések: 1. A II. megoldásban kapott összeget

10 - 9

alakban 1-gyel szorozva a III. megoldásban kapott

10^{6} - 9^{6}

alakra hozhatjuk.
2. A IV. megoldásban azt használtuk fel, hogy valamennyi legfeljebb hatjegyű természetes számnak összessége, ill. az 1-es nem tartalmazása miatt elhagyandó számok összessége ‐ a 0-t mindkét összességbe beszámítva ‐ azonos a 10-, ill. 9-féle számjegy ismétléses 6-odosztályú variációival.
3. Általánosítások: a) Egyik megoldásban sem használtuk ki, hogy a kitüntetett számjegy éppen az 1-es. Eszerint azoknak a legfeljebb hatjegyű természetes számoknak a száma, amelyekben egy adott tetszőleges (0-tól különböző) jegy előfordul:

468 559

.
b) Mindegyik megoldás gondolatmenete akkor is alkalmazható, ha az olyan legfeljebb

n

-jegyű természetes számok számát keressük, amelyekben egy megadott (0-tól különböző) számjegy előfordul. Ezek száma (pl. a IV. megoldásból)

10^{n} - 9^{n}

.
c) Ugyanezt a kérdést egy tetszőleges

k

alapú számrendszerben vizsgálva ‐ ahol

k

az 1-nél nagyobb természetes szám, és a figyelembe vett számjegy nem a 0, ‐ a követelménynek eleget tevő számok száma

\begin{matrix} k^{n} - {(k - 1)}^{n} . \end{matrix}

¹A feladat tartalmának megfelelően elég ,,természetes szám'' helyett röviden ,,szám''-ot mondanunk.

²Másképpen: e számok $100 ... 0$ -tól $199 ... 9$ -ig terjednek, ahol a 0-ok, ill. 9-esek száma $n$ , ‐ így számuk $199 ... 9 - 9 ... 99 = 100 ... 0 = 10^{n}$ .

³Szó szerint: visszafutó; az előzőre támaszkodó.