Kezdőlap


Feladat:	Pontversenyen kívüli P.358	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Alberti Gábor , Megyesi Gábor , Sigray István , Törőcsik Jenő , Wágner Péter Antal
Füzet:	1983/január, 18 - 20. oldal		PDF \| MathML
Témakör(ök):	Kombinatorika, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1982/január: Pontversenyen kívüli P.358

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.

I. megoldás. Legyenek a gyűrűk nagyság szerint $g_{1}$ , $g_{2}$ , $...$ , $g_{9}$ , a legkisebb gyűrű $g_{1}$ , a legnagyobb $g_{9}$ .
Nézzük, hányféleképpen lehet pontosan $k$ gyűrűt elhelyezni az oszlopon. Rendeljük hozzá minden ilyen gyűrűelhelyezéshez a gyűrűk sorszámát alulról felfelé haladva leírt sorrendben. Így egy $k$ jegyű számot kapunk. Az első jegy az először ledobott gyűrű sorszáma lesz. Ez a gyűrű nem lehet $g_{1}$ , $g_{2}$ , $...$ , $g_{k - 1}$ , hiszen ezek közül egyik sem esik lejjebb a $(k - 1)$ -edik pozíciónál, és utána már csak legfeljebb $(k - 2)$ -t, így összesen $k - 1$ gyűrűt tudnánk az oszlopon elhelyezni. Az első jegy tehát nagyobb, mint $k - 1$ .
Általában az $i$ -edik jegy az $i$ -ediknek ledobott gyűrű sorszáma lesz, ez a gyűrű nem lehet a $g_{1}$ , $g_{2}$ , $...$ , $g_{k - i}$ gyűrűk egyike sem, hiszen ez esetben csak további $k - i - 1$ gyűrűnek maradna hely. [ $g_{k - i}$ a $(k - i)$ -edik pozíciónál fennakad.] Az $i$ -edik jegy tehát nagyobb, mint $k - i$ .

Másrészt a

k

jegyű szám minden jegye különböző, mert egy gyűrű sem szerepel kétszer. Azt kaptuk tehát, hogy a

k

gyűrű elrendezésének egy olyan

k

jegyű szám felel meg, amelynek minden jegye különböző és

i

-edik jegye

(1 \leq i \leq k)

nagyobb, mint

k - i

. Nyilvánvaló másrészt, hogy ha egy

k

jegyű számnak megvannak ezek a tulajdonságai, akkor a neki megfelelő számú gyűrűket sorra rádobhatjuk az oszlopra, egyik sem fog túl magasan fennakadni. (Az első után legalább

k - 1

hely, a második után legalább

k - 2

, általában az

i

-edik után legalább

k - i

hely marad meg.)
A gyűrű‐elhelyezések és az ilyen tulajdonságú

k

jegyű számok között kölcsönös megfeleltetést hoztunk tehát létre.
Azt kell most már kiszámolnunk, hogy hány olyan csupa különböző jegyből álló

k

jegyű szám van, amelynek

1 \leq i \leq k

-ra az

i

-edik jegye nagyobb, mint

k - i

.
Az ilyen számok első jegye a

k

k + 1

...

, 9 számjegyek valamelyike lesz, ez

10 - k

lehetőség. Rögzítsük az első jegyet. Ekkor a második jegy a

k - 1

k

k + 1

...

, 9 számjegyek valamelyike lesz, de az első jeggyel nem egyezhet meg. Így most is

10 - k

lehetőség van. Bármi is tehát az első jegy, a második

10 - k

különböző módon, választható meg a feltételeknek megfelelően. Tegyük fel általában, hogy az első

i

számjegyet már megválasztottuk a feltételeknek megfelelően: mind különböző és az első jegy a

k

...

, 9, a második a

k - 1

k

...

, 9 stb., az

i

-edik a

k - i + 1

k - i + 2

...

k

...

, 9 számjegyek közül való. Az

(i + 1)

-edik jegyet a

k - i

k - i + 1

...

k

...

, 9 számok közül kell választani, hiszen a feltétel szerint az

(i + 1)

-edik jegy nagyobb, mint

k - i - 1

. Ez tehát

10 - (k - i)

lehetőség, de ezek között közte van az első

i

jegy is, ami most már nem választható. Így akárhogyan is rögzítettük az első

i

jegyet a feltételnek megfelelően, az

(i + 1)

-edik jegyet a feltételnek megfelelően

10 - k

különböző módon választhatjuk meg. Ebből következik, hogy az első jegy

10 - k

, az első két jegy

{(10 - k)}^{2}

stb., s végül a

k

jegy

{(10 - k)}^{k}

különböző módon választható.
Azt kaptuk tehát, hogy

{(10 - k)}^{k}

olyan

k

-jegyű szám van, amelynek az

i

-edik jegye nagyobb, mint

k - i

, ha

1 \leq i \leq k

. Ugyanennyi tehát azoknak a gyűrűelhelyezéseknek a száma is, ahol pontosan

