Feladat:	C.1685	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Egyházi Hanna ,  Nagy Korina
Füzet:	2022/március, 149 - 152. oldal		PDF  |  MathML
Témakör(ök):	Matematika, C gyakorlat, Kombinatorikai leszámolási problémák
Hivatkozás(ok):	Feladatok: 2021/október: C.1685

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. Ha nem ülne átok a királyi családon, azaz uralkodhatnának a korban egymást követő testvérek közül 3-nál többen is egymás után, akkor az első kivételével minden gyermek vagy trónra kerül, vagy nem (az első uralkodik éppen, ezért ő biztosan trónra kerül). Így ekkor $2^7=128$-féleképp kerülhetnének trónra. Viszont azokat az eseteket ebből ki kell vonnunk, amikor 3-nál több, korban egymást követő testvér kerül trónra, hiszen a családon átok ül, így ezek nem lehetségesek. Ezeket a kivonandó lehetőségeket esetekre bontottam aszerint, hogy mennyi a legnagyobb $m$ száma azon testvéreknek, akik korban egymást követik, és egymás után uralkodnak. Ezek a testvérek megkapják az $M$ címkét is. A táblázatokban az $x$-szel jelölt testvérek uralkodnak, míg a többiek nem. Az első esetben $m=8$, tehát mindenki trónra kerül, ami 1-féleképp történhet meg.   ${\displaystyle \begin{array}{|cccccccc|}\hline \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle \text{2}}\hfill & \hfill {\displaystyle \text{3}}\hfill & \hfill {\displaystyle \text{4}}\hfill & \hfill {\displaystyle \text{5}}\hfill & \hfill {\displaystyle \text{6}}\hfill & \hfill {\displaystyle \text{7}}\hfill & \hfill {\displaystyle \text{8}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hline\end{array}}$ $m=8$ A második esetben $m=7$, ami csak úgy lehetséges, hogy az utolsót kivéve mindenki uralkodik (hiszen az első biztosan uralkodik). Ez szintén 1 lehetőség.   ${\displaystyle \begin{array}{|cccccccc|}\hline \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle \text{2}}\hfill & \hfill {\displaystyle \text{3}}\hfill & \hfill {\displaystyle \text{4}}\hfill & \hfill {\displaystyle \text{5}}\hfill & \hfill {\displaystyle \text{6}}\hfill & \hfill {\displaystyle \text{7}}\hfill & \hfill {\displaystyle \text{8}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill \\ \hline\end{array}}$ $m=7$ A harmadik esetben $m=6$. Ekkor vagy az első 6 $M$ címkéjű, vagy az utolsó 6, hiszen ha a középső 6 lenne $M$, akkor közülük az első a legidősebb gyermek melletti, ezért $m=7$ lenne. Ha az első 6 $M$ címkéjű, akkor az utolsó gyermek vagy uralkodik, vagy nem, ami 2 lehetőség, míg ha az utolsó 6 az $M$ címkéjű, csak egy lehetőség van, mivel az első gyermek biztosan uralkodik. Ez összesen 3 lehetőség. ${\displaystyle \begin{array}{|cccccccc|}\hline \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle \text{2}}\hfill & \hfill {\displaystyle \text{3}}\hfill & \hfill {\displaystyle \text{4}}\hfill & \hfill {\displaystyle \text{5}}\hfill & \hfill {\displaystyle \text{6}}\hfill & \hfill {\displaystyle \text{7}}\hfill & \hfill {\displaystyle \text{8}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hline\end{array}}$ $m=6$ A következő esetben $m=5$. Ekkor $M$ címkéjű lehet az első 5, ekkor az utolsó kettő vagy uralkodik, vagy nem, ami $2^2=4$ lehetőség; a 3.-tól a 7. gyermek, ekkor (az elsőn kívül) más nem uralkodhat; vagy az utolsó 5, amikor a 2. vagy uralkodik, vagy nem (2 lehetőség). Ez összesen $4+1+2=7$ lehetőség.   ${\displaystyle \begin{array}{|cccccccc|}\hline \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle \text{2}}\hfill & \hfill {\displaystyle \text{3}}\hfill & \hfill {\displaystyle \text{4}}\hfill & \hfill {\displaystyle \text{5}}\hfill & \hfill {\displaystyle \text{6}}\hfill & \hfill {\displaystyle \text{7}}\hfill & \hfill {\displaystyle \text{8}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hline\end{array}}$   $m=5$ Az utolsó esetben $m=4$. Ekkor ha az első 4 $M$ címkéjű, az utolsó 3 vagy uralkodik, vagy nem, ami $2^3=8$-féle lehetőség (ezekből csak egyet tüntettem fel a táblázatban).   ${\displaystyle \begin{array}{|cccccccc|}\hline \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle \text{2}}\hfill & \hfill {\displaystyle \text{3}}\hfill & \hfill {\displaystyle \text{4}}\hfill & \hfill {\displaystyle \text{5}}\hfill & \hfill {\displaystyle \text{6}}\hfill & \hfill {\displaystyle \text{7}}\hfill & \hfill {\displaystyle \text{8}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill & \hfill {\displaystyle \text{x}}\hfill \\ \hline\end{array}}$ $m=4$ Ha a 3.-tól a 6.-ig $M$ címkéjűek, az utolsó vagy uralkodik, vagy nem, ami 2-féleképp történhet. Ha $M$ címkés a 4.-től a 7., akkor a 2. vagy uralkodik, vagy nem, ez szintén 2 lehetőség. Ha pedig az utolsó 4 uralkodik, akkor a 2. és a 3. vagy uralkodik, vagy nem, ami $2^2=4$-féleképp valósulhat meg. Azaz $m=4$ összesen $8+2+2+4=16$-féleképp lehetséges. Tehát összesen $1+1+3+7+16=28$-féleképp lehet $m>3$. Így valójában a testvérek $128-28=100$-féleképp kerülhetnek trónra.   Egyházi Hanna (Budapest, ELTE Apáczai Csere J. Gyak. Gimn., 12. évf.)   II. megoldás. Jelöljük a 8 gyereket betűkkel életkor szerint csökkenő sorrendben: $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$. Tudjuk, hogy a legidősebb, azaz $A$ uralkodik először. Bontsuk csoportokra azokat az eseteket, ahol különböző számú gyerek uralkodik. Helyes uralkodó kiválasztás alatt olyan kiválasztást értek, ahol maximum 3, életkorban egymást követő személy van kiválasztva. Ha helyesen kiválasztjuk az uralkodókat, akkor egyértelműen meghatároztuk az esetet, mert a kiválasztott emberek életkor szerint csökkenő sorrendben fognak uralkodni. Ezért minden különböző kiválasztás különböző esetet fog jelenteni. ‐ Ha pontosan 1 fő uralkodott a 8 fő közül: Mivel $A$ biztosan először uralkodott, ezért itt csak 1 lehetséges helyes kiválasztás van. ‐ Ha pontosan 2 fő uralkodott a 8 fő közül: Az első uralkodó biztosan $A$, a második pedig bárki lehet a többi 7 gyerek közül. Ezért ez 7 lehetséges helyes kiválasztás. ‐ Ha pontosan 3 fő uralkodott a 8 fő közül: Az első uralkodó biztosan $A$, a második és a harmadik uralkodót pedig $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=\frac{7\cdot 6}{2!}=21$-féleképpen választhatjuk ki. (Az $A$-n kívüli 7 főből 2-t kell kiválasztani úgy, hogy a kiválasztás sorrendje nem számít). Ezek közül az esetek közül mindegyik kiválasztás helyes, mert egyik esetben sem volt 4, életkorban egymást követő uralkodó. 21 lehetséges helyes kiválasztás van. ‐ Ha pontosan 4 fő uralkodott a 8 fő közül: Az első uralkodó biztosan A. A másik 3 uralkodót $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=\frac{7\cdot 6\cdot 5}{3!}=35$-féleképpen választhatjuk ki. Mivel $A$ biztosan a kiválasztottak között van, ezért pontosan 1 eset lesz helytelen kiválasztás, amikor a 4 kiválasztott fő $A$, $B$, $C$ és $D$. A többi 34 esetben nem lesz 3-nál több, életkorban egymást követő személy a kiválasztottak között. Azaz 34 helyes kiválasztás van. ‐ Ha pontosan 5 fő uralkodott a 8 fő közül: Az első uralkodó biztosan $A$. A másik 4 uralkodót $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=\frac{7\cdot 6\cdot 5\cdot 4}{4!}=35$-féleképpen választhatjuk ki. A helytelen kiválasztások, amikor az $A$-n kívüli 4 uralkodó életkorban egymást követi, ebből 4 eset van ($B$ ‐ $C$ ‐ $D$ ‐ $E$, $C$ ‐ $D$ ‐ $E$ ‐ $F$, $D$ ‐ $E$ ‐ $F$ ‐ $G$, $E$ ‐ $F$ ‐ $G$ ‐ $H$); illetve, amikor $A$ miatt létezik egy 4 főből életkorban egymást követő személyekből álló uralkodó négyes, ebből 3 eset van ($A$ ‐ $B$ ‐ $C$ ‐ $D$ ‐ $F$, $A$ ‐ $B$ ‐ $C$ ‐ $D$ ‐ $G$, $A$ ‐ $B$ ‐ $C$ ‐ $D$ ‐ $H$). $\left(4+3=\right)7$ helytelen kiválasztás van. Vonjuk ki az összes kiválasztásból a helytelen kiválasztásokat, és megkapjuk a helyeseket: $35-7=28$ helyes kiválasztás van. ‐ Ha pontosan 6 fő uralkodott a 8 fő közül: Ekkor pontosan 2 fő nem fog uralkodni. Ha őket meghatározzuk, akkor egyben az uralkodó 6 főt is meghatározzuk. A két fő lehet: $B$ ‐ $E$, $B$ ‐ $F$, $C$ ‐ $E$, $C$ ‐ $F$, $C$ ‐ $G$, $D$ ‐ $E$, $D$ ‐ $F$, $D$ ‐ $G$, $D$ ‐ $H$. Ez 9 eset, 9 helyes kiválasztás van. Egymást követő életkorú 3 gyerek esetén meghal az életkorban csökkenő sorrendben rákövetkező személy, így elmondható, hogy bármely 4 egymást követő gyerek közül legfeljebb 3 uralkodhat. Ez alapján, ha kiválasztjuk az $A$ ‐ $B$ ‐ $C$ ‐ $D$ négy főből álló csoportot, tudjuk, hogy közülük legfeljebb 3 fog uralkodni. Ugyanez elmondható az $E$ ‐ $F$ ‐ $G$ ‐ $H$ csoportra is, ezért legfeljebb $\left(3+3=\right)6$ fő uralkodhat a 8 gyerek közül. Adjuk össze a kapott lehetséges eseteket: $\begin{array}{c}{\displaystyle 1+7+21+34+28+9=100.}\end{array}$ A királyi család 8 gyermeke 100-féleképpen uralkodhatott.   Nagy Korina (Kecskeméti Bányai Júlia Gimn., 9. évf.)   Megjegyzés. A honlapon ezektől különböző megoldások olvashatók, azonban a versenyzők zöme a két fenti megoldásmenet egyikét választotta.