 |
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:
A B. 5539. feladat értékelése még nem fejeződött be.
A KöMaL 2026. májusi matematika feladatai