Kezdőlap


Feladat:	615. matematika feladat	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Almási L. , Bártfai P. , Beliczky G. , Biczó G. , Csiszár I. , Eördögh L. , Goldstein R. , Grätzer Gy. , Jónás J. , Kálmán Gy. , Kiss P. , Lackner Györgyi , Makkai M. , Pintér L. , Plichta J. , Quittner P. , Rázga T. , Rozsondai Z. , Siklósi P. , Szentai E. , Takács J. , Tomor B. , Vértes P. , Vigassy J. , Zawadowski Alfréd , Zsombok Z.
Füzet:	1955/január, 21 - 22. oldal		PDF \| MathML
Témakör(ök):	Binomiális együtthatók, Kombinációk, Oszthatóság, Feladat
Hivatkozás(ok):	Feladatok: 1954/május: 615. 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:
a)

\begin{matrix} (\binom{2 a}{a}) = \frac{2 a (2 a - 1) ... (a + 1)}{1 \cdot 2 ... a} = \frac{2 a}{a} \cdot \frac{(2 a - 1) ... (a + 1)}{1 \cdot 2 ... (a - 1)} = 2 (\binom{2 a - 1}{a - 1}) \end{matrix}

Ezzel tételünk első része nyilvánvalóvá vált.
b)

a

és

a + 1

relatív prímek, azért ha

a (\binom{2 a}{a})

osztható

(a + 1)

-gyel, akkor

(\binom{2 a}{a})

is osztható vele, de

\begin{matrix} a (\binom{2 a}{a}) = a \frac{2 a (2 a - 1) ... (a + 2) (a + 1)}{1 \cdot 2 ... (a - 1)} = (a + 1) \frac{2 a (2 a - 1) ... (a + 2)}{1 \cdot 2 ... a - 1} = \\ = (a + 1) (\binom{2 a}{a - 1}) . \end{matrix}

\begin{matrix} (\binom{2 a}{a}) = \frac{2 a (2 a - 1) ... (a + 2) (a + 1)}{1 \cdot 2 ... (a - 1) a} = \\ = \frac{2 (2 a - 1)}{a} \cdot \frac{(2 a - 2) ... (a + 1) a}{1 \cdot 2 ... (a - 1)} = \frac{(2 a - 1)}{a} (\binom{2 a - 2}{a - 1}) . \end{matrix}

De az előbb bebizonyított tétel alapján

(\binom{2 a - 2}{a - 1}) :

a

egész szám, és így

(\binom{2 a}{a})

osztható

(2 a - 1)

-gyel.

II. megoldás:

(\binom{2 a}{a}) = C_{2 a}^{a}

, vagyis

(\binom{2 a}{a})

jelenti a

2 a

elemből kiválasztható

a

elemű csoportok számát. A kiválasztás módja sokféle lehet.
a) Valahányszor egy

a

elemű csoportot kiválasztunk, visszamarad egy

a

elemű csoport. Ilyen módon az összes lehetséges

a

elemű csoportokat párosával kapjuk, számuk tehát 2-vel osztható.
b)

2 a

elemből kiválasztható

(\binom{2 a}{a})

számú

a

elemű csoport mindegyikében jelöljünk meg egy tetszőleges elemet. Ilyen módon mindegyik csoportból

a

számú új csoportot készíthetünk. Összesen tehát lesz

a (\binom{2 a}{a})

csoportunk.
De az összes ilyen csoportokhoz, mégpedig mindegyikhez csak egyszer, a következőképpen is juthatunk. Először a

2 a

elemből kiválasztjuk az összes lehetséges

(a - 1)

elemű csoportot. Ezeknek száma

(\binom{2 a}{a - 1});

azután mindegyik csoportból

(a + 1)

számú új csoportot alkotunk azáltal, hogy megjelölve hozzáírunk mindegyik csoporthoz egy-egy elemet az illető csoportban elő nem forduló

(a + 1)

számú elem közül. Így összesen

(a + 1) (\binom{2 a}{a - 1})

csoportot nyerünk.
Tehát

\begin{matrix} a (\binom{2 a}{a}) = (a + 1) (\binom{2 a}{a - 1}) \end{matrix}

és mivel

a

és

a + 1

relatív prím,

(\binom{2 a}{a})

osztható

(a + 1)

-gyel.
c) A

(\binom{2 a}{a})

számú

a

elemű csoport mindegyikében jelöljünk meg két elemet különböző jellel.
Az első jelölés történhetik

a

-féléképpen, a második jelölés

(a - 1)

-féleképpen, tehát mindegyik csoportból

a (a - 1)

számú új csoportot kapunk, és így lesz összesen

a (a - 1) (\binom{2 a}{a})

számú csoport,

2

‐

2

különböző jellel megjelölt elemmel.
E kettős jelölésű csoportok előállítása azonban a következőképpen is történhetik:
A

2 a

elem egy elemét megjelöljük az első jellel. A többi

(2 a - 1)

élem egyikét a másik jellel. E jelölések

2 a (2 a - 1)

-féleképpen történhetnek. Végül a két megjelölt elemhez hozzácsatolunk a jelöletlen

(2 a - 2)

elemből minden lehetséges módon kiválasztott

(a - 2)

elemet. Utóbbi kiválasztás

(\binom{2 a - 2}{a - 2})

-féleképpen történhetik. Ilyen módon is eljutunk az összes kettős jelölésű csoporthoz és mindegyikhez csak egyszer, tehát az így nyert csoportok száma megegyezik az első módon nyert csoportok számával, vagyis

\begin{matrix} a (a - 1) (\binom{2 a}{a}) = 2 a (2 a - 1) (\binom{2 a - 2}{a - 2}), \end{matrix}

azaz

\begin{matrix} (a - 1) (\binom{2 a}{a}) = 2 (2 a - 1) (\binom{2 a - 2}{a - 2}) . \end{matrix}

Mivel

(a - 1)

és

(2 a - 1)

egymáshoz relatív prim számok, azért

(\binom{2 a}{a})

osztható

(2 a - 1)

-gyel.

Zawadowski Alfréd (Bp. 1., Petőfi g. 1V. o. t.)

Megjegyzés: Látható, hogy az itt követett gondolatmenet az I. megoldásával teljesen párhuzamosan halad, azzal az eltéréssel, hogy a felhasznált oszthatósági viszonyokra algebrai átalakítások helyett kombinatorikus meggondolásokból következtet.