 |
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