Kezdőlap


Feladat:	F.2597	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1987/március, 106 - 109. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Binominális együtthatók prímtényezős felbontása, Kettes alapú számrendszer, Feladat
Hivatkozás(ok):	Feladatok: 1986/október: F.2597

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. $n = 1$ nyilván megfelel, $n = 2$ nem: $(\binom{1}{0}) = (\binom{1}{1}) = 1$ páratlan, de $(\binom{2}{1}) = 2$ páros. A továbbiakban legyen $n$ a feltételeknek megfelelő, 2-nél nagyobb egész. Ismeretes, hogy

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

(\binom{n}{1}) = n

páratlan, akkor

(\binom{n}{2}) = n \frac{n - 1}{2}

csak úgy lehet páratlan, ha

n - 1

páros, de nem osztható néggyel. Ha

n > 4

, akkor tekintsük a

3 (\binom{n}{4}) = \frac{n (n - 1)}{2} \cdot (n - 2) \frac{n - 3}{4}

számot. Ez páratlan, és

\frac{n (n - 1)}{2} = (\binom{n}{2})

is,

n - 2

is páratlan egész, tehát

\frac{n - 3}{4}

is szükségképp egész. Ezért

n - 3

osztható néggyel. Ha most

n > 2^{l}

, akkor hasonlóan a

(2^{l} - 1) (\binom{n}{2^{l}})

páratlan egész, másrészt

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

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

Itt a bal oldal és a jobb oldal első két tényezője páratlan egész, tehát

2^{l}

osztója (

n - 2^{l} + 1

)-nek. Azt kaptuk, hogy valahányszor

2^{l} < n

(n - 2^{l} + 1)

-nek mindannyiszor osztója

2^{l}

. Legyen

2^{L}

a legnagyobb,

n

-nél kisebb kettőhatvány:

2^{L} < n < 2^{L + 1}

. Ilyen

L ≧ 1

létezik, hisz

n

páratlan és

n ≧ 3.

Ekkor az imént bizonyítottak szerint

2^{L}

osztója (

n - 2^{L} + 1

)-nek. De

n - 2^{L} + 1 < 2^{L + 1} - 2^{L} + 1 = 2^{L} + 1

és

n - 2^{L} + 1 > 1

. Mivel

2^{L}

az 1-nél nagyobb, és a (

2^{L} + 1

)-nél kisebb számok közül csak önmagát osztja, ezért

2^{L} = n - 2^{L} + 1

, tehát

n = 2^{L + 1} - 1

.
Azt kaptuk, hogy ha

(\binom{n}{k})

minden

k

-ra páratlan, akkor vagy

n = 1

vagy

n = 2^{L + 1} - 1

alakú, ahol

L ≧ 1

.
Most megmutatjuk, hogy a talált feltétel elégséges, azaz ha

n = 2^{L + 1} - 1

alakú, akkor

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

minden

1 ≦ k ≦ 2^{L + 1} - 1

esetén páratlan.
S valóban: ha

1 ≦ j ≦ 2^{L + 1} - 1

, akkor a fenti szorzat j-edik tényezője,

\frac{2^{L + 1} - j}{j}

olyan törtté egyszerűsíthető, amelynek számlálója is, nevezője is páratlan egész. Írjuk fel ugyanis

j

-t

2^{m} \cdot j'

alakban, ahol

m ≧ 0

egész és

j' > 0

páratlan. Minthogy

2^{m} ≦ j < 2^{L + 1}

, ezért

m ≦ L

. Következésképp