k

gyűrűt helyeztünk el. Az összes gyűrűelhelyezések számát tehát úgy kapjuk, ha

{(10 - k)}^{k}

értékét

k = 0

, 1,

...

, 9-re összeadjuk:

10^{0} + 9^{1} + 8^{2} + 7^{3} + 6^{4} + 5^{5} + 4^{6} + 3^{7} + 2^{8} + 1^{9} = 11 378

. Ha

n

gyűrű van, akkor a fenti gondolatmenet azt adja, hogy az összes gyűrű elhelyezések száma

R_{n} = {(n + 1)}^{0} + n^{1} + (n - 1^{2} + ... + {(n - k)}^{k + 1} + ... + 2^{n - 1} + 1^{n}

, például

R_{0} = 1

R_{1} = 2

R_{2} = 4

R_{3} = 9

R_{4} = 23

Törőcsik Jenő (Budapest, Fazekas M. Gyak. Gimn., III. o. t.)

II. megoldás. A feladatot általánosabban oldjuk meg, 9 gyűrű helyett

n

gyűrűre. Legyen az

n

gyűrű nagyság szerint rendre

g_{1}

g_{2}

...

g_{n}

, a legnagyobb

g_{1}

, a legkisebb

g_{n}

. Jelölje

f (n, k)

azt, hogy hányféleképp tudunk pontosan

k

gyűrűt az oszlopra dobni,

R_{n}

pedig a keresett gyűrűelhelyezések számát. Nyilván

\begin{matrix} R_{n} = f (n, n) + f (n, n - 1) + ... + f (n, 0) . \end{matrix}

(1)

Nézzük tehát, mennyi

f (n, k)

értéke, azaz hányféleképpen lehet

k

gyűrűt az oszlopra dobni? Nyilvánvaló, hogy ha a

g_{n}

gyűrűt az első

k - 1

lépés valamelyikében az oszlopra dobom, akkor utána több már nem fér rá, hiszen

g_{n}

mindenképp fennakad az oszlop tetején.

k

gyűrűt tehát csak úgy helyezhetek el, ha az első

k - 1

gyűrűt

g_{1}

g_{2}

...

g_{n - 1}

közül választom, majd a

k

-adiknak a még rá nem dobott gyűrűk közül egy tetszőlegest választok. Az első

k - 1

gyűrű a legfelső pozíciót szabadon kell hogy hagyja, különben nincs hely a

k

-adik gyűrűnek. Az első

k - 1

dobásnál tehát ugyanaz a helyzet, mintha a

g_{n}

gyűrű és a legfelső pozíció nem létezne:

k - 1

gyűrűt kell elhelyeznem az oszlopon,

n - 1

gyűrű közül válogathatok, és az oszlopon

n - 1

hely van. Ezt nyilván

f (n - 1, k - 1)

különböző módon tehetem meg, az első

k - 1

gyűrűt tehát ugyanennyiféleképpen:

f (n - 1, k - 1)

különböző módon választhatom, a

k

-adikat az első

k - 1

ilyen választása után mindig

(n - k + 1)

-féleképp választhatom,

k

gyűrű elhelyezésére tehát

f (n - 1, k - 1) \cdot (n - k + 1)

különböző lehetőség van. (Nyilvánvaló, hogy minden lehetőséget számbavettünk, és minden lehetőséget pontosan egyszer vettünk számba. Végül az is nyilvánvaló, hogy minden számba vett lehetőség valóban

k

gyűrűnek egy jó elhelyezését adja.)
Azt kapjuk, hogy

\begin{matrix} f (n, k) = f (n - 1, k - 1) \cdot (n - k + 1) . \end{matrix}

(2)

Tudjuk, hogy

f (n, 0) = 1

minden

n

természetes számra; ebből és (1)-ből teljes indukcióval könnyen adódik, hogy

f (n, k) = {(n - k + 1)}^{k}

. Ez ugyanis

k = 0

esetén igaz és ha tudjuk, hogy minden

n

-re

f (n, k - 1) = {[n - (k - 1) + 1]}^{k - 1}

, akkor (1)-ből

f (n, k) = f (n - 1, k - 1) \cdot (n - k + 1) = {[n - 1 - (k - 1) + 1]}^{k - 1} \cdot (n - k + 1) =

= {(n - k + 1)}^{k}

. Azt kaptuk tehát, hogy a gyűrűket

\begin{matrix} R_{n} = \sum_{k = 0}^{n} {(n + 1 - k)}^{k} \end{matrix}

különböző módon lehet az oszlopra dobni. A feladat esetében

\begin{matrix} R_{9} = 10^{0} + 9^{1} + 8^{2} + 7^{3} + 6^{4} + 5^{5} + 4^{6} + 3^{7} + 2^{8} + 1 = 11 378. \end{matrix}

Megyesi Gábor (Szeged, Ságvári E. Gyak. Gimn., I. o. t.)