Kezdőlap


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 \| MathML
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

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. Legyen $n = 2^{m}$ ( $m$ pozitív egész) és $2 ≦ k ≦ 2^{m} - 1$ egész. Ekkor

\begin{matrix} (\binom{n}{k}) = (\binom{2^{m}}{k}) = \frac{2^{m} (2^{m} - 1) ... (2^{m} - k + 1)}{k!} = & (1) \\ = \frac{2^{m}}{k} \cdot \frac{2^{m} - (k - 1)}{k - 1} \cdot \frac{2^{m} - (k - 2)}{k - 2} \cdot ... \cdot \frac{2^{m} - 1}{1} . \end{matrix}

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

2^{m} - l

is páratlan, és így

\frac{2^{m} - l}{l}

-nek sem a számlálójában, sem pedig a nevezőjében nincs

2

-es tényező.

2^{m} - 2

2^{m} - 6

2^{m} - 10

...

páros, de néggyel nem osztható, így

\frac{2^{m} - 2}{2}

\frac{2^{m} - 6}{6}

\frac{2^{m} - 10}{10}

...

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

1 ≦ l < 2^{m}

, akkor

l

és

2^{m} - l

kettőnek ugyanazzal a hatványával osztható. (Ha ugyanis

2^{i}

osztja

l

-et, akkor

l < 2^{m}

miatt

2^{i} < 2^{m}

, tehát

i < m

, s így

2^{i}

osztja

2^{m}

-et is, tehát (

2^{m} - l

)-et is. Ha pedig

2^{i}

osztja (

2^{m} - l

)-et, akkor osztja

2^{m} - (2^{m} - l) = l

-et is.)
A

\frac{2^{m} - l}{l}

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

1 ≦ l < 2^{m}

. (1) jobb oldalán így a

\frac{2^{m} - (k - 1)}{k - 1}

\frac{2^{m} - (k - 2)}{k - 2}

...

\frac{2^{m} - 1}{1}

törtek mindegyike két páratlan szám hányadosává egyszerűsíthető

(1 ≦ k - 1 < 2^{m})

. Végül

1 ≦ k < 2^{m}

miatt

k

biztosan kettőnek

m

-nél kisebb kitevőjű hatványával osztható, tehát a

2^{m} / k

tört egyszerűsítése után a számlálóban marad legalább egy

2

-es tényező. Vagyis

(\binom{2^{m}}{k})

-ban

2 ≦ k < 2^{m}

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

(\binom{2^{m}}{k})

biztosan páros, ha

2 ≦ k < 2^{m}

k = 1

esetben

(\binom{2^{m}}{k}) = (\binom{2^{m}}{1}) = 2^{m}

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

1 ≦ k < n

, amelyre

(\binom{n}{k})

nem páros. Ha

n

nem kettőhatvány, akkor a számelmélet alaptétele szerint

n = 2^{m} p

alakba írható, ahol

m ≧ 0, p

pedig

1

-nél nagyobb páratlan szám. Ha most

k = 2^{m}

, akkor

\begin{matrix} (\binom{n}{k}) = (\binom{2^{m} \cdot p}{2^{m}}) = \frac{2^{m} \cdot p \cdot (2^{m} \cdot p - 1) \cdot ... \cdot (2^{m} \cdot p - 2^{m} + 1)}{2^{m} \cdot (2^{m} - 1) \cdot ... \cdot 1} = & (2) \\ = \frac{2^{m} \cdot p}{2^{m}} \cdot \frac{2^{m} \cdot p - 1}{2^{m} - 1} \cdot ... \cdot \frac{2^{m} \cdot p - l}{2^{m} - l} \cdot ... \cdot \frac{2^{m} \cdot p - 2^{m} + 1}{1} . \end{matrix}

Most azt használjuk fel, hogy

2^{m} p - l

és

2^{m} - l

törzstényezős felbontásában a

2

ugyanazon hatványon fordul elő, ha

0 ≦ l < 2^{m}

. Ez az

l = 0

esetben nyilvánvaló; hisz a

p

páratlan. A megoldás első felében láttuk, hogy

l

és

2^{m} - l

2

-nek ugyanazzal a hatványával oszthatók. Megmutatjuk, hogy

2^{m} p - l

prímtényezős felbontásában is ez a

2

-hatvány szerepel.
Ha

2^{i} | l

, akkor

2^{i} < 2^{m}

és így

2^{i} | 2^{m}

, tehát

2^{i} | 2^{m} - l

és

2^{i} | 2^{m} p - l

. Megfordítva, ha

2^{i} | 2^{m} p - l

, akkor

i < m

. Ellenkező esetben ugyanis

2^{m} | 2^{m} p - l

és ebből

2^{m} | l

következne, ami

0 < l < 2^{m}

miatt nem lehet. Így viszont

2^{i} | 2^{m} p - l

-ből

2^{i} | 2^{m} p

miatt valóban

