Feladat: F.2507 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Schmideg Ádám ,  Várkonyi Viktor 
Füzet: 1986/január, 3 - 5. oldal  PDF file
Témakör(ök): Algebrai átalakítások, Összefüggések binomiális együtthatókra, Binomiális együtthatók, Kombinációk, Oszthatósági feladatok, Prímtényezős felbontás, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1985/január: F.2507

Legyen n kettőhatvány. Igazoljuk, hogy ekkor minden 1kn-1 egészre (nk) páros. Igaz-e az állítás megfordítása is?

I. megoldás. Legyen n=2m (m pozitív egész) és 2k2m-1 egész. Ekkor
(nk)=(2mk)=2m(2m-1)...(2m-k+1)k!=(1)=2mk2m-(k-1)k-12m-(k-2)k-2...2m-11.


Ez a szám biztosan egész. Egyszerűsítsük gondolatban a törtet úgy, hogy először a kettő hatványaival osszunk! Ha l páratlan, akkor 2m-l is páratlan, és így 2m-ll-nek sem a számlálójában, sem pedig a nevezőjében nincs 2-es tényező. 2m-2, 2m-6, 2m-10, ... páros, de néggyel nem osztható, így 2m-22, 2m-66, 2m-1010, ... 2-vel való egyszerűsítés után rendre két páratlan szám hányadosa lesz.
Általában is igaz, hogy ha 1l<2m, akkor l és 2m-l kettőnek ugyanazzal a hatványával osztható. (Ha ugyanis 2i osztja l-et, akkor l<2m miatt 2i<2m, tehát i<m, s így 2i osztja 2m-et is, tehát (2m-l)-et is. Ha pedig 2i osztja (2m-l)-et, akkor osztja 2m-(2m-l)=l-et is.)
A 2m-ll tört tehát általában is egyszerűsíthető úgy, hogy a számlálóban és a nevezőben is páratlan szám maradjon, feltéve, hogy 1l<2m. (1) jobb oldalán így a 2m-(k-1)k-1, 2m-(k-2)k-2, ..., 2m-11 törtek mindegyike két páratlan szám hányadosává egyszerűsíthető (1k-1<2m). Végül 1k<2m miatt k biztosan kettőnek m-nél kisebb kitevőjű hatványával osztható, tehát a 2m/k tört egyszerűsítése után a számlálóban marad legalább egy 2-es tényező. Vagyis (2mk)-ban 2k<2m esetén kettő minden lehetséges hatványával egyszerűsítve a nevező páratlan lesz, a számláló pedig páros.
Folytassuk az egyszerűsítést a 2-nél nagyobb prímek megfelelő hatványával! Miután 2-vel a továbbiakban már nem osztunk, az eredményül kapott egész szám páros.
Megmutattuk tehát, hogy (2mk) biztosan páros, ha 2k<2m.
k=1 esetben (2mk)=(2m1)=2m nyilván páros. Ezzel az állítást beláttuk.
Bebizonyítjuk, hogy az állítás fordítottja is igaz: ha n nem kettőhatvány, akkor van olyan 1k<n, amelyre (nk) nem páros. Ha n nem kettőhatvány, akkor a számelmélet alaptétele szerint n=2mp alakba írható, ahol m0,p pedig 1-nél nagyobb páratlan szám. Ha most k=2m, akkor
(nk)=(2mp2m)=2mp(2mp-1)...(2mp-2m+1)2m(2m-1)...1=(2)=2mp2m2mp-12m-1...2mp-l2m-l...2mp-2m+11.


Most azt használjuk fel, hogy 2mp-l és 2m-l törzstényezős felbontásában a 2 ugyanazon hatványon fordul elő, ha 0l<2m. Ez az l=0 esetben nyilvánvaló; hisz a p páratlan. A megoldás első felében láttuk, hogy l és 2m-l 2-nek ugyanazzal a hatványával oszthatók. Megmutatjuk, hogy 2mp-l prímtényezős felbontásában is ez a 2-hatvány szerepel.
Ha 2i|l, akkor 2i<2m és így 2i|2m, tehát 2i|2m-l és 2i|2mp-l. Megfordítva, ha 2i|2mp-l, akkor i<m. Ellenkező esetben ugyanis 2m|2mp-l és ebből 2m|l következne, ami 0<l<2m miatt nem lehet. Így viszont 2i|2mp-l-ből 2i|2mp miatt valóban 2i|l adódik.
Azt kaptuk, hogy (2)-ben a 2mp-l2m-i törtek mindegyike páratlan számok hányadosává egyszerűsíthető, és mivel a törtek szorzata, (nk) egész, ebben az esetben (nk) páratlan.
 

 Schmideg Ádám (Bp. Berzsenyi D. Gimn., III. o. t.)
 
