Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4178. feladat (2009. április)

B. 4178. Bizonyítsuk be, hogy tetszőleges n, k pozitív egészek esetén az \binom{n}{k}, \binom{n+1}{k}, \ldots, \binom{n+k}{k} számok legnagyobb közös osztója 1.

(1949. évi Schweitzer Miklós Emlékverseny feladata)

(5 pont)

A beküldési határidő 2009. május 15-én LEJÁRT.

Megoldás: Ha n\lek, akkor az adott számok között szerepel \binom{k}{k}=1, az állítás nyilvánvaló. Tegyük fel tehát, hogy n\gek, ekkor mindegyik szám pozitív egész, és azt kell megmutatnunk, hogy tetszőleges p prímszámra található közöttük legalább egy olyan szám, amely p-vel nem osztható. Rögzítsük tehát a p prímszámot, és tekintsük az n-k+1, n-k+2,\ldots,n+k számokat. Az adott binomiális együtthatók mindegyike egy olyan tört alakjában í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, egyébként pedig válasszunk ki közülük egy olyan m számot, amely p-nek lehető legnagyobb hatványával, mondjuk p^\alpha-val osztható.

Tegyük fel először, hogy n-k+1\lem\len, és nézzük az

\binom{m+k}{k}=\frac{(m+k)(m+k-1)\cdots(m+1)}{k(k-1)\cdots1}

binomiális együtthatót. A számlálóban egyik tényező sem osztható p^{\alpha+1}-nel, \beta\le\alpha esetén pedig m+i pontosan akkor osztható p^\beta-val, ha i osztható vele, ezért egyszerűsítés után olyan törtet kapunk, amelynek sem számlálója, sem nevezője nem osztható p-vel. Az n<m\len+k esetben pedig az

\binom{m-1}{k}=\frac{(m-k)(m-k+1)\cdots(m-1)}{k(k-1)\cdots1}

binomiális együtthatót érdemes tekinteni; ekkor az m-i tényezőről állítható, hogy p-nek pontosan akkora hatványával osztható, mint i.

Statisztika:

49 dolgozat érkezett.
5 pontot kapott:Ágoston Péter, Ágoston Tamás, Blázsik Zoltán, Bodor Bertalan, Botos Csongor, Bősze Zsuzsanna, Cséke Balázs, Dinh Hoangthanh Attila, Dudás 002 Zsolt, Énekes Péter, Fonyó Dávid, Frankl Nóra, Horowitz Gábor, Huszár Kristóf, Janzer Olivér, Keresztfalvi Tibor, Kiss 232 Dóra, Kiss 902 Melinda Flóra, Kovács 888 Adrienn, Lovas Lia Izabella, Márki Róbert, Márkus Bence, Mester Márton, Mezei Márk, Nagy 111 Miklós, Nagy 648 Donát, Nagy Róbert, Németh Bence, Nguyen Milán, Perjési Gábor, Popper Dávid, Réti Dávid, Somogyi Ákos, Strenner Péter, Szabó 928 Attila, Tóth 222 Barnabás, Tuan Nhat Le, Varga 171 László, Vuchetich Bálint, Weisz Ágoston, Zelena Réka.
4 pontot kapott:Kovács 235 Gábor.
3 pontot kapott:1 versenyző.
2 pontot kapott:1 versenyző.
0 pontot kapott:2 versenyző.
Nem versenyszerű:3 dolgozat.

A KöMaL 2009. áprilisi matematika feladatai