Feladat: 1986. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Benczúr András [1983-1987] ,  Bereczky Áron ,  Bóna Miklós ,  Bordás Ferenc ,  Csom Gyula ,  Cynolter Gábor ,  Kós Géza ,  Lipták László ,  Mándy Attila ,  Montágh Balázs ,  Rimányi Richárd ,  Szabó Gábor ,  Tóth Gábor 
Füzet: 1987/február, 60 - 62. oldal  PDF  |  MathML 
Témakör(ök): Játékelmélet, játékok, Többszemélyes véges játékok, Maradékos osztás, Oszthatóság, Kombinatorikai leszámolási problémák, Kombinációk, Binomiális együtthatók, Teljes indukció módszere, Egész együtthatós polinomok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1987/február: 1986. évi Kürschák matematikaverseny 3. 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. Az első 100 pozitív egész szám közül kiválasztható k-asok közül úgy választunk ki csoportokat, ameddig tudunk, hogy egy-egy csoportban ugyanannyinak az összege legyen páros, mint amennyié páratlan. Válasszuk ki először azokat, amelyekben szerepel vagy az 1 vagy a 100, de nem mind a kettő. Ezeket párokba állíthatjuk úgy, hogy az első 98 szám közül kiválasztott egy-egy k-1-eshez egyszer az 1-et, egyszer a 100-at vesszük k -adiknak. Ekkor minden pár egyik k-asának az összege páros, a másiké páratlan.
A maradó k-asok közül vegyük azokat, amelyek a 2 és a 99 közül az egyiket tartalmazzák, a másikat nem. Ezek közül is ugyanannyinak az összege páros, mint amennyié páratlan, az előbbi gondolatmenet szerint. Az eljárást tovább ismételjük a 3,98, a 4,97, ..., az 50,51 párral. Ezután már csak olyan k-asok maradnak meg, amelyek a kiválasztáshoz használt párok közül bizonyosaknak mindkét eleméből tevődnek össze. Ilyenek csak páros k esetén vannak, tehát páratlan k esetén A-nak és B-nek egyenlő esélye van a nyerésre.
Páros k esetén azok a k-asok maradnak meg, amelyek az említett 50 pár közül k/2-nek mindkét eleméből állnak. Mivel mindegyik pár két elemének összege 101, tehát páratlan szám, így mindegyik fennmaradt k-as elemeinek összege páros, ha k/2 páros és páratlan, k/2 páratlan. Ezek szerint A-nak nagyobb a nyerési esélye, ha k osztható 4-gyel, ha viszont k4-gyel osztva 2 maradékot ad, akkor B esélye nagyobb a nyerésre.
 

Megjegyzések. 1. Az elmondottak alapján ki is számíthatjuk, ki hány esetben nyer. A kiválasztható k-asok száma (100k) és, ha k páros, akkor (50k/2)-vel több esetben nyer az egyik játékos, mint a másik. Így páratlan k esetén mindegyikük
12(100k)
esetben nyer, páros k esetén pedig az egyikük és másikuk számára kedvező esetek száma
12((100k)-(50k/2)),ill.12((100k)+(50k/2)).

2. Az eljárás alkalmazható akkor is, ha 100 helyett bármilyen páros N számot mondunk. A válasz ekkor is ugyanaz, mint a 100 esetében volt. Ha páratlan N számot veszünk 100 helyett, akkor már sohasem egyenlők a nyerési esélyek. Ilyenkor 1 és N-1, majd 2 és N-2,3 és N-3 és így tovább, ismét használhatók egyenlő esélyt adó k-asok kiválasztására. A fennmaradó k-asok közül külön kell foglalkozni azokkal, amelyekben előfordul az N. A részletek végiggondolását az olvasóra bízzuk. B-nek nagyobb a nyerési esélye, ha k4-gyel osztva 1 vagy 2 maradékot ad, különben A-nak.
 

