 |
A B. 5539. feladat (2026. május) |
B. 5539. Legyen \(\displaystyle n\) pozitív egész szám. Mutassuk meg, hogy
\(\displaystyle \dfrac{n!\cdot\big[\tfrac{n}{30}\big]!}{\big[\tfrac{n}{2}\big]!\cdot\big[\tfrac{n}{3}\big]!\cdot\big[\tfrac{n}{5}\big]!}\)
egész szám, és osztója az \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle \ldots\), \(\displaystyle n\) számok legkisebb közös többszörösének.
Pafnutyij Lvovics Csebisev (1821–1894) (Szentpétervár)
(5 pont)
A beküldési határidő 2026. június 10-én LEJÁRT.
Megoldás. Világos, hogy a tört számlálójának és nevezőjének is csak \(\displaystyle n\)-nél nem nagyobb prímosztói lehetnek. Legyen tehát \(\displaystyle p\leq n\) prímszám, és jelölje \(\displaystyle 1\leq \alpha_p\) a legnagyobb egész kitevőt, melyre \(\displaystyle p^{\alpha_p}\leq n\).
A Legendre-formula szerint \(\displaystyle p\) kitevője a számlálóban
\(\displaystyle \sum\limits_{\alpha=1}^{\alpha_p}\left\lfloor\frac{n}{p^{\alpha}}\right\rfloor+\sum\limits_{\alpha=1}^{\alpha_p}\left \lfloor\frac{n/30}{p^{\alpha}}\right\rfloor,\)
a nevezőben pedig
\(\displaystyle \sum\limits_{\alpha=1}^{\alpha_p}\left\lfloor\frac{n/2}{p^{\alpha}}\right\rfloor+\sum\limits_{\alpha=1}^{\alpha_p}\left \lfloor\frac{n/3}{p^{\alpha}}\right\rfloor+\sum\limits_{\alpha=1}^{\alpha_p}\left \lfloor\frac{n/5}{p^{\alpha}}\right\rfloor.\)
Az \(\displaystyle 1,2,\dots,n\) számok legkisebb közös többszörösében pedig \(\displaystyle p\) kitevője éppen \(\displaystyle \alpha_p\).
A feladat mindkét állítása rögtön következik abból, ha igazoljuk, hogy bármely \(\displaystyle 1\leq \alpha\leq \alpha_p\) mellett
\(\displaystyle 0\leq \left\lfloor\frac{n}{p^{\alpha}}\right\rfloor + \left\lfloor\frac{n/30}{p^{\alpha}}\right\rfloor - \left\lfloor\frac{n/2}{p^{\alpha}}\right\rfloor - \left\lfloor\frac{n/3}{p^{\alpha}}\right\rfloor - \left\lfloor\frac{n/5}{p^{\alpha}}\right\rfloor \leq 1,\)
hiszen az alsó becslést összegezve kapjuk, hogy a számlálóban minden prím kitevője legalább akkora, mint a nevezőben, a felső becslést összegezve pedig, hogy a törtben (ami ezek szerint egy egész szám) a kitevő nem lehet nagyobb, mint \(\displaystyle \alpha_p\).
A rövidség kedvéért legyen \(\displaystyle x=n/p^\alpha\), ekkor elegendő azt igazolnunk, hogy az
\(\displaystyle f(x):=\left\lfloor x\right\rfloor + \left\lfloor\frac{x}{30}\right\rfloor - \left\lfloor\frac{x}{2}\right\rfloor - \left\lfloor\frac{x}{3}\right\rfloor - \left\lfloor\frac{x}{5}\right\rfloor\)
függvényre
\(\displaystyle 0\leq f(x) \leq 1.\)
Világos, hogy \(\displaystyle f\) egész értékű, továbbá az \(\displaystyle \lfloor y\rfloor=y-\{y\}\) összefüggést használva kapjuk, hogy
\(\displaystyle f(x)=x-\{x\}+\frac{x}{30}-\left\{\frac{x}{30}\right\}-\frac{x}{2}+\left\{\frac{x}{2}\right\}-\frac{x}{3}+\left\{\frac{x}{3}\right\}-\frac{x}{5}+\left\{\frac{x}{5}\right\}=\left\{\frac{x}{2}\right\}+\left\{\frac{x}{3}\right\}+\left\{\frac{x}{5}\right\}-\{x\}-\left\{\frac{x}{30}\right\}.\)
Az \(\displaystyle f\) függvény eredeti alakjából világos, hogy elegendő egész helyeken vizsgálni, hiszen \(\displaystyle f(x)\) és \(\displaystyle f(\lfloor x\rfloor)\) értéke megegyezik. A továbbiakban tehát feltesszük, hogy \(\displaystyle x\) egész szám.
Ekkor \(\displaystyle f(x)=\left\{\frac{x}{2}\right\}+\left\{\frac{x}{3}\right\}+\left\{\frac{x}{5}\right\}-\left\{\frac{x}{30}\right\}\), és ebből az alakból világos, hogy
\(\displaystyle -\frac{29}{30}\leq f(x) \leq \frac12+\frac23+\frac45=\frac{59}{30},\)
ami alapján \(\displaystyle f(x)\in \{0,1\}\), hiszen \(\displaystyle f\) egész értékű.
Ezzel a feladat állítását igazoltuk.
Statisztika:
24 dolgozat érkezett. 5 pontot kapott: Bao Nguyen Gia, Bodor Ádám, Diaconescu Tashi, Ercse Ferenc, Li Mingdao, Miszori Márton, Pázmándi József Áron, Péter Hanna, Rajtik Sándor Barnabás, Sajter Klaus, Tóth László Pál, Varsányi Benedek, Wiener Marcell (13 versenyző). 4 pontot kapott: Lovas Márk, Sógor-Jász Soma (2 versenyző). 3 pontot kapott: 3 versenyző. 2 pontot kapott: 1 versenyző. 1 pontot kapott: 2 versenyző. 0 pontot kapott: 3 versenyző.
A KöMaL 2026. májusi matematika feladatai