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 solutionss.

Problems in Mathematics of KöMaL, May 2014