KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 4091. Prove that

\sum_{k=0}^m \binom mk \binom{t+k}{m} =\sum_{k=0}^m\binom mk\binom tk\cdot2^k

for arbitrary positive integers m, t.

(5 points)

Deadline expired on 15 May 2008.


Google Translation (Sorry, the solution is published in Hungarian only.)

Megoldás: A jobboldali kifejezést könnyebb értelmezni, kezdjük ezzel. Legyen M és T két diszjunkt halmaz úgy, hogy |M|=m és |T|=t. Számoljuk meg, hányféleképpen lehet kiválasztani A,B,C halmazokat úgy, hogy C\subseteq A\subseteq M, B\subseteq T és |A|=|B|. Ekkor nyilván |A|\lem, tehát alkalmas 0\lek\lem számmal |A|=|B|=k, ezen feltétel mellett A és B megválasztására egymástól függetlenül {m\choose k}, illetve {t\choose k} lehetőségünk van, ha pedig A-t és B-t már megválasztottuk, akkor A-n belül C kiválasztására 2k lehetőség van. Ezért a jobboldalon álló összeg a fenti tulajdonságokkal rendelkező (A,B,C) hármasokat számolja össze.

Ugyanezt most számoljuk össze másképpen. Kezdjük C kiválasztásával: ha C elemszáma m-k (ahol 0\lek\lem), akkor erre éppen {m\choose k} különböző lehetőségünk van. Ehhez megfelelő A és B halmazt úgy kapunk, hogy T-ből alkalmas q-val kiválasztunk egy q elemű B részhalmazt, a k elemű M\C halmazból pedig egy m-q elemű részhalmazt választunk ki, amit az M\A halmaznak fogunk fel. Vagyis arról van szó, hogy ha C-t már kiválasztottuk a |C|=m-k feltétel mellett, akkor kölcsönösen egyértelmű megfeleltetést létesíthetünk az adott C-hez tartozó (A,B,C) hármasok és a t+k elemű (M\C)\cupT halmaz m elemű részhalmazai között. Ez a megfeleltetés mutatja, hogy a baloldalon álló összeg is ugyanazokat az (A,B,C) hármasokat számolja össze.


Statistics on problem B. 4091.
30 students sent a solution.
5 points:Bálint Dániel, Bencs 111 Ferenc, Blázsik Zoltán, Bodor Bertalan, Dudás 002 Zsolt, Éles András, Fonyó Dávid, Gévay Gábor, Kiss 243 Réka, Kovács 729 Gergely, Lovas Lia Izabella, Márkus Bence, Muszka Balázs, Nagy 648 Donát, Perjési Gábor, Réti Dávid, Somogyi Ákos, Szalkai Balázs, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Véges Márton, Vincze Ákos, Zelena Réka, Zieger Milán.
1 point:1 student.
0 point:4 students.


  • Problems in Mathematics of KöMaL, April 2008

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley