Kezdőlap


Feladat:	1404. matematika feladat	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Bárány Imre , Belső Béla , Csirmaz László
Füzet:	1966/január, 24 - 26. oldal		PDF \| MathML
Témakör(ök):	Variációk, Partíciós problémák, Számelméleti függvények, Feladat
Hivatkozás(ok):	Feladatok: 1965/szeptember: 1404. matematika feladat

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. Az $n = 1$ esetre az állítás szerint 1 összeg‐felbontás létezik. Viszont 1-et nem lehet felbontani természetes számokra. Ez azt mutatja, hogy az egytagú összeget, magát az $n$ számot is előállításnak kell tekintenünk, pl. $n = 2$ összes előállításainak a száma úgy lesz $2^{2 - 1} = 2$ , ha ezeket vesszük: $1 + 1$ és 2.
Tüntessük fel a számegyenesen a 0-t és az első $n$ természetes számot. Az $n$ szám minden szóban forgó előállításának megfelel a kijelölt pontok közül egy olyan kiválasztás, amely tartalmazza a 0-t, az $n$ -t és a többi $n - 1$ pont közül tetszés szerintieket (akár mindet, akár esetleg egyet sem). Megfordítva, minden ilyen kiválasztásból leolvasható $n$ -nek egy a követelményt kielégítő előállítása. Pl. az 1-es és az $n - 1$ -es osztáspont kiválasztása (a 0-n és $n$ -en kívül) különbözőnek számít, mihelyt $n > 2$ , mert az $1 + (n - 1)$ és az $(n - 1) + 1$ felbontásokat különbözőknek tekintjük.
Így azt kell meghatároznunk, hányféleképpen lehet az 1, 2, $...$ , $n - 1$ pontból tetszés szerinti számút osztópontnak venni. Egy‐egy kiválasztást úgy adhatunk meg, hogy az 1-es, 2-es, $...$ , $n - 1$ -es ponthoz rendre csillagot, ill. mínusz jelet írunk, aszerint, hogy kiválasztottuk-e osztópontnak vagy nem. Így minden pontban 2 lehetőségünk van, összesen tehát $2^{n - 1}$ , mert a megjelölések egymástól függetlenek, a lehetőségek száma lépésről lépésre megkétszereződik. Eszerint a szóban forgó előállítások száma valóban $2^{n - 1}$ .
Pl. $n = 3$ és 4 esetén a 2, ill. 3 belső pont megjelölésének lehetőségei:

\begin{matrix} \begin{matrix} ^{*},^{*};^{*}, -; & -,^{*}; & -, -; \\ ^{*},^{*},^{*};^{*},^{*}, -; & ^{*}, -,^{*};^{*}, -, -; & -,^{*},^{*}; \end{matrix} \end{matrix}

és az utóbbi esetben a megfelelő előállítások tagjai:

\begin{matrix} 1,1,1,1; 1,1,2; 1,2,1; 1,3; 2,1,1; 2,2; 3,1; 4. \end{matrix}

Belső Béla (Győr, Benedek‐rendi Czuczor Gergely g. IV. o. t.)

Megjegyzés. A meggondolást továbbfejlesztve külön‐külön megszámlálhatjuk, hány felbontás 1-tagú, hány 2-tagú,

...

, hány

n

-tagú.

n

tagú az, amelyben minden belső pont

^{*}

jelet kapott, 1 tagú a csupa mínusz‐jeles, ilyen felbontás tehát 1‐1 van. 2-tagúak azok, amelyekben egyetlen helyen áll

^{*}

, számuk nyilvánvalóan

n - 1

, ugyanennyi az

n - 1

tagúaké is, amelyekben egyetlen helyen áll mínuszjel. A

k

tagúak száma (ahol

1 \leq k \leq n

) az 1362. feladatban¹ alkalmazott meggondoláshoz hasonlóan

\begin{matrix} \frac{(n - 1) \cdot (n - 2) \cdot ... \cdot (n - k)}{k \cdot (k - 1) \cdot ... \cdot 2 \cdot 1} . \end{matrix}

