Kezdőlap


Feladat:	F.2892	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	1993/január, 15 - 16. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Részhalmazok, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1992/február: F.2892

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.

Ha $n \leq k$ , akkor a jobb oldalon $\sum_{i = 0}^{n} (\binom{n}{i}) = 2^{n}$ áll, ami éppen az $n$ elemű halmaz összes részhalmazainak a száma, ekkor (1) nyilvánvalóan teljesül. Feltehetjük tehát, hogy $n > k$ .
Az állítást $n$ szerinti teljes indukcióval igazoljuk. Ha $n = 1$ , akkor $k$ csak $1$ lehet, így előbbi megjegyzésünk szerint fennáll a kívánt egyenlőség.
Tegyük fel, hogy az állítás igaz $n - 1$ -re. Megmutatjuk, hogy akkor $n$ -re is igaz.
Legyen $x$ az $n$ elemű halmaz egyik eleme. Tekintsük a megadott részhalmazok közül azokat, amelyek tartalmazzák $x$ -et. Ha $x$ -et mindegyikből elhagynánk, akkor ezek egy $(n - 1)$ -elemű halmaz részhalmazai lennének, és közülük bármely két különbözőnek $(k - 1)$ -nél kevesebb közös eleme lenne, mert $x$ is közös elem volt eredetileg. Ezért az indukciós feltevés szerint ezen halmazok száma legfeljebb

\begin{matrix} m_{1} = \sum_{i - 0}^{k - 1} (\binom{n - 1}{i}) . \end{matrix}

(Ez akkor is igaz, ha

k = 1

).
Tekintsük most azokat a megadott részhalmazokat, amelyek nem tartalmazzák

x

-et. Ezek egy

x

-et nem tartalmazó,

n - 1

elemű halmaznak is részei, tehát az indukciós feltevés alapján számuk legfeljebb

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

Az összes megadott részhalmazok száma pedig nyilván legfeljebb

m_{1} + m_{2}

, azaz

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

Ezzel az állítást igazoltuk.

Megjegyzések. 1. Ha a megadott halmazok az

n

elemű halmaz legfeljebb

k

elemű részhalmazai, akkor (1)-ben egyenlőség áll, tehát az állítás éles.

2. Ha egy

n

elemű halmaz bizonyos részhalmazairól csupán annyit követelünk meg, hogy közülük bármelyik kettő (különböző) közös elemeinek száma legfeljebb

k

-féle lehet, akkor ezen részhalmazok száma legfeljebb

\sum_{i = 0}^{k} (\binom{n}{i})

. Ennek a ‐ Ray-Chaudhusi és Wilson néven ismert ‐ tételnek a bizonyítása azonban az ismertetett megoldásnál lényegesen nehezebb.