|
Feladat: |
1968. évi Kürschák matematikaverseny 3. feladata |
Korcsoport: 18- |
Nehézségi fok: nehéz |
Megoldó(k): |
Bajmóczy Ervin , Lempert László , Michaletzky György , Ruzsa Imre , Soltész János , Somorjai Gábor , Soós Miklós , Takács László |
Füzet: |
1969/november,
99 - 102. oldal |
PDF | MathML |
Témakör(ök): |
Kombinatorika, Egyéb szinezési problémák, Kombinatorikai leszámolási problémák, Kombinációk, Binomiális együtthatók, Összefüggések binomiális együtthatókra, Halmazok számossága, Maradékos osztás, Kürschák József (korábban Eötvös Loránd) |
Hivatkozás(ok): | Feladatok: 1969/január: 1968. é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. Harmadik feladat. Minden lehetséges módon elrendezünk egy sorban fehér és fekete golyót. Minden elrendezésben megállapítjuk a színváltások számát. Bizonyítsuk be, hogy ugyanannyi elrendezésben van színváltás, mint ahányban színváltás .
I. megoldás. Kiszámítjuk, hogy hány golyóelrendezésben van színváltás. Két esetet különböztetünk meg aszerint, hogy páratlan-e, avagy páros.
Első eset. Ha páratlan, legyen . A golyóelrendezés szakaszainak mondjuk a más színű golyók által közrefogott egyszínű golyókat. Minthogy a színváltások száma , a szakaszok száma , tehát fehér és ugyanannyi fekete szakasz van. Ha az fehér szakaszt összetoljuk, az fehér golyó sorában szakaszhatár helyezkedik el. Ezek az golyó sorában található golyóközből közt jelölnek ki. A fekete golyókról ugyanígy elmondhatjuk, hogy golyóelrendezésünk az fekete golyó sorát szakaszra bontja fel, azaz e sor golyóköze közül közt jelöl ki (a 3. ábra 1. részének első két sora szemlélteti a mondottakat egy olyan golyóelrendezésre, amelynél és , tehát . 3. ábra Ilyen módon minden vizsgált golyóelrendezés két elemből alkotott -ad osztályú kombinációt szolgáltat. Két-két golyóelrendezés azonban ugyanazt a kombinációpárt adja, ti. azok, amelyekben mind a fehér, mind a fekete szakaszok hossza és elrendezése ugyanaz, csak éppen az egyik fehér, a másik pedig fekete szakasszal kezdődik. Akárhogyan választunk is meg egy kombinációpárt, tehát bontjuk szakaszra a fehér golyók sorát és a fekete golyók sorát is, e szakaszokat váltogatva sorbarakhatjuk és olyan golyóelrendezést kapunk, amelyben színváltás van. Ezt a sorbarakást kétféleképpen végezhetjük el, mert az elrendezést fehér szakasszal vagy fekete szakasszal kezdhetjük. Ezek szerint a színváltású golyóelrendezések száma a mondott két kombináció megválasztási lehetőségei számának kétszerese. Minthogy mindegyik kombináció -féleképpen választható meg, a színváltású golyóelrendezések száma Ha a feladatban szereplő szám páratlan, akkor páratlan is, hiszen a két szám különbsége, páros. Eredményünk tehát mindkét esetben alkalmazható, és esetben az eredmény, ahol mintájára határozza meg értékét. Ezek szerint , és a binomiális együtthatók jól ismert tulajdonsága szerint ami a fentiek szerint a kapott két eredmény egyenlőségét, tehát páratlan esetére a feladat állításának helyességét mondja ki.
Második eset. Ha páros, legyen . Az első esethez hasonlóan járunk el, a golyóelrendezést ismét szakaszokra bontjuk fel, és most szakaszhoz jutunk. Ha az elrendezés fehér szakasszal kezdődött, akkor fehér és fekete szakasz van. Egyelőre figyelmen kívül hagyjuk a fekete szakasszal kezdődő elrendezéseket, amelyekről a színeket felcserélve hasonlót mondhatunk el. Ha az fehér és fekete szakaszt összetoljuk, az fehér golyó sorának köze közül helyen, a fekete golyók sorának köze közül pedig helyen van szakaszhatár (a mondottakat a 3. ábra 2. részének első két sora szemlélteti egy olyan golyóelrendezésre, amelynél és , tehát . Az első eset mintájára elmondhatjuk most, hogy annyi színváltású golyóelrendezés van, ahányféleképpen két elemű halmaz egyikéből elemet, másikából pedig elemet kiválaszthatunk, megengedve, hogy a két halmaz szerepet cseréljen. Itt a golyóelrendezések és a kombinációpárok egymáshoz rendelése kölcsönösen egyértelmű, az első szakasz színének megválasztása nem okoz kétféleséget, mert ha pl. -gyel több a fehér, mint a fekete szakasz, akkor a sorbarakásukat fehér szakasszal kell elkezdenünk. A színváltású golyóelrendezések száma tehát ahol a -es szorzó az említett szerepcsere miatt lép fel. Ha a feladatbeli , akkor is páros: . Az színváltású elrendezések száma tehát Minthogy most , a binomiális együtthatók már említett tulajdonsága szerint | | a kapott két számosság tehát páros esetében is egyenlő.
II. megoldás. A feladat két halmaz számosságának egyenlőségét mondja ki. Első megoldásunkban megszámláltuk mind a két halmazt és konstatáltuk a két eredmény egyenlőségét. Most megszámlálás nélkül bizonyítjuk a két számosság egyenlőségét oly módon, hogy a két halmaz elemei között kölcsönös egyértelmű hozzárendelést létesítünk. Ilyen hozzárendelés természetesen csak akkor létesíthető, ha mindkét halmazban ugyanannyi elem van. Eljárásunk ennyiben eltér az első megoldásétól, viszont lényegében mégis azzal azonos, mert annak alapja a kombinációs együtthatók tulajdonsága volt, s ennek alkalmazása helyett dolgozhatunk a kombinációknak azzal az egymáshoz rendelésével, amely az említett tulajdonságot szolgáltatja, ha ti. az elemből kiválasztott -adosztályú kombinációhoz hozzárendeljük az imént ki nem választott elemből álló kombinációt. Ezzel második megoldásunkat lényegében már elő is adtuk, csak egyes részletek tisztázására van még szükség. Egy színváltásos golyóelrendezés az első megoldás előírása szerint az egyszínű szakaszok összetolása révén az fehér golyóból és az fekete golyóból álló golyósor szakaszokra bontását határozza meg. Új szakaszokra bontáshoz jutunk, ha ott helyezünk el szakaszhatárokat, ahol az imént nem volt szakaszhatár. Az így kapott szakaszokat váltakozó színekkel sorbarakjuk és új golyóelrendezéshez jutunk. Ez a hozzárendelés azonban ‐ mint az első megoldásban is láttuk ‐ nem egyértelmű, ha ugyanannyi fehér és fekete szakasz van. Ez páratlan esetén következik be, s ekkor az új elrendezés számára is ugyanannyi fehér és fekete szakasz adódik. Ezt a zavaró kétféleséget megszüntethetjük azáltal, hogy páratlan esetében megállapodunk abban, hogy egy elrendezésből származtatott új elrendezés pl. ugyanolyan színű szakasszal kezdődjék, mint amilyennel az eredeti kezdődött. (Az új elrendezés származtatását a 3. ábra mutatja be két esetben.) Az így létesített hozzárendelés minden színváltású golyóelrendezéshez egy-egy színváltásút rendel, mert az fehér golyó sorában található köz és az fekete golyó sorában található köz, összesen tehát köz közül helyen volt szakaszhatár, s ezért az új szakaszkijelöléskor szakaszhatárt helyeztünk el, így a két -elemű golyósorban együttesen szakaszvég és ugyanennyi szakasz keletkezett, s a váltakozó színekkel történő összerakás valóban színváltású elrendezést adott. Ugyanaz az előírás, amely egy színváltású elrendezésből egy színváltáshoz vezetett, egy ilyenből visszavezet az eredeti színváltásúhoz. Ez biztosítja, hogy valamennyi színváltású elrendezés halmaza és valamennyi színváltású elrendezés halmaza között kölcsönös egyértelmű hozzárendelést létesítettünk. A két halmaz tehát egyenlő számosságú. |
|