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. Elegendő a sorrendeknél csak arra tekintettel lenni, hol állnak lányok, hol fiúk, hiszen ha már ki vannak jelölve a ,,lányhelyek'' és a ,,fiúhelyek'', akkor mindig ugyanannyiféleképpen tudjuk elrendezni a lányokat a lányhelyeken, és a lányok elhelyezésétől függetlenül ugyanannyiféleképpen a fiúkat a fiúhelyeken. A megoldásokban ezért csak a fiú‐lány sorrendek számával foglalkozunk. Nevezzük azokat a sorrendeket, amelyek nem vághatók a feladatokban leírt módon ketté, -típusúnak, azokat, amelyeknek egy ilyen kettévágásuk van, -típusúnak.
I. megoldás. Jelöljük az első helyen álló tanulót és a vele egyező neműeket -szel, a másik nemű tanulókat -nal. Ha lány és fiú van az osztályban, akkor eszerint darab -nek és darab -nak az -szel kezdődő sorrendjeit kell vizsgálnunk. Minden ilyen sorrendhez a fiúknak és lányoknak két sorrendje tartozik, az egyik, amelyikben -et fiúnak és -t lánynak értelmezzük, és a másik a fordított értelmezéssel keletkező. Egy -szel kezdődő -típusú elrendezésben bármely betűig ‐ az utolsó kivételével ‐ legalább eggyel több fordul elő, mint , hiszen a két betű előfordulásszáma közti különbség betűről betűre haladva eggyel változik, tehát ha -szel kezdődik a sor, akkor az -ok csak úgy kerülhetnének túlsúlyba, ha előzőleg egyenlővé vált volna az -ek és -ok száma. Ez azonban -típusú elrendezésben csak az utolsó betűnél következhet be. Egy -típusú elrendezés a kettévágásnál két -típusúra bomlik szét. Ezek közül az első -szel kezdődik, a második azonban kezdődhet -szel is, -nal is. Azok, amelyekben a második rész is -szel kezdődik, a -típusú elrendezések felét teszik ki, mert ezek második részében felcserélve az -eket és -okat, minden sorrendet megkapunk és mindegyiket csak egyszer. A feladat állítását tehát bebizonyítjuk, ha az -szel kezdődő -típusú elrendezéseket egyértelműen összepárosítjuk az olyan -típusúakkal, amelyeknek mindkét -típusú része -szel kezdődik. Egy kívánt hozzárendelés történhet úgy, hogy a -típusú elrendezés második -típusú részének élén álló -et a sor legelejére állítjuk. Ezáltal -típusú elrendezést kapunk, ugyanis a -típusú elrendezés első -típusú részében, mint láttuk, egy tetszőleges betűig, az utolsó kívételével, legalább eggyel több van, mint . Az egész elé téve egy -et, a második betűtől kezdve tehát legalább -vel több lesz mint , egészen amíg az első -típusú rész utolsó betűjéig nem érünk. Ez a betű a második -típusú rész első betűje helyére került. Idáig eggyel több az -ek száma, mint az -oké. A további betűket ugyanazok a betűk előzik meg, amelyek a -típusú elrendezésben megelőzték, így megint több lesz, mint , egészen az utolsó betűig. A meggondolásból azt is látjuk, hogy fordítva egy -típusú sorrendben a második olyan betűt kell megkeresni, ameddig eggyel több szerepel, mint , és ez után helyezni a sor elejéről az első -et. Ezáltal -szel kezdődő sorrendet kapunk, mert ha az -típusú elrendezésben az első -et egy követné, akkor mindjárt az után ketté lehetne vágni a sorrendet, hiszen legalább négy betűből áll a sor. Az első elvételével az -ek és -ok számának a különbsége -gyel csökken, amíg el nem érjük az áthelyezett betű új helyét. Mivel az előtt volt ez a különbség, most -ra csökken, mégpedig itt először. Itt tehát kettévágható a sorrend, előbb azonban nem. Tovább megint az -ek lesznek túlsúlyban, mig a sor végére nem érünk, hiszen az új helyén túl minden betűig ugyanazok a betűk vannak a módosított sorrendben is, mint az eredetiben. Ezzel a kívánt párosítást elvégeztük, s így a feladat állítását igazoltuk.
Megjegyzések. 1. Jelöljük a fiú és lány -, ill. -típusú sorrendjeinek számát -val , ill. -val . Egy -típusú elrendezést csak páros számú betű után lehet kettévágni. Az olyan elrendezések száma, amelyben ez a -adik betű után történik , mert egy betűből álló, -szel kezdődő -típusú elrendezést követ egy tetszés szerinti, betűből álló. Így | | A feladatot tehát megoldjuk, ha megmutatjuk, hogy is felírható a jobb oldal formájában, vagy -vel osztva és -t -vel jelölve | | (1) |
2. Tuza Zsolt, dolgozatában a következő probléma közvetítésével látja be fennállását: ,,Hányféleképpen lehet egy kör (v. bármely konvex zárt vonal) mentén elhelyezett pontot úgy összepárosítani, hogy a párokat összekötő húroknak ne legyen közös pontja?'' Megmutatja egyfelől, hogy a megfelelő összekötések száma . Az összekötő húrok kisebb indexű végpontjához -et, a nagyobb indexűhöz -t ír, majd sorra leírja az egymás utáni pontok mellé írt betűket és az elejére ír még egy -et, a végére egy -t. Másfelől az első pontból induló átló két zárt vonalat képez a körből. Az egyikre és a másikra eső pontok külön‐külön egymást nem metsző húrokkal vannak összekötve. (Megegyezünk abban, hogy pont összekötéseinek számán -et értünk.) Ez a gondolat elvezet az összefüggés igazolásához. A részletek végiggondolását az olvasóra bízzuk. 3. A fenti megszámlálási gondolat megfogalmazható az -típusú elrendezések kettébontásaként az összekötési probléma közbeiktatása nélkül, ugyanis az első pontból induló húr végpontjának az a betű felel meg, amelynél másodszor csökken az addig előforduló -ek és -ok számának különbsége -re. Így az -típusú elrendezéseknek a fenti megoldásban szereplő átalakításához jutunk, csak ezt most nem a -típusú elrendezésekhez való hozzárendelésre használjuk, hanem összeszámláljuk segítségével az -típusú elrendezéseket is ugyanúgy, mint föntebb a -típusúakat. A részletek végiggondolását ismét az olvasóra bízzuk. Ez a meggondolás azt mutatja, hogy az összekötési probléma szellemes közbeiktatása nélkülözhető, és tulajdonképpen a fenti megoldás egy variánsával állunk szemben. 4. Az formula és az kezdő érték módot ad az , s így egyben az , értékek egymás utáni kiszámítására, az , értékek úgynevezett rekurzív meghatározására. Többen egy másik rekurzív meghatározást találtak: Az összes, darab -ből és darab -ból álló sorozatok száma . Ezek közül a nem -típusúak valamilyen -ra a -adik betű után először (esetleg azután még más helyen is) kettévághatók úgy, hogy odáig darab és darab legyen . A vágás előtti rész -típusú, az ilyenek száma , tovább a elem lehetséges elrendezésének bármelyike állhat. Ebből az | | (2) | összefüggés adódik, ami az kezdő értékkel szintén meghatározza az értékeket. Kézenfekvő gondolat volna ezután -et teljes indukcióval megpróbálni bizonyítani felhasználásával, ez azonban nem vezet eredményre. Többen megtalálták vagy megsejtették , meghatározását binomiális együtthatók segítségével. Még ennek ismeretében sem könnyű bizonyítani az azonosság helyességét, a versenyzőknek nem is sikerült. Először mindjárt az első után lesz ez a különbség 1.A kérdést feladatnak kitűzni tervezzük. (Szerk.) |