Kezdőlap


Feladat:	B.4091	Korcsoport: 18-	Nehézségi fok: könnyű
Megoldó(k):	Bálint Dániel , Bencs Ferenc , Blázsik Zoltán , Bodor Bertalan , Dudás Zsolt , Éles András , Fonyó Dávid , Gévay Gábor , Kiss Réka , Kovács Gergely , Lovas Lia Izabella , Márkus Bence , Muszka Balázs , Nagy Donát , Perjési Gábor , Réti Dávid , Somogyi Ákos , Szalkai Balázs , Tossenberger Anna , Tóth László Márton , Varga László , Véges Márton , Vincze Ákos , Zelena Réka , Zieger Milán
Füzet:	2009/május, 286 - 287. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Kombinációk, Konstruktív megoldási módszer, Számelrendezések, Feladat
Hivatkozás(ok):	Feladatok: 2008/április: B.4091

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.

Megoldás. Tekintsünk egy 2 sorból és $t + m$ oszlopból álló üres táblázatot. Nézzük a táblázat azon kitöltéseit, amelyek kielégítik az alábbi feltételeket:

‐	Minden mezőbe vagy egy 1, vagy egy 0 számjegy kerül;

‐	A felső sor első $t$ mezőjébe 1-es kerül;

‐	Ha bárhol a felső sorban egy 0 áll, akkor közvetlenül alatta is 0 van;

‐	Az alsó sorban pontosan $m$ darab 1-es van.

A feladat állításának bizonyításához megmutatjuk, hogy mindkét kifejezés a megfelelő kitöltések számát határozza meg.
Hogyan kaphatunk egy helyes kitöltést?
I. módszer: A felső sor utolsó

m

mezőjébe pontosan

k

helyre 1-es kerüljön, a többi helyre 0 (

0 \leq k \leq m

). Ezt

k

függvényében

(\binom{m}{k})

-féleképpen tehetjük meg. Ebben a sorban ekkor pontosan

t + k

darab 1-es van. Az alsó sor

m

darab 1-ese csak a felső sor

t + k

darab 1-ese alá kerülhet, nekik

(\binom{t + k}{m})

-féleképpen választhatunk helyet. A többi helyre 0 kerül.
Ez adott

k

esetén

(\binom{m}{k}) (\binom{t + k}{m})

kitöltést jelent, összesen

\begin{matrix} \sum_{k = 0}^{m} (\binom{m}{k}) (\binom{t + k}{m}) \end{matrix}

helyes kitöltést, ami a bizonyítandó egyenlőség bal oldalán található kifejezés.
II. módszer: Az alsó sor

m

darab 1-ese közül

k

darabot (

0 \leq k \leq m

) az első

t

oszlopba rakunk, ezt

k

függvényében

(\binom{t}{k})

-féleképpen tehetjük meg.
Az alsó sor utolsó

m

mezőjébe pontosan

m - k

darab 1-es kerül, nekik

(\binom{m}{m - k}) = (\binom{m}{k})

-féleképpen adhatunk helyet.
Az alsó sort

k

függvényében

(\binom{t}{k}) (\binom{m}{k})

-féleképpen tölthetjük ki, a felső sor utolsó

m

mezője viszont még üres.
Közülük pontosan

m - k

mező alatt az alsó sorban 1-es áll, így ebben az

m - k

mezőben is biztosan 1-esek állnak. A többi,

m - (m - k) = k

darab üres mezőt szabadon, összesen

2^{k}

-féleképpen tölthetjük ki.
A

k

függvényében így

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

darab kitöltés létezik, ez összesen

\begin{matrix} \sum_{k = 0}^{m} (\binom{m}{k}) (\binom{t}{k}) \cdot 2^{k} \end{matrix}

helyes kitöltést jelent. Ez pedig a bizonyítandó egyenlőség jobb oldalán található kifejezés.
Ezzel a feladat állítását beláttuk.

Megjegyzés. A fentitől különböző megoldás található Hajnal Péter: Elemi kombinatorikai feladatok c. könyvében (3.17/l, 14. o.), illetve Lovász László: Kombinatorikai problémák és feladatok c. könyvében (§1. 43/a, 20. o.). Azok a diákok, akik csak hivatkoztak erre, de nem írták le a megoldást, a versenykiírás értelmében 0 pontot kaptak.