 |
A B. 5481. feladat (2025. október) |
B. 5481. Bizonyítsuk be, hogy bármely \(\displaystyle n\) pozitív egészre teljesül, hogy
\(\displaystyle (n!)^n \mid n^2 \cdot (n^2-1) \cdot (n^2-2) \cdot \ldots \cdot (n+2) \cdot (n+1). \)
Javasolta: Hujter Bálint (Budapest)
(4 pont)
A beküldési határidő 2025. november 10-én LEJÁRT.
1. megoldás. A megoldás során a szokásos módon \(\displaystyle v_p(k)\) azt jelöli, hogy a \(\displaystyle k\) pozitív egész szám prímtényezős felbontásában a \(\displaystyle p\) prím milyen kitevővel szerepel. Azt kell igazolnunk, hogy minden \(\displaystyle p\) prímszámra
\(\displaystyle v_p\Big((n^2)!\Big) \ge (n+1)\cdot v_p\Big(n!\Big). \)
A Legendre-formula szerint
\(\displaystyle v_p\Big(n!\Big)=\sum_{k=1}^\infty\left[\dfrac{n}{p^k}\right] \quad\text{és}\quad v_p\Big((n^2)!\Big)=\sum_{k=1}^\infty\left[\dfrac{n^2}{p^k}\right], \)
tehát azt kell megmutatnunk, hogy
\(\displaystyle \sum_{k=1}^\infty\left[\dfrac{n^2}{p^k}\right] \ge (n+1)\cdot \sum_{k=1}^\infty\left[\dfrac{n}{p^k}\right]. \)
Ha \(\displaystyle p>n\), akkor a jobboldal \(\displaystyle 0\). Tegyük fel tehát, hogy \(\displaystyle p\le n\), és legyen \(\displaystyle k_0\) a legnagyobb olyan pozitív egész szám, amelyre \(\displaystyle p^{k_0}\le n\). Ekkor
\(\displaystyle v_p\Big((n^2)!\Big)= \sum_{k=1}^\infty\left[\dfrac{n^2}{p^k}\right] \ge \sum_{k=1}^{2k_0}\left[\dfrac{n^2}{p^k}\right] = \sum_{k=1}^{k_0}\left[\dfrac{n^2}{p^k}\right]+ \sum_{k=1}^{k_0}\left[\dfrac{n^2}{p^{k_0+k}}\right]. \)
Az \(\displaystyle [nx]\ge n[x]\) egyenlőtlenséget felhasználva
\(\displaystyle \left[\dfrac{n^2}{p^k}\right] = \left[n\cdot\dfrac{n}{p^k}\right] \ge n\cdot\left[\dfrac{n}{p^k}\right], \)
Az egészrész-függvény monotonitása miatt pedig
\(\displaystyle \left[\dfrac{n^2}{p^{k_0+k}}\right] = \left[\frac{n}{p^{k_0}}\cdot \dfrac{n}{p^{k}}\right] \ge \left[\dfrac{n}{p^{k}}\right]. \)
Így
\(\displaystyle v_p\Big((n^2)!\Big) \ge \sum_{k=1}^{k_0}\left[\dfrac{n^2}{p^k}\right]+ \sum_{k=1}^{k_0}\left[\dfrac{n^2}{p^{k_0+k}}\right] \ge \sum_{k=1}^{k_0}\left(n\cdot\left[\dfrac{n}{p^k}\right]+\left[\dfrac{n}{p^{k}}\right]\right) = \)
\(\displaystyle = (n+1)\sum_{k=1}^{k_0}\left[\dfrac{n}{p^{k}}\right] \ge (n+1)\sum_{k=1}^\infty\left[\dfrac{n}{p^{k}}\right] = (n+1)\cdot v_p\Big(n!\Big). \)
2. megoldás. A feladat állítása ekvivalens az \(\displaystyle (n!)^{n+1}\mid (n^2)!\) oszthatósággal. Azt fogjuk bizonyítani, hogy \(\displaystyle \frac{(n^2)!}{(n!)^{n+1}}\) éppen azt adja meg, \(\displaystyle n^2\) dolgot hányféleképpen lehet \(\displaystyle n\) darab \(\displaystyle n\) méretű csoportba szétosztani, így következésképpen egész szám, ami a feladat állítását is igazolja.
Osszuk csoportba az első \(\displaystyle n^2\) pozitív egész számot. Ezt megtehetjük úgy, hogy leírjuk őket egy tetszőleges sorrendben, majd az első \(\displaystyle n\) szám alkotja az első csoportot, a következő \(\displaystyle n\) szám a másodikat, és így tovább... Ugyanazt a szétosztást ily módon többször is megkapjuk, hiszen egyrészt a csoportokon belül tetszőleges sorrendben lehetnek az elemek, másrészt az \(\displaystyle n\) csoport sorrendje is szabadon permutálható. Egy úgy módosított szétosztási feladatnál kapnánk meg minden beosztást pontosan egyszer, ahol \(\displaystyle n\) darab, 1-től \(\displaystyle n\)-ig sorszámozott \(\displaystyle n\) méretű csoportba kellene beosztani az elemeket úgy, hogy az egy csoportba kerülő elemek is 1-től \(\displaystyle n\)-ig sorszámozva kerülnek be (vagyis számít a sorrendjük). Mindezek alapján az eredeti változatban minden beosztást \(\displaystyle (n!)^{n+1}\)-féleképpen kapunk meg (mind az \(\displaystyle n\) csoporton belül \(\displaystyle n!\) féle sorrend és a csoportok sorrendje is \(\displaystyle n!\) féle lehet), vagyis \(\displaystyle n^2\) számot \(\displaystyle n\) darab csoportba szétosztani \(\displaystyle \frac{(n^2)!}{(n!)^{n+1}}\)-féleképpen lehet. Mivel ez egy egész szám, ezzel a feladat állítását igazoltuk.
Statisztika:
A B. 5481. feladat értékelése még nem fejeződött be.
A KöMaL 2025. októberi matematika feladatai