KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4634. (May 2014)

B. 4634. For what positive integers \(\displaystyle n\) and \(\displaystyle k\) is \(\displaystyle \binom nk\) a power of a prime?

(5 pont)

Deadline expired on June 10, 2014.


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

Megoldás. A Legendre-formula szerint \(\displaystyle m!\) prímtényezős felbontásában a \(\displaystyle p\) prímszám kitevője \(\displaystyle \sum_{i=1}^{M}\left[\frac{m}{p^i}\right]\), ahol \(\displaystyle M\) a legnagyobb olyan egész, amelyre még \(\displaystyle p^{M}\leq m\). Ebből következik, hogy \(\displaystyle \binom{n}{k}\) prímtényezős felbontásában a \(\displaystyle p\) prímszám kitevője

\(\displaystyle \sum_{i=1}^{N}\left(\left[\frac{n}{p^i}\right]-\left[\frac{k}{p^i}\right]-\left[\frac{n-k}{p^i}\right]\right),\)

ahol \(\displaystyle N\) a legnagyobb olyan egész szám, amelyre még \(\displaystyle p^N\leq n\). Mivel minden \(\displaystyle x,y\) valós számra fennáll az \(\displaystyle [x+y]-[x]-[y]\leq 1\) egyenlőtlenség, ezért ebben az összegben minden tag értéke legfeljebb 1, vagyis \(\displaystyle \binom{n}{k}\) prímtényezős felbontásában \(\displaystyle p\) kitevője legfeljebb \(\displaystyle N\). Mivel \(\displaystyle p^N\leq n\), ezért ez azt jelenti, hogy \(\displaystyle \binom{n}{k}\) minden prímhatvány osztója legfeljebb \(\displaystyle n\). Így \(\displaystyle \binom{n}{k}\) csak akkor lehet prímhatvány, ha \(\displaystyle k=1\) vagy \(\displaystyle k=n-1\), és \(\displaystyle \binom{n}{1}=\binom{n}{n-1}=n\) prímhatvány, hiszen \(\displaystyle 1<k<n-1\) esetén \(\displaystyle \binom{n}{k}>n\), ha pedig \(\displaystyle k=0\) vagy \(\displaystyle k=n\), akkor \(\displaystyle \binom{n}{k}=1\).

Ezzel bebizonyítottuk, hogy \(\displaystyle \binom{n}{k}\) pontosan akkor prímhatvány, ha \(\displaystyle n\) prímhatvány és \(\displaystyle k=1\) vagy \(\displaystyle k=n-1\).


Statistics:

35 students sent a solution.
5 points:Andó Angelika, Baran Zsuzsanna, Di Giovanni Márk, Forrás Bence, Gyulai-Nagy Szuzina, Kúsz Ágnes, Lajkó Kálmán, Maga Balázs, Porupsánszki István, Schwarcz Tamás, Szőke Tamás, Tóth Viktor, Williams Kada.
4 points:Fekete Panna, Simkó Irén.
2 points:5 students.
1 point:8 students.
0 point:5 students.
Unfair, not evaluated:2 solutions.

Our web pages are supported by:   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