Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem B. 4178. (April 2009)

B. 4178. Prove that for all positive integers n and k, the greatest common divisor of the numbers \binom{n}{k}, \binom{n+1}{k}, \ldots, \binom{n+k}{k} is 1.

Miklós Schweitzer Memorial Competition, 1949

(5 pont)

Deadline expired on May 15, 2009.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

49 students sent a solution.
5 points:Á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 points:Kovács 235 Gábor.
3 points:1 student.
2 points:1 student.
0 point:2 students.
Unfair, not evaluated:3 solutions.

Problems in Mathematics of KöMaL, April 2009