2^{i} | l

adódik.
Azt kaptuk, hogy (2)-ben a

\frac{2^{m} \cdot p - l}{2^{m} - i}

törtek mindegyike páratlan számok hányadosává egyszerűsíthető, és mivel a törtek szorzata,

(\binom{n}{k})

egész, ebben az esetben

(\binom{n}{k})

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

1 ≦ k < 2^{m}

, akkor

(\binom{2^{m}}{k})

páros. Ha

m = 0

, akkor az állítás üres, ha pedig

m = 1

, akkor csak

k = 1

jöhet szóba és

(\binom{2^{1}}{1}) = 2

páros.
Tekintsük most a

(\binom{2^{j + 1}}{k})

számot

(1 ≦ k < 2^{j + 1})

. Ez azt mutatja meg, hogy hányféleképpen választható ki egy

2^{j + 1}

elemű

A

halmazból

k

elem. Osszuk

A

-t két egyenlő elemszámú,

2^{j}

elemű

A_{1}

és

A_{2}

halmazra !

A

-ból úgy választhatunk ki

k

elemet, hogy

A_{1}

-ből

0

A_{2}

-ből pedig

k

elemet választunk ki ‐ ez összesen

(\binom{2^{j}}{0}) \cdot (\binom{2^{j}}{k}) = (\binom{2^{j}}{k})

-féleképpen tehető meg^{$^{*}$} ‐ és általában,

A_{1}

-ből

i

darabot,

A_{2}

-ből pedig

(k - i)

darabot ‐ ami összesen

(\binom{2^{j}}{i}) \cdot (\binom{2^{j}}{k - i})

-féleképpen lehetséges. Azt kapjuk, hogy

\begin{matrix} (\binom{2^{j + 1}}{k}) = (\binom{2^{j}}{0}) \cdot (\binom{2^{j}}{k}) + (\binom{2^{j}}{1}) \cdot (\binom{2^{j}}{k - 1}) + ... + (\binom{2^{j}}{i}) \cdot (\binom{2^{j}}{k - i}) + ... + (\binom{2^{j}}{k}) \cdot (\binom{2^{j}}{0}) . \end{matrix}

(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

(\binom{2^{j}}{i}) (\binom{2^{j}}{k - i})

szorzatban

i

és

k - i

pozitív és mivel összegük kisebb

2^{j + 1}

-nél, legalább egyikük kisebb, mint

2^{j}

. 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

2^{k}

n

-nél kisebb

2

-hatványok legnagyobbika. Ekkor

n = 2^{k} + r

, ahol

0 < r < 2^{k}

.
Azt állítjuk, hogy

(\binom{n}{r})

páratlan. Az első rész bizonyításához hasonlóan osszuk most az

n

elemű

A

halmazt egy

2^{k}

elemű

A_{1}

és egy

r

elemű

A_{2}

részre, majd csoportosítsuk az

A

halmaz

r

elemű részhalmazait aszerint, hogy hány

A_{2}

-beli elemet tartalmaznak. Így a (3)-hoz hasonlóan kapjuk, hogy

\begin{matrix} (\binom{n}{r}) = (\binom{2^{k}}{0}) (\binom{r}{r}) + (\binom{2^{k}}{1}) (\binom{r}{r - 1}) + ... + (\binom{2^{k}}{i}) (\binom{r}{r - i}) + ... + (\binom{2^{k}}{r}) (\binom{r}{0}) . \end{matrix}

(4)

A fenti összeg első tagja 1 ‐ ez annak felel meg, hogy az

r

elem mindegyike az

A_{2}

halmazból való ‐, a további tagok első tényezője pedig

(\binom{2^{k}}{i})

, ahol

0 < i < 2^{k}

, ami az állítás első része szerint páros. Ez azt jelenti, hogy ebben az esetben

(\binom{n}{r})

páratlan.

Megjegyzések. 1. Ismeretes, hogy

n!

prímtényezős felbontásában a

2

kitevője

s (n) = [\frac{n}{2}] + [\frac{n}{2^{2}}] + ... + [\frac{n}{2^{k}}] + ...

. Ha most

2^{m} ≦ n < 2^{m + 1}

, akkor

s (n) = [\frac{n}{2}] + [\frac{n}{4}] + ... + [\frac{n}{2^{m}}] ≦ n (\frac{1}{2} + \frac{1}{4} + ... + \frac{1}{2^{m}}) = n (1 - \frac{1}{2^{m}}) ≦ n - 1

, és egyenlőség pontosan akkor teljesül, ha

n = 2^{m}

.
Ez azt jelenti, hogy a

(\binom{2^{m}}{k}) = \frac{(2^{m})!}{k! (2^{m} - k)!}

tört számlálójának prímtényezős felbontásában

2^{m} - 1

, a nevezőben pedig legfeljebb

(2^{m} - k - 1) + (k - 1) = 2^{m} - 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

(\binom{n}{k}) = 0