A B. 4634. feladat (2014. május)

B. 4634. Milyen \(\displaystyle n\) és \(\displaystyle k\) pozitív egészekre lesz \(\displaystyle \binom nk\) prímhatvány?

(5 pont)

A beküldési határidő 2014. június 10-én LEJÁRT.

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\).

Statisztika:

35 dolgozat érkezett.
5 pontot kapott:	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 pontot kapott:	Fekete Panna, Simkó Irén.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	8 versenyző.
0 pontot kapott:	5 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2014. májusi matematika feladatai