Problem B. 5539. (May 2026)
B. 5539. For any positive integer \(\displaystyle n\) prove that
\(\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]!}\)
is an integer, and divides the least common multiple of integers \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle \ldots\), \(\displaystyle n\).
Pafnuty Lvovich Chebyshev (1821–1894), Saint Petersburg
(5 pont)
Deadline expired on June 10, 2026.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
24 students sent a solution. 5 points: 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 students). 4 points: Lovas Márk, Sógor-Jász Soma (2 students). 3 points: 3 students. 2 points: 1 student. 1 point: 2 students. 0 points: 3 students.
Problems in Mathematics of KöMaL, May 2026