Feladat:	1996. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1997/február, 68 - 69. oldal		PDF  |  MathML
Témakör(ök):	Kombinatorika, Variációk, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 1997/február: 1996. évi Kürschák matematikaverseny 2. feladata

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. Legyen a küldöttségek létszáma $n$. Az $A$ országbeli minden csoporthoz hozzárendelünk egy zérusokból és egyesekből álló $n$-elemű sorozatot; ennek a $j$-edik eleme $0$, ha a $B$-beli küldöttség $j$-edik tagja páros számú embert ismer a csoportból, és 1, ha páratlan számút ismer. Így egyrészt $2^n$ különböző sorozat keletkezhet, másrészt $2^n-1$ különböző csoport választható ki az $A$-beli küldöttségből. Ha mindegyik csoporthoz különböző sorozat tartozik, akkor tehát a $\left(\mathrm{0,}\mathrm{0,}\text{...}\mathrm{,}0\right)$ és az $\left(\mathrm{1,}\mathrm{1,}\text{...}\mathrm{,}1\right)$ legalább egyike előfordul, vagyis az a) és b) lehetőségeknek legalább egyike teljesül. Ha van két különböző csoport, amelyikhez ugyanaz a sorozat tartozik, akkor vegyük azokat a küldötteket, akik az elsőben benne vannak, a másodikban nincsenek benne, továbbá azokat, akik az elsőben nincsenek benne, a másodikban benne vannak. Mivel a két csoport különböző, elhagyva azokat (ha vannak), akik mindkét csoporthoz hozzátartoznak, legalább egy $A$-beli küldött marad. Ekkor minden $B$-beli küldött első csoportbeli ismerőseinek a száma ugyanannyival változik, mint a másodikbeli ismerőseinek a száma, a két megmaradt részcsoportbeli küldött ismerőseinek az együttes száma tehát páros. Az így keletkezett csoportra ekkor az a) lehetőség teljesül.   II. megoldás. A küldöttségek létszáma ($n$) szerinti teljes indukcióval bizonyítjuk a feladat állítását. Egytagú küldöttségek esetén az $A$-beli küldöttet vagy ismeri a $B$-beli küldött, vagy nem. Ennek megfelelően a b) vagy az a) lehetőség teljesül. Tegyük most fel, hogy $n$-tagú küldöttségek esetén igaz a bizonyítandó állítás, és tekintsünk két $\left(n+1\right)$-tagú küldöttséget. Az $A$-beli küldöttség tagjait jelöljük $a_i$-vel, a $B$-beli tagjait $b_i$-vel, $i=1$, $2$, $\text{...}$, $n+1$. Hagyjuk egyelőre figyelmen kívül $b_{n+1}$-et. Ha sorra figyelmen kívül hagyjuk $a_1$-et, $a_2$-t, $\text{...}$, $a_{n+1}$-et, akkor a megmaradók közül mindig van legalább egy jó kiválasztás, tehát olyan, amelyikhez vagy az $n$-darab 0-ból álló sorozat, vagy az $n$ darab 1-ből álló sorozat tartozik. Ezek a jó kiválasztások az $\left(n+1\right)$-tagú küldöttségből is kiválasztások. Közülük egyesek állhatnak ugyanazokból az $A$-beli küldöttekből, de nem kaphattuk mindegyik esetben ugyanazt a csoportot, mert mindegyik $A$-beli küldöttet figyelmen kívül hagytuk egyszer. Vegyünk két különböző jó kiválasztást. Ha valamelyikből $b_{n+1}$ is ugyanolyan párosságú embert ismer, mint a küldöttsége többi tagjai, akkor a csoportra teljesül a megfelelő lehetőség az egész $B$-beli küldöttséget véve is tekintetbe. Ha nem ez a helyzet, és mind a két csoporthoz az $n$ darab $c$-ből álló sorozat tartozik, ahol $c$ vagy $0$, vagy $1$, akkor a $b_{n+1}$-hez tartozó szám mind a két csoport esetében $1-c$. Ha a két csoporthoz különböző $n$-elemű sorozatok tartoznak, akkor $b_{n+1}$ az egyik csoportból páratlan számú embert ismer, a másikból páros számút, csak fordított sorrendben, mint a többiek. Vegyük azokat az $A$-beli embereket, akik valamelyik csoportban benne vannak, de nem mind a kettőben. Ekkor minden $B$-beli embernek ugyanannyival változik az első csoportbeliek közti ismerőseinek a száma, mint a második csoportbeliek közöttieké. Így a megmaradottak között az első esetben minden $b_i$-nek összesen páros számú ismerőse van, beleértbe $b_{n+1}$-et is; a második esetben viszont minden $B$-beli küldöttnek, $b_{n+1}$-nek is páratlan számú ismerőse van. Található tehát jó kiválasztás $\left(n+1\right)$-tagú küldöttségek esetében is. Ez a tulajdonság tehát öröklődik, így akárhány tagú küldöttségre fennáll.