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, Kombinációk, Oszthatósági feladatok, 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.

 
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-i)+...+(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.

 
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.