|
Feladat: |
F.2526 |
Korcsoport: 18- |
Nehézségi fok: átlagos |
Megoldó(k): |
Bán Rita , Beke T. , Bóna M. , Boros Z. , Csizmadia Gy. , Deák Csaba , Dinnyés Enikő , Edvi T. , Fülöp T. , Grallert Ágnes , Heller Judit , Hetyei Judit , Íjjas Cs. , Kocsis 443 Katalin , Kós G. , Licsik I. , Ligeti Z. , Limbek Cs. , Majzik I. , Makay G. , Montágh B. , Olasz-Szabó M. , Pfeil T. , Pintér A. , Regős G. , Ribényi Á. , Sobor G. |
Füzet: |
1986/november,
361 - 362. oldal |
PDF | MathML |
Témakör(ök): |
Összefüggések binomiális együtthatókra, Kombinatorikai leszámolási problémák, Kombinációk, Variációk, Számsorozatok, Teljes indukció módszere, Feladat |
Hivatkozás(ok): | Feladatok: 1985/április: F.2526 |
|
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. Próbáljunk jelentést tulajdonítani az egyenlőség két oldalán álló mennyiségeknek! Tekintsük ehhez az hosszúságú 0‐1 sorozatokat. Azoknak a sorozatoknak a száma, amelyek pontosan darab 1-est tartalmaznak, éppen , az 1-esek helyét ugyanis ennyiféleképpen választhatjuk meg. Az egyenlőség bal oldalán eszerint azoknak az hosszúságú 0‐1 sorozatoknak a száma áll, amelyek pontosan darab azaz legfeljebb darab 1-est tartalmaznak. Vegyük most szemügyre a jobb oldalon álló összeg egy tagját. Az első tényező, azoknak az hosszúságú 0‐1 sorozatoknak a száma, amelyek darab 1-est tartalmaznak. Ami a második tényezőt illeti, összesen darab hosszúságú 0‐1 sorozat van. A szorzat így azoknak az hosszúságú 0‐1 sorozatoknak a száma, amelyekben az első helyen éppen darab 1-es fordul elő. Ha minden egyes ilyen sorozatban az -edik helyre egy 0-t illesztünk, akkor olyan, most már hosszúságú sorozatokat kapunk, amelyekben legfeljebb darab 1-es van, az első elem között pontosan , az utolsó elem között pedig legfeljebb . Az utólag beillesztett 0 pedig éppen az -adik 0 a sorozatban. Csoportosítsuk tehát aszerint a legfeljebb darab 1-est ‐ és így legalább darab 0-t ‐ tartalmazó hosszúságú 0‐1 sorozatokat, hogy az -adik 0 hányadik helyen fordul elő a sorozatban. Ennek a 0-nak a pozíciója -tól -ig változhat, tekintsük azt az esetet, amikor ez épp az -edik elem . Ekkor az ezt a 0-t megelőző elem között darab 0 és így darab 1-es van, az utolsó elem mindegyike lehet 0 vagy 1, az ilyen sorozatok száma tehát valóban . Így az összes olyan 0‐1 sorozatok száma, amelyek legfeljebb darab 1-est tartalmaznak, valóban II. megoldás. Az -re vonatkozó teljes indukcióval bizonyítjuk az állítást. Ha , akkor a bizonyítandó egyenlőség minden -re az 1=1 alakot ölti, ha pedig , akkor ugyancsak minden -re a bal oldal a jobb oldal pedig | | az állítás tehát minden -re igaz, ha vagy . Innen következik, hogy és esetekben fennáll (1). Tegyük most fel, hogy és az állítás -re igaz. Ekkor az és az párokra értelmes és igaz az (1) egyenlőség, azaz
A (3) összefüggés bal oldala alakban is írható. Ha összeadjuk a két egyenlőséget, és felhasználjuk az , illetve az összefüggéseket, akkor éppen a bizonyítandó állítást kapjuk.
Megjegyzés. A legtöbb megoldás -ra vonatkozó teljes indukciót használt. Volt, aki észrevette, hogy az összefüggés fennáll az (1) két oldalán szereplő mennyiségekre és így a kezdeti értékek egyenlőségéből következik az állítás.
|
|