II. megoldás. Vizsgáljuk az 1, 2, ..., 2N számok közül kiválasztható k-asokat. Jelöljük D(N,k)-val a páros, illetve a páratlan összegű k-asok számának a különbségét. Erre a függvényre állapítunk meg egy rekurzív összefüggést. Legyen k≦2N-2. Csoportosítsuk a k-asokat aszerint, hogy hány számot tartalmaznak a (2N-1,2N) párból. Az első csoportba tartozzanak azok a k-asok, amelyek tartalmazzák mind a kettőt, a másodikba azok, amelyek egyiket sem tartalmazzák, a harmadikba pedig azok, amelyek az egyiket tartalmazzák, a másikat nem.
A harmadik csoportbeli k-asoknak k-1 eleme nem nagyobb 2N-2-nél, és minden ilyen k-1-es a 2N-1-gyel és a 2N-nel is k-assá egészíthető ki. Az elemek összege a két k-as közül az egyikben páros, a másikban páratlan. A harmadik csoportban tehát ugyanannyi páros összegű k-as van, mint páratlan összegű, így ezek járuléka D(N,k) értékéhez 0.
A második csoport k-asai csupa 2N-2-nél nem nagyobb számból állnak, ezek tehát D(N-1,k)-t adnak D(N,k) értékéhez.
Az első csoport minden k-asa k-2 elemet tartalmaz, amelyek nem nagyobbak 2N-2-nél, továbbá a 2N-1-et és a 2N-et. Az első k-2 elem összegét tekintve a vizsgált különbség D(N-1,k-2). A k-asokban még 2N-1+2N, tehát páratlan szám adódik az összeghez, így annak párossága az ellenkezőjére változik. Az első csoport k-asai, tehát -D(N-1,k-2)-vel járulnak hozzá D(N,k) értékéhez. Ezzel a következő összefüggést kaptuk:
D(N,k)=D(N-1,k)-D(N-1,k-2).(3)
Az összefüggés k=2N-1-re és k=2N-re is helyes, ha megállapodunk abban, hogy ha k>2N, akkor D(N,k) jelentsen 0-t.
Ennek alapján teljes indukcióval igazoljuk a következő állítást: D(N,k) pozitív, ha k osztható 4-gyel, negatív, ha k páratlan szám kétszerese, és 0, ha k páratlan. Belátjuk először, hogy ez k=1,2,3 és 4-re igaz. (2N tetszőleges, k-nál nem kisebb páros szám.)
k=1-re N páros szám van az adottak közt és N páratlan, így D(N,1)=0. Párokat választva ki, akkor lesz az összeg páros, ha vagy mind a két szám páros, vagy mind a kettő páratlan, és akkor lesz páratlan, ha az egyik szám páros, a másik páratlan. Az előbbi és az utóbbi típusú párok száma 2(N2)=N(N-1), ill. N2, tehát D(N,2)=-N<0. Ezek az értékek N=1-re is helyesek.
Három szám összege páros, ha mindegyik szám páros, vagy egyikük páros, a másik kettő páratlan; viszont páratlan az összeg, ha mindegyik szám páratlan, vagy ha egyikük páratlan, a másik kettő pedig páros. Mivel a páros és páratlan számok száma egyenlő, így a kétféle hármasok száma is megegyezik, tehát
D(N,3)=0.

Ha k=4, akkor páros összeget kapunk, ha mind a 4 páros, vagy mind a 4 páratlan, vagy közülük 2 páros, 2 páratlan. Páratlan lesz az összeg, ha a 4 szám között 1 páratlan van, vagy ha 1 páros van. Az egyik-, ill. másikféle esetek száma

2(N4)+(N2)2=N(N-1)(N-2)(N-3)12+N2(N-1)24==N(N-1)(2N2-4N-3)6,
illetőleg
2N(N3)N2(N-1)(N-2)3=N(N-1)(2N2-4N)6;
N=2 esetén az esetek száma 1, ill. 0. Eszerint
D(N,4)=n(N-1)2>0.