\begin{matrix} \frac{2^{L + 1} - j}{j} = \frac{2^{m} (2^{L + 1 - m} - j')}{2^{m} j'} = \frac{2^{L + 1 - m} - j'}{j'} . \end{matrix}

Itt

j'

, s így

2^{L + 1 - m} - j'

is páratlan egész, ahogy állítottuk.

(\binom{2^{L + 1} - 1}{k})

tehát minden

1 ≦ k ≦ 2^{L + 1} - 1

esetén egész, másrészt olyan törtek szorzata, amelyeknek számlálója is, nevezője is páratlan. Ebből következik, hogy

(\binom{2^{L + 1} - k}{k})

csak páratlan egész lehet. Végül

(\binom{2^{L + 1} - 1}{0}) = 1

is páratlan.
Beláttuk tehát, hogy

(\binom{n}{k})

pontosan akkor páratlan minden

0 ≦ k ≦ n

-re, ha

n = 2^{m} - 1

alakú, ahol

m ≧ 2. (L ≧ 1

volt.) Végül

m = 1

-re

n = 2^{1} - 1 = 1

is megfelel, tehát a feladat feltételeinek pontosan azok az

n

számok felelnek meg, amelyek egy kettőhatványnál 1-gyel kisebbek:

n = 1

3

7

...

2^{m} - 1

...

Megjegyzések. 1. A megoldás során gyakran használtuk a számelmélet alaptételét.
2. Ismeretes (1. KÖMAL F. 2507., 1986/1. sz. 3. o.), hogy

(\binom{n}{k})

pontosan akkor lesz minden

1 ≦ k ≦ (n - 1)

-re páros, ha

n

kettőhatvány. Most megmutatjuk, hogy ez az állítás egyenértékű a feladat megoldásában bizonyítottakkal. Belátjuk, hogy

(\binom{n}{l})

pontosan akkor lesz minden

0 ≦ l ≦ n

-re páratlan, ha

(\binom{n + 1}{l})

páros minden

1 ≦ l ≦ n

-re. (Ebből a két állítás egyenértékűsége már következik.)
Ismert, hogy

\begin{matrix} (\binom{n}{l - 1}) + (\binom{n}{l}) = (\binom{n + 1}{l}), \end{matrix}

1 ≦ l ≦ n

. Ha minden

(\binom{n}{l})

páratlan

(0 ≦ l ≦ n)

, akkor a bal oldalon két páratlan szám összege áll s az páros, tehát

(\binom{n + 1}{l})

páros

1 ≦ l ≦ n

esetén. Másrészt ha

(\binom{n + 1}{l})

minden

1 ≦ l ≦ n

-re páros, akkor

(\binom{n}{l - 1})

és

(\binom{n}{l})

minden

1 ≦ l ≦ n

-re ugyanazt a maradékot adja kettővel osztva, azaz egyforma paritású. Tehát

(\binom{n}{0})

és

(\binom{n}{1})

(\binom{n}{1})

és

(\binom{n}{2})

...

(\binom{n}{n - 1})

és

(\binom{n}{n})

egyforma paritású, ami azt jelenti, hogy

(\binom{n}{0})

(\binom{n}{1})

(\binom{n}{2})

...

(\binom{n}{n})

paritása megegyezik. Minthogy

(\binom{n}{n}) = 1

, ezért mindegyikük páratlan, ahogy állítottuk. 3. Az állítás hasonlóan bizonyítható a módosított Pascal-háromszöggel is,

(\binom{n}{k})

helyére 1-et vagy 0-t írva aszerint, hogy páratlan vagy páros. A módosított (''mod 2'' számolt) Pascal-háromszög így néz ki (l. KÖMAL 1985/2. 51. o.):

(1. sor csupa 1-es;
2. sor csupa 1-es;
3. sor nem csupa 1-es;
:
:

2^{k} .

sor csupa 1-es;
:
:

2^{k + 1} .

sor csupa 1-es)

Itt a ,,fenti'' és a két ,,oldalsó, lenti'' háromszög megegyezik. Az ábráról leolvasható, hogy a

2^{k} + 1

2^{k} + 2

...

2^{k + 1} - 1

sorok mindegyikében van nulla (,,középen''), míg a

2^{k + 1}

. sorban nincs. Tehát pontosan azokban a sorokban áll végig egyes, amelyek sorszáma kettőhatvány. Az

n

. sorban a

k

. helyen éppen az

(\binom{n - 1}{k - 1})

szám kettővel osztva kapott maradéka áll, vagyis ismét azt kaptuk, hogy

(\binom{n}{k})

akkor lesz minden

0 ≦ k ≦ n

-re páratlan, ha a módosított Pascal-háromszög

(n + 1)

. sorában végig egyes áll, azaz ha

n + 1

kettőhatvány.

II. megoldás. A 2. megjegyzésben idézett állítás felhasználásával általában adunk szükséges és elegendő feltételt arra, hogy adott

n

és

k

esetén

(\binom{n}{k})

páratlan legyen.
Írjuk fel ehhez az

n

-et kettes számrendszerben, azaz legyen

n = 2^{a_{r}} + 2^{a_{r - 1}} + ... + 2^{a_{1}}

, ahol

a_{1} < a_{2} < ... < a_{r}

, és tekintsünk egy

n

-elemű halmazt, amelynek minden elemét

r

darab szín valamelyikével festettük ki úgy, hogy az egyes színekből rendre

2^{a_{1}}, 2^{a_{2}}, ..., 2^{a_{r}}

darab forduljon elő.
Az idézett állítás szerint tetszőleges

1 ≦ k' < 2^{a_{i}}

esetén

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

páros, tehát az azonos színű elemek adott,

k'

elemszámú részhalmazai párokba rendezhetők. A kifestés után minden egyes csoportban rögzítsük ezeket a párosításokat is, mégpedig minden

1 ≦ k' < 2^{a_{i}}

esetben.
Legyen most

0 ≦ k ≦ n

tetszőleges és tekintsük az

n

-elemű halmaz

(\binom{n}{k})

darab

k

-elemű részhalmazát. Vegyük szemügyre azokat a

k

-asokat, amelyekhez van olyan szín ‐ mondjuk az

i

-edik ‐, hogy mind az adott részhalmazban, mind pedig rajta kívül található

i

-színű elem. Hívjuk az ilyen

k

-asokat ‐ az

i

színre nézve ‐ csonkának. Megmutatjuk, hogy a csonka

k

-asok száma páros.
Tekintsük ehhez minden egyes ilyen

k

-ashoz a legkisebb olyan

i

-t, amelyre nézve csonka. Ha egy ilyen

k

-as a

2^{a_{i}}

darab

i

-színű elem közül

k'

darabot tartalmaz, akkor nyilván

k' ≦ k

, másrészt a csonkaság miatt

0 < k' < 2^{a_{i}}

.
Feleltessük most meg ennek a csonka

k

-asnak azt a

k

-ast, amelyben az

i

-től különböző színű elemek ugyanazok, a

k'

darab

i

-színű elem helyére pedig az ennek a

k'

-elemű részhalmaznak a

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

, darab

i

-színű

k'

-elemű részhalmazon rögzített párosításnak megfelelő részhalmaz kerül. Ez a megfeleltetés nyilván kölcsönösen egyértelmű, csonka

k

-ashoz tőle különböző csonka

k

-ast rendel, így a csonka

k

-asok száma valóban páros.
Ez azt jelenti, hogy

(\binom{n}{k})

paritása megegyezik az

n

elem közül kiválasztható nem csonka

k

-elemű részhalmazok számának a paritásával. Ha egy

k

-elemű részhalmaz nem csonka, akkor tetszőleges

i

-re vagy minden

i

-színű elemet tartalmaz vagy pedig egyet sem. Egy nem csonka

k

-elemű részhalmaz elemszáma tehát bizonyos egyszínű részhalmazok elemszámának, azaz különböző

2

-hatványoknak az összege. Mivel tetszőleges

k

egyértelműen írható fel ilyen számok összegeként ‐ ez éppen a

k

kettes számrendszerbeli alakja ‐ ezért adott

k

esetén legfeljebb egy nem csonka részhalmaz létezhet és ez is csak akkor, ha minden olyan

2

-hatvány, ami a

k

kettes számrendszerbeli alakjában szerepel, előfordul az

n

kettes számrendszerbeli alakjában is.
Azt kaptuk, hogy

(\binom{n}{k})

pontosan akkor páratlan, ha az

n

-et és a

k

-t kettes számrendszerben felírva mindazokon a helyiértékeken, ahol a

k

-ban 1-es áll, az

n

-ben is 1-es áll.
Feladatunk állítása innen nyilvánvalóan adódik, hiszen ha

(\binom{n}{k})

minden

0 ≦ k ≦ n

esetén páratlan, akkor az

n

kettes számrendszerbeli alakja nem tartalmazhat

0

számjegyet.