Kezdőlap


Feladat:	B.4178	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	2009/november, 479 - 480. oldal		PDF \| MathML
Témakör(ök):	Feladat, Binomiális együtthatók, Legnagyobb közös osztó
Hivatkozás(ok):	Feladatok: 2009/április: B.4178

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. Ha $n \leq k$ , akkor az adott számok között szerepel $(\binom{k}{k}) = 1$ , ezért az állítás nyilvánvaló.
Tudjuk, hogy minden $0 \leq ℓ \leq m$ egészre $(\binom{m}{ℓ}) + (\binom{m}{ℓ + 1}) = (\binom{m + 1}{ℓ + 1})$ . Ezért

\begin{matrix} (\binom{m}{ℓ}) = (\binom{m + 1}{ℓ + 1}) - (\binom{m}{ℓ + 1}), \end{matrix}

vagyis

(\binom{m}{ℓ + 1})

és

(\binom{m + 1}{ℓ + 1})

minden közös osztója egyúttal

(\binom{m}{ℓ})

-nek is osztója.
Legyen az

\begin{matrix} (\binom{n}{k}), (\binom{n + 1}{k}), ..., (\binom{n + k}{k}) \end{matrix}

számok legnagyobb közös osztója

d

. Ekkor az előző bekezdésben leírtakat az

ℓ + 1 = k

és

m = n, n + 1, ..., n + k - 1

esetekben alkalmazva kapjuk, hogy

d

osztója az

\begin{matrix} (\binom{n}{k - 1}), (\binom{n + 1}{k - 1}), ..., (\binom{n + k - 1}{k - 1}) \end{matrix}

számok mindegyikének. Ismét alkalmazzuk az oszthatóságra vonatkozó állításunkat, most az

ℓ + 1 = k - 1

és

m = n, n + 1, ..., n + k - 2

számokra. Azt kapjuk, hogy

d

osztója az

\begin{matrix} (\binom{n}{k - 2}), (\binom{n + 1}{k - 2}), ..., (\binom{n + k - 2}{k - 2}) \end{matrix}

számoknak is. Ezt az eljárást lépésről-lépésre folytatva kapjuk, hogy

d

osztója az

\begin{matrix} (\binom{n}{k - i}), (\binom{n + 1}{k - i}), ..., (\binom{n + k - i}{k - i}) \end{matrix}

számoknak, minden

i < k

pozitív egész esetén.
Ezért, ha

i = k - 1

, akkor azt kapjuk, hogy

(\binom{n}{1})

és

(\binom{n + 1}{1})

is, s így

\begin{matrix} (\binom{n + 1}{1}) - (\binom{n}{1}) = (\binom{n}{0}) = 1 \end{matrix}

is osztható

d

-vel. Vagyis

d = 1

, ami éppen a bizonyítandó állítás.

II. megoldás. Ha

n \leq k

, akkor az első megoldásban leírtak miatt igaz az állítás. A továbbiakban tegyük fel, hogy

n > k

. Ekkor azt kell megmutatnunk, hogy bármely

p

prímszámra található az

(\binom{n}{k}), (\binom{n + 1}{k}), ..., (\binom{n + k}{k})

számok között legalább egy olyan, amely nem osztható

p

-vel.
Rögzítsük a

p

prímszámot. Tekintsük az

n - k + 1

n - k + 2

...

n

n + 1

...

n + k

számokat. Az adott binomiális együtthatók mindegyike egy olyan törtként írható fel, amelynek számlálójában ezek közül

k

darab egymást követő szám szorzata áll, nevezője pedig

k!

. Ha

p

nem osztója egyik számnak sem, akkor készen vagyunk. Ha

p

osztója az

n - k + 1

n - k + 2

...

n + k

számok közül néhánynak, akkor pedig válasszunk ki közülük egy olyan

m

számot, amely

p

-nek a lehető legnagyobb hatványával, mondjuk

p^{α}

-val osztható. Először vizsgáljuk meg az

n - k + 1 \leq m \leq n

esetet. Tekintsük az

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

binomiális együtthatót. Az

α

definíciójából következően a számlálóban egyik tényező sem osztható

p^{α + 1}

-nel. Ha pedig

0 < β \leq α

tetszőleges pozitív egész, akkor

m

választása miatt minden

i

pozitív egész esetén

m + i

pontosan akkor osztható

p^{β}

-val, ha

i

osztható vele. Ezért a törtet egyszerűsíthetjük

p^{β}

-val. Minden lehetséges

β

értékre elvégezve az egyszerűsítést, olyan törtet kapunk, amelynek sem a számlálója, sem a nevezője nem osztható

p

-vel. Tehát ebben az esetben van a feladatban szereplő binomiális együtthatók közt olyan, amelyik nem osztható

p

-vel.
Az

n < m \leq n + k

esetben pedig az

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

binomiális együtthatót érdemes tekinteni. Ekkor minden

1 \leq i \leq k

esetén a tört számlálójában szereplő

m - i

tényezőről állítható, hogy

p

-nek pontosan akkora hatványával osztható, mint a tört nevezőjében szereplő

i

tényező. Tehát az egyszerűsítések elvégzése után látható, hogy

(\binom{m - 1}{k})

nem osztható

p

-vel.
Ezzel a feladat állítását beláttuk.