A vizsgált k értékek esetén tehát minden szóba jövő N-re igaz az állítás. Ekkor egyszersmind N=1 és N=2-re minden szóba jövő k esetén igaz az állítás.
Tegyük most fel, hogy M>2, K>4 és igaz az állítás, ha k<K, továbbá az M-nél kisebb N-ekre tetszés szerinti szóba jövő k mellett. A (3) összefüggés szerint
D(M,K)=D(M-1,K)-D(M-1,K-2).
Ha K páratlan, akkor K-2 is, így feltevés szerint a jobb oldal mindkét tagja 0, tehát D(M,K) is az. Ha K páros, akkor K-2 is, és feltevés szerint D(M-1,K), ha nem 0 (ti. ha M=K), ellenkező előjelű, mint D(M-1,K-2). Az indukciós feltételből az is következik, hogy D(M-1,K-2) nem 0. Azt kaptuk tehát, hogy D(M,K) sem 0, és ellenkező előjelű, mint D(M-1,K-2). Ez azonban azt jelenti, hogy az állítás helyessége öröklődik M és K-ra. A kimondott állítás tehát minden szóba jövő N,k értékpárra igaz.
 

Megjegyzések. 1. Felesleges volt D(N,3) és D(N,4) kiszámítása, mert az indukciós bizonyítás már ezekre is adja az állítás helyességét. Jónak láttuk azonban mind a 4 lehetséges esetre bemutatni egy-egy példát. Aki nem tartja erőszakoltnak a k=0 eset megengedését, ezt tekintheti a k=2 helyett további egyszerűsítésként.
2. A teljes indukciónak itt egy ritkábban előforduló esetével találkoztunk, a két változó szerint egyidejűleg futó teljes indukcióval, hiszen mikor M-re és K-ra bizonyítottuk az öröklődést, fel kellett használnunk azt is, hogy M-1-re és ugyanerre a K-ra igaz az állítás. Így tulajdonképpen a k=2 eset után k=3-ra és minden N-re, majd K=4-re és így tovább adódik az állítás helyessége. Ehhez viszont kell az, hogy a legkisebb N értékre minden szóba jövő k esetén igaz legyen az állítás. Esetünkben ez mindössze az N=1, k=1,2 eseteket jelentette. Annyiban is speciális volt ez a bizonyítás, hogy M-re a K-nál kisebb k-kra nem volt szükséges felhasználnunk az indukciós feltevést.
 

III. megoldás. Az előző megoldásban bevezetett jelöléssel D(50,k)-t kapcsolatba hozhatjuk az
1+(-1)cx,c=1,2,...,100
elsőfokú polinomok szorzatával. Ebben úgy kapjuk a k-adfokú tagokat, hogy k tényezőből az x-es tagot vesszük, a többiből az 1-et, ezeket összeszorozzuk és az összes ilyen tagot összeadjuk. Egy-egy ilyen tagban xk együtthatója -1-nek a c1+c2+...+ck-adik hatványa, ahol az összeadandók különböző, 100-nál nem nagyobb egészek. Az együttható tehát 1, ha az összeg páros, -1, ha az összeg páratlan. Eszerint xk együtthatója a szorzatban éppen D(100,k).
A szorzat másfelől felváltva 1+x és 1-x tényezők szorzata, vagyis
(1-x2)50=1-50x2+...+(-1)j(50j)x2j+...+x100.
Eszerint egyenlők a nyerési esélyek, ha k páratlan, (50j)-vel több esetben nyer A, mint B, ill. B, mint A, ha k=2j és j páros, ill. páratlan.
 

Megjegyzés. Az F(k)=D(100,k) függvényt úgy sikerült meghatároznunk, hogy hozzárendeltük az
F(x)=1+f(1)x+f(2)x2+...+f(100)x100
polinomot, amit sikerült más alakba írni és abból f értékeit meghatározni. F-et az f generátor függvényének nevezzük. A generátorfüggvény gondolata és számos érdekes alkalmazása Leonhard Euler (1707‐1783) rendkívül termékenynek bizonyult felfedezése, ami a matematika számos ágában alapvető szerepet kapott. Feladatunkban alkalmazható 100 helyett tetszés szerinti N számra és az I. megoldáshoz fűzött 2. megjegyzésben kimondott eredményre vezet. A számolás elvégzését az olvasóra bízzuk.