(1)

II. megoldás. Jelöljük az

n

szám szóba jövő előállításainak számát

f (n)

-nel. Az I. megoldásban láttuk, hogy

f (1) = 1 = 2^{0}

, és

f (2) = 2 = 2^{1}

. Elég még megmutatnunk, hogy a számot eggyel növelve a felbontások száma megkétszereződik:

f (n + 1) = 2 \cdot f (n)

. Ebből

f (n) = 2^{n - 1}

, a feladat állítása nyilvánvalóan következik.
Gondoljuk magunk elé az

n

szám összes szóban forgó előállításait. Ezek mindegyikéből két módon képezünk egy‐egy előállítást az

n + 1

számra:

α

mód: az utolsó tagot 1-gyel növeljük,

β

mód: az előállítás végére egy

+ 1

-es új tagot csatolunk.
Megmutatjuk, hogy az

n

szám két különböző előállításából,

E_{1}

-ből és

E_{2}

-ből az

n + 1

számra képezett

E_{1} α

E_{1} β

E_{2} α

E_{2} β

előállítások mind különbözők, így

n + 1

előállításainak száma legalább 2-szer akkora, mint

n

előállításaié, vagyis

f (n + 1)

nem kisebb

2 \cdot f (n)

-nél.

E_{1} α

és

E_{2} α

különbözők, mert ha azonosak volnának, akkor az utolsó tagjuknak 1-gyel ‐ 1-gyel való csökkentésével az

n

számra kapnánk két azonos előállítást. Ugyanígy

E_{1} β

és

E_{2} β

is különbözők. Végül nem lehet azonos

E_{i} α

és

E_{j} β

sem ‐ ahol

i

is,

j

is az 1 és 2 indexek bármelyike ‐, mert az utóbbinak utolsó tagja 1, az előbbié pedig legalább 2.
Másrészt nincs

n + 1

-nek olyan előállítása, amelyet a fenti módon ne kaptunk volna meg. Mert ha

n + 1

egy megfelelő előállításának,

F

-nek, utolsó tagja nagyobb 1-nél, akkor abból 1-et levonva, ha pedig az utolsó tag 1, akkor azt elhagyva

n

-re kapunk egy összeg‐előállítást, ezt a feltevés szerint fent felhasználtuk, és így belőle az

α

, ill.

β

módon eljutottunk

F

-hez. Így

f (n + 1)

nem is nagyobb

2 \cdot f (n)

-nél, tehát egyenlő vele. ‐ Ezzel a bizonyítást befejeztük.

Bárány Imre (Budapest‐Mátyásföld, Corvin M. g. IV. o. t.)

III. megoldás. Ismét az

f (n + 1) = 2 \cdot f (n)

egyenlőséget bizonyítjuk be. Csoportosítsuk az

n + 1

szám felbontásait első tagjuk értéke szerint. Az

n

taggal kezdődő felbontások száma

f (n + 1 - a)

, ahányféleképpen az

a

-t

n + 1

-re kiegészítő

n + 1 - a

számot előállíthatjuk. Végigmenve a szóba jövő

a = 1

, 2,

...

n

n + 1

értékeken, minden felbontást egyszer és csak egyszer veszünk számba, ezért

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

az utolsó tag azt fejezi ki, hogy

n + 1

-nek 1 egytagú felbontása is van.
Ugyanígy adódik

n

helyén

n - 1

-et véve az

\begin{matrix} f (n) = f (n - 1) + f (n - 2) + ... + f (1) + 1 \end{matrix}

egyenlőség. Ezt az előbbiből kivonva

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

Csirmaz László (Budapest, I. István g. I. o. t.)

¹Lásd K. M. L. 31 (1965) 73. o. ‐ Az ilyen alakú kifejezésekről bővebbet olvashat az érdeklődő pl. a következő helyen: Kürschák J.‐Hajós Gy.‐Neukomm Gy.‐Surányi J.: Matematikai Versenytételek I. rész 3. kiadás, Tankönyvkiadó, Bp., 1964. 26‐28. o.