Kezdőlap


Feladat:	1972. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Győri Ervin , Tuza Zsolt
Füzet:	1973/február, 50 - 53. oldal		PDF \| MathML
Témakör(ök):	Kombinatorika, Kombinatorikai leszámolási problémák, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 1973/január: 1972. é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.

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é, $A$ -típusúnak, azokat, amelyeknek egy ilyen kettévágásuk van, $B$ -típusúnak.

I. megoldás. Jelöljük az első helyen álló tanulót és a vele egyező neműeket

X

-szel, a másik nemű tanulókat

Y

-nal. Ha

n

lány és

n

fiú van az osztályban, akkor eszerint

n

darab

X

-nek és

n

darab

Y

-nak az

X

-szel kezdődő sorrendjeit kell vizsgálnunk. Minden ilyen sorrendhez a fiúknak és lányoknak két sorrendje tartozik, az egyik, amelyikben

X

-et fiúnak és

Y

-t lánynak értelmezzük, és a másik a fordított értelmezéssel keletkező.
Egy

X

-szel kezdődő

A

-típusú elrendezésben bármely betűig ‐ az utolsó kivételével ‐ legalább eggyel több

X

fordul elő, mint

Y

, 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

X

-szel kezdődik a sor, akkor az

Y

-ok csak úgy kerülhetnének túlsúlyba, ha előzőleg egyenlővé vált volna az

X

-ek és

Y

-ok száma. Ez azonban

A

-típusú elrendezésben csak az utolsó betűnél következhet be.
Egy

B

-típusú elrendezés a kettévágásnál két

A

-típusúra bomlik szét. Ezek közül az első

X

-szel kezdődik, a második azonban kezdődhet

X

-szel is,

Y

-nal is. Azok, amelyekben a második rész is

X

-szel kezdődik, a

B

-típusú elrendezések felét teszik ki, mert ezek második részében felcserélve az

X

-eket és

Y

-okat, minden sorrendet megkapunk és mindegyiket csak egyszer. A feladat állítását tehát bebizonyítjuk, ha az

X

-szel kezdődő

A

-típusú elrendezéseket egyértelműen összepárosítjuk az olyan

B

-típusúakkal, amelyeknek mindkét

A

-típusú része

X

-szel kezdődik.
Egy kívánt hozzárendelés történhet úgy, hogy a

B

-típusú elrendezés második

A

-típusú részének élén álló

X

-et a sor legelejére állítjuk.
Ezáltal

A

-típusú elrendezést kapunk, ugyanis a

B

-típusú elrendezés első

A

-típusú részében, mint láttuk, egy tetszőleges betűig, az utolsó kívételével, legalább eggyel több

X

van, mint

Y

. Az egész elé téve egy

X

-et, a második betűtől kezdve tehát legalább

2

-vel több

X

lesz mint

Y

, egészen amíg az első

A

-típusú rész utolsó betűjéig nem érünk. Ez a betű a második

A

-típusú rész első betűje helyére került. Idáig eggyel több az

X

-ek száma, mint az

Y

-oké. A további betűket ugyanazok a betűk előzik meg, amelyek a

B

-típusú elrendezésben megelőzték, így megint több

X

lesz, mint

Y

, egészen az utolsó betűig.
A meggondolásból azt is látjuk, hogy fordítva egy

A

-típusú sorrendben a második olyan betűt kell megkeresni, ameddig eggyel több

X

szerepel,^{$^{*}$} mint

Y

, és ez után helyezni a sor elejéről az első

X

-et. Ezáltal

X

-szel kezdődő sorrendet kapunk, mert ha az

A

-típusú elrendezésben az első

X

-et egy

Y

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ő

X

elvételével az

X

-ek és

Y

-ok számának a különbsége

1

-gyel csökken, amíg el nem érjük az áthelyezett betű új helyét. Mivel az előtt

1

volt ez a különbség, most

0

-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

X

-ek lesznek túlsúlyban, mig a sor végére nem érünk, hiszen az

X

ú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

k

fiú és

k

lány

A

-, ill.

B

-típusú sorrendjeinek számát

a_{k}

-val

(k \geq 1)

, ill.

b_{k}

