KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 15 May 2009.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem B. 4178.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley