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 file
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

Legyen n tetszőleges pozitív egész. Mutassuk meg, hogy 2(3n)! osztható n!(n+1)!(n+2)!-sal.

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(3n)! prímtényezős felbontásában bármelyik prímszám legalább akkora kitevővel szerepel, mint n!(n+1)!(n+2)! 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
α=1[kpα]=[kp]+[kp2]+[kp3]+....
Az összegnek csak az első [logpn] 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
α=1[npα]+α=1[n+1pα]+α=1[n+2pα]α=1[3npα],(1)
illetve p=2 esetén
α=1[n2α]+α=1[n+12α]+α=1[n+22α]1+α=1[3n2α].(2)
Az [x]+[x+13]+[x+23]=[3x] azonosság alapján tetszőleges pα3-ra
[npα]+[n+1pα]+[n+2pα][npα]+[npα+13]+[npα+23]=[3npα],
továbbá az [x]+[x+12]=[2x] azonosság felhasználásával
[n2]+[n+12]+[n+22]=n+[n2]+1=[3n2]+1.
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 (p+q+r)!p!q!r! egész. (Például p darab A, q darab B és r darab C betűből (p+q+r)!p!q!r! féle szó készíthető.)
Könnyű ellenőrizni, hogy
2(3n)!n!(n+1)!(n+2)!=(3n)!n!3+17(3n)!(n-1)!2(n+2)!-7(3n+1)!(n-1)!n!(n+2)!+(3n+1)!(n-1)!(n+1)!2.
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!2!...(k-1)!(kn)! osztható n!(n+1)!...(n+k-1)!-sal.
2. A 2(3n)!n!(n+1)!(n+2)! számnak (és az általánosabb 1!2!...(k-1)!(kn)!n!(n+1)!...(n+k-1)!-nak) vannak kombinatorikus jelentétesei is. Ezzel kapcsolatban lásd az N. 163. feladatot.