Feladat:	N.144	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Baharev Ali ,  Bérczi Gergely ,  Boros M. Mátyás ,  Gerbicz Róbert ,  Gyenes Zoltán ,  Hegedűs Péter ,  Hesz Gábor ,  Hesz Zoltán ,  Horváth Gábor ,  Hubenkó Elemér ,  Juhász András ,  Katona Zsolt ,  Kiss Tamás ,  Kun Gábor ,  Léka Zoltán ,  Lippner Gábor ,  Lukács László ,  Mecz Balázs ,  Naszódi Gergely ,  Pap Júlia ,  Papp Dávid ,  Pataki Péter ,  Székelyhidi Gábor ,  Szigel Gábor ,  Szűcs Gábor ,  Terpai Tamás ,  Tóth Ádám ,  Végh A. László ,  Zábrádi Gergely ,  Zawadowski Ádám
Füzet:	1998/február, 98 - 99. oldal		PDF  |  MathML
Témakör(ök):	Oszthatósági feladatok, Prímtényezős felbontás, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1997/szeptember: N.144

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Megmutatjuk, hogy $2\cdot \left(3n\right)!$ prímtényezős felbontásában bármelyik prímszám legalább akkora kitevővel szerepel, mint $n!\left(n+1\right)!\left(n+2\right)!$ felbontásában. Felhasználjuk azt a Legendre-tól származó tételt, miszerint $k!$ prímtényezős felbontásában egy tetszőleges $p$ prímszám kitevője $\begin{array}{c}{\displaystyle \sum _{\alpha =1}^{\infty }\left[\frac{k}{p^{\alpha }}\right]=\left[\frac{k}{p}\right]+\left[\frac{k}{p^2}\right]+\left[\frac{k}{p^3}\right]+\text{...}\mathrm{.}}\end{array}$ Az összegnek csak az első $\left[\text{log}{}_{p}n\right]$ tagja nem 0, elég az összeget idáig felírni.) A tétel és bizonyítása megtalálható pl. Erdős‐Surányi: Válogatott fejezetek a számelméletből c. könyvének 29. oldalán (XII. tétel). A tételt alkalmazva a $k=n$, $k=n+1$, $k=n+2$ és $k=3n$ esetekre, azt kell igazolnunk, hogy tetszőleges $p>2$ esetén $\begin{array}{c}{\displaystyle \sum _{\alpha =1}^{\infty }\left[\frac{n}{p^{\alpha }}\right]+\sum _{\alpha =1}^{\infty }\left[\frac{n+1}{p^{\alpha }}\right]+\sum _{\alpha =1}^{\infty }\left[\frac{n+2}{p^{\alpha }}\right]\le \sum _{\alpha =1}^{\infty }\left[\frac{3n}{p^{\alpha }}\right]\mathrm{,}}\end{array}$ (1) illetve $p=2$ esetén $\begin{array}{c}{\displaystyle \sum _{\alpha =1}^{\infty }\left[\frac{n}{2^{\alpha }}\right]+\sum _{\alpha =1}^{\infty }\left[\frac{n+1}{2^{\alpha }}\right]+\sum _{\alpha =1}^{\infty }\left[\frac{n+2}{2^{\alpha }}\right]\le 1+\sum _{\alpha =1}^{\infty }\left[\frac{3n}{2^{\alpha }}\right]\mathrm{.}}\end{array}$ (2) Az $\left[x\right]+\left[x+\frac{1}{3}\right]+\left[x+\frac{2}{3}\right]=\left[3x\right]$ azonosság alapján tetszőleges $p^{\alpha }\ge 3$-ra $\begin{array}{c}{\displaystyle \left[\frac{n}{p^{\alpha }}\right]+\left[\frac{n+1}{p^{\alpha }}\right]+\left[\frac{n+2}{p^{\alpha }}\right]\le \left[\frac{n}{p^{\alpha }}\right]+\left[\frac{n}{p^{\alpha }}+\frac{1}{3}\right]+\left[\frac{n}{p^{\alpha }}+\frac{2}{3}\right]=\left[\frac{3n}{p^{\alpha }}\right]\mathrm{,}}\end{array}$ továbbá az $\left[x\right]+\left[x+\frac{1}{2}\right]=\left[2x\right]$ azonosság felhasználásával $\begin{array}{c}{\displaystyle \left[\frac{n}{2}\right]+\left[\frac{n+1}{2}\right]+\left[\frac{n+2}{2}\right]=n+\left[\frac{n}{2}\right]+1=\left[\frac{3n}{2}\right]+1.}\end{array}$ Ezekből az egyenlőtlenségekből (1) és (2) azonnal következik.   II. megoldás. Felhasználjuk, hogy ha $p$, $q$ és $r$ nem-negatív egész számok, akkor $\frac{\left(p+q+r\right)!}{p!q!r!}$ egész. (Például $p$ darab $A$, $q$ darab $B$ és $r$ darab $C$ betűből $\frac{\left(p+q+r\right)!}{p!q!r!}$ féle szó készíthető.) Könnyű ellenőrizni, hogy $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle \frac{2\cdot \left(3n\right)!}{n!\left(n+1\right)!\left(n+2\right)!}=\frac{\left(3n\right)!}{n{!}^3}+17\frac{\left(3n\right)!}{\left(n-1\right){!}^2\left(n+2\right)!}-7\frac{\left(3n+1\right)!}{\left(n-1\right)!n!\left(n+2\right)!}+\frac{\left(3n+1\right)!}{\left(n-1\right)!\left(n+1\right){!}^2}\mathrm{.}}\end{array}}}\end{array}$ A jobb oldalon mindegyik tag egész.   Megjegyzések. 1. Az első megoldás gondolatmenetét követve igazolható, hogy tetszőleges $k$ és $n$ pozitív egészekre $1!\cdot 2!\cdot \text{...}\cdot \left(k-1\right)!\cdot \left(kn\right)!$ osztható $n!\cdot \left(n+1\right)!\cdot \text{...}\cdot \left(n+k-1\right)!$-sal. 2. A $\frac{2\cdot \left(3n\right)!}{n!\left(n+1\right)!\left(n+2\right)!}$ számnak (és az általánosabb $\frac{1!\cdot 2!\cdot \text{...}\cdot \left(k-1\right)!\cdot \left(kn\right)!}{n!\cdot \left(n+1\right)!\cdot \text{...}\cdot \left(n+k-1\right)!}$-nak) vannak kombinatorikus jelentétesei is. Ezzel kapcsolatban lásd az N. 163. feladatot.