-val

(k \geq 2)

. Egy

B

-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

2 k

-adik betű után történik

(k = 1,2, ..., n - 1) (a_{k} / 2) \cdot a_{n - k}

, mert egy

2 k

betűből álló,

X

-szel kezdődő

A

-típusú elrendezést követ egy tetszés szerinti,

2 n - 2 k

betűből álló. Így

\begin{matrix} \frac{b_{n}}{2} = \frac{a_{1}}{2} \cdot a_{n - 1} + \frac{a_{2}}{2} \cdot a_{n - 2} + ... + \frac{a_{n - 1}}{2} \cdot a_{1} . \end{matrix}

A feladatot tehát megoldjuk, ha megmutatjuk, hogy

a_{n}

is felírható a jobb oldal formájában, vagy

2

-vel osztva és

a_{k} / 2

-t

a'_{k}

-vel jelölve

\begin{matrix} a'_{n} = a'_{1} \cdot a'_{n - 1} + a'_{2} \cdot a'_{n - 2} + ... + a'_{n - 1} \cdot a'_{1} . \end{matrix}

(1)

2. Tuza Zsolt, dolgozatában a következő probléma közvetítésével látja be

(1)

fennállását:
,,Hányféleképpen lehet egy kör (v. bármely konvex zárt vonal) mentén elhelyezett

2 k

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

a'_{k + 1}

. Az összekötő húrok kisebb indexű végpontjához

X

-et, a nagyobb indexűhöz

Y

-t ír, majd sorra leírja az egymás utáni pontok mellé írt betűket és az elejére ír még egy

X

-et, a végére egy

Y

-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

0

pont összekötéseinek számán

a'_{1} = 1

-et értünk.) Ez a gondolat elvezet az

(1)

ö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

A

-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ó

X

-ek és

Y

-ok számának különbsége

1

-re. Így az

A

-típusú elrendezéseknek a fenti megoldásban szereplő átalakításához jutunk, csak ezt most nem a

B

-típusú elrendezésekhez való hozzárendelésre használjuk, hanem összeszámláljuk segítségével az

A

-típusú elrendezéseket is ugyanúgy, mint föntebb a

B

-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

(1)

formula és az

a'_{1} = 1

kezdő érték módot ad az

a'_{n}

, s így egyben az

a_{n}

, értékek egymás utáni kiszámítására, az

a'_{n}

, értékek úgynevezett rekurzív meghatározására. Többen egy másik rekurzív meghatározást találtak:
Az összes,

n

darab

X

-ből és

n

darab

Y

-ból álló sorozatok száma

(\binom{2 n}{n})

. Ezek közül a nem

A

-típusúak valamilyen

k

-ra a

2 k

-adik betű után először (esetleg azután még más helyen is) kettévághatók úgy, hogy odáig

k

darab

X

és

k

darab

Y

legyen

(1 \leq k \leq n - 1)

. A vágás előtti rész

A

-típusú, az ilyenek száma

a_{k}

, tovább a

2 n - 2 k

elem

(\binom{2 n - 2 k}{n - k})

lehetséges elrendezésének bármelyike állhat. Ebből az

\begin{matrix} a_{n} = (\binom{2 n}{n}) - a_{1} (\binom{2 n - 2}{n - 1}) - a_{2} (\binom{2 n - 4}{n - 2}) - ... - a_{n - 1} (\binom{2}{1}) \end{matrix}

(2)

összefüggés adódik, ami az

a_{1} = 2

kezdő értékkel szintén meghatározza az

a_{n}

értékeket. Kézenfekvő gondolat volna ezután

(1)

-et teljes indukcióval megpróbálni bizonyítani

(2)

felhasználásával, ez azonban nem vezet eredményre. Többen megtalálták vagy megsejtették

a_{n}

, meghatározását binomiális együtthatók segítségével. Még ennek ismeretében sem könnyű bizonyítani az

(1)

azonosság helyességét, a versenyzőknek nem is sikerült.^{$^{*}$}

^{$^{*}$}Először mindjárt az első

X

után lesz ez a különbség 1.

^{$^{*}$}A kérdést feladatnak kitűzni tervezzük. (Szerk.)