II. megoldás. A binomiális együtthatók kombinatorikai jelentését használjuk ki a megoldásban. Először m-re vonatkozó teljes indukcióval megmutatjuk, hogy ha 1k<2m, akkor (2mk) páros. Ha m=0, akkor az állítás üres, ha pedig m=1, akkor csak k=1 jöhet szóba és (211)=2 páros.
Tekintsük most a (2j+1k) számot (1k<2j+1). Ez azt mutatja meg, hogy hányféleképpen választható ki egy 2j+1 elemű A halmazból k elem. Osszuk A-t két egyenlő elemszámú, 2j elemű A1 és A2 halmazra !
A-ból úgy választhatunk ki k elemet, hogy A1-ből 0, A2-ből pedig k elemet választunk ki ‐ ez összesen (2j0)(2jk)=(2jk)-féleképpen tehető meg* ‐ és általában, A1-ből i darabot, A2-ből pedig (k-i) darabot ‐ ami összesen (2ji)(2jk-i)-féleképpen lehetséges. Azt kapjuk, hogy
(2j+1k)=(2j0)(2jk)+(2j1)(2jk-1)+...+(2ji)(2jk-1)+...+(2jk)(2j0).(3)

A fenti egyenlőség jobb oldalán az első és az utolsó tag egyenlő, összegük tehát páros. Minden további (2ji)(2jk-i) szorzatban i és k-i pozitív és mivel összegük kisebb 2j+1-nél, legalább egyikük kisebb, mint 2j. A szorzatnak ez a tényezője így az indukciós feltevés szerint páros, és így (3) jobb oldalán páros szám áll.
Az állítás megfordításának bizonyításához tegyük most fel, hogy az n nem 2-hatvány, és legyen 2k az n-nél kisebb 2-hatványok legnagyobbika. Ekkor n=2k+r, ahol 0<r<2k.
Azt állítjuk, hogy (nr) páratlan. Az első rész bizonyításához hasonlóan osszuk most az n elemű A halmazt egy 2k elemű A1 és egy r elemű A2 részre, majd csoportosítsuk az A halmaz r elemű részhalmazait aszerint, hogy hány A2-beli elemet tartalmaznak. Így a (3)-hoz hasonlóan kapjuk, hogy
(nr)=(2k0)(rr)+(2k1)(rr-1)+...+(2ki)(rr-i)+...+(2kr)(r0).(4)
A fenti összeg első tagja 1 ‐ ez annak felel meg, hogy az r elem mindegyike az A2 halmazból való ‐, a további tagok első tényezője pedig (2ki), ahol 0<i<2k, ami az állítás első része szerint páros. Ez azt jelenti, hogy ebben az esetben (nr) páratlan.
 

 Várkonyi Viktor (Bp. Táncsics Mihály Gimn., III. o. t.)
 dolgozata alapján
 
Megjegyzések. 1. Ismeretes, hogy n! prímtényezős felbontásában a 2 kitevője s(n)=[n2]+[n22]+...+[n2k]+.... Ha most 2mn<2m+1, akkor s(n)=[n2]+[n4]+...+[n2m]n(12+14+...+12m)=n(1-12m)n-1, és egyenlőség pontosan akkor teljesül, ha n=2m.
Ez azt jelenti, hogy a (2mk)=(2m)!k!(2m-k)! tört számlálójának prímtényezős felbontásában 2m-1, a nevezőben pedig legfeljebb (2m-k-1)+(k-1)=2m-2 darab kettős tényező szerepel, így az állítás első felének újabb bizonyítását kapjuk.
2. A feladat állítása igaz marad, ha a 2 helyére tetszőleges p prímszámot írunk.
3. A feladat kapcsolatban áll a tavalyi Kürschák-verseny 1. feladatával. A megoldásokat lásd a következő cikkben: Surányi János: Az 1984. évi Kürschák József matematikai tanulóverseny feladatainak megoldása KML 35 (1985) 51. oldal.

*Ha k>n, akkor megállapodás szerint (nk)=0.