 |
A C. 1685. feladat (2021. október) |
C. 1685. Egy királyi család nyolc gyermeke közül a legidősebb uralkodik. A testvérek mindegyike pontosan akkor uralkodik, amikor ő a legidősebb még élő személy közülük. Viszont ezen a királyi családon átok ül: ha három testvér, kik korban egymást követik, mind trónra kerülnek, akkor a rákövetkező testvérük meghal reménytelenségében. Hányféleképpen uralkodhatnak, ha csak arra vagyunk tekintettel, hogy kik kerülnek trónra a testvérek közül?
(5 pont)
A beküldési határidő 2021. november 10-én LEJÁRT.
1. megoldás. Számozzuk meg a testvéreket 1-től 8-ig a trónöröklési sorrend szerint: 1 a legidősebb testér, 2 a második legidősebb, és így tovább. Ily módon az, hogy kik fognak végül uralkodni az \(\displaystyle \{1,2,3,4,5,6,7,8\}\) egy részhalmazának felel meg, mely az 1-et mindenképpen tartalmazza, és nem tartalmaz 4 szomszédos számot, hiszen ha hárman egymás után trónra kerülnek, akkor a rákövetkező testvér meghal.
Tehát azt kell megszámolni, hány ilyen tulajdonságú részhalmaza van az \(\displaystyle \{1,2,3,4,5,6,7,8\}\) halmaznak.
Ezt a továbbiakban esetvizsgálattal határozzuk meg.
1. eset. Az 5 nincs a halmazban. Ilyenkor a \(\displaystyle \{6,7,8\}\) elemek közül bárhogyan választhatunk, nem tud kialakulni őket tartalmazó szomszédos 4-es blokk, ez tehát \(\displaystyle 2^3=8\) lehetőség. A \(\displaystyle \{2,3,4\}\) elemek közül is majdnem tetszőlegesen választhatunk: csak mindhármukat kiválasztva jön létre az 1234 szomszédos 4-es, ez így \(\displaystyle 2^3-1=7\) lehetőség. Ekkor tehát \(\displaystyle 8\cdot 7=56\) megfelelő részhalmaz van.
2. eset. Az 5 a halmazban van, de a 4 nincs. Ekkor \(\displaystyle \{2,3\}\) tetszőleges részhalmaza választható, és \(\displaystyle \{6,7,8\}\) esetében is csak akkor jön létre szomszédos 4-es (az 5678), ha mind a három elemet kiválasztjuk. Így a megfelelő részhalmazok száma ebben az esetben \(\displaystyle 2^2(2^3-1)=28\).
3. eset. A 4 és az 5 is a halmazban van.
Ekkor a 3 és a 6 közül legalább az egyik nincs a halmazban, hiszen különben létrejönne a 3456 szomszédos 4-es. Három alesetet különböztetünk meg aszerint, hogy melyikük nincs a halmazban: a 3, a 6 vagy egyikük sem.
3.(a) eset. A 3 és a 6 sincs a halmazban.
Ekkor a \(\displaystyle \{2\}\) és a \(\displaystyle \{7,8\}\) tetszőleges részhalmazai választhatók, nem tud létrejönni szomszédos 4-es. Ez \(\displaystyle 2\cdot 4=8\) eset.
3.(b) eset. A 3 a halmazban van, de a 6 nincs. Ekkor a 2 nem lehet a halmazban (különben létrejönne az 1234 szomszédos 4-es), viszont a \(\displaystyle \{7,8\}\) halmaz bármely részhalmaza választható. Ez \(\displaystyle 2^2=4\) eset.
3.(c) eset. A 6 a halmazban van, de a 3 nincs. Ekkor a 7 nem lehet a halmazban (különben létrejönne a 4567 szomszédos 4-es), viszont a 2 és a 8 bármelyike szabadon hozzávehető a halmazhoz. Ez \(\displaystyle 2\cdot 2=4\) eset.
Tehát a megfelelő részhalmazok száma \(\displaystyle 56+28+8+4+4=100\).
2. megoldás. Az előző megoldás alapján azt kell megszámolnunk, hogy az \(\displaystyle \{1,2,3,4,5,6,7,8\}\) halmaznak hány olyan részhalmaza van, ami tartalmazza az 1-et, de nem tartalmaz négy szomszédos elemet.
Legyen \(\displaystyle 1\leq n\leq 8\)-ra \(\displaystyle f(n)\) az \(\displaystyle \{1,2,\dots,n\}\) ilyen tulajdonságú részhalmazainak száma. Az \(\displaystyle f(n)\) értékét rekurzívan fogjuk meghatározni. Világos, hogy \(\displaystyle f(1)=1.\)
Ha \(\displaystyle A\subseteq \{1,2,\dots,n\}\) egy megfelelő részhalmaz, akkor \(\displaystyle A':=A\setminus \{n\}\) is az, ez a halmaz \(\displaystyle f(n-1)\) féle lehet. Az \(\displaystyle A\) halmaz vagy \(\displaystyle A'\), vagy \(\displaystyle A'\cup \{n\}\) (és különböző \(\displaystyle A'\)-kből különböző \(\displaystyle A\)-kat kapunk. Világos, hogy \(\displaystyle A=A'\) megfelelő részhalmaz, nézzük meg, hogy \(\displaystyle A'\cup \{n\}\) mikor nem az. Csak úgy romolhat el a feltétel, ha kialakul négy egymást követő elem, vagyis \(\displaystyle n-3,n-2,n-1\in A'\), azonban mivel \(\displaystyle A'\) még megfelelő halmaz volt, ezért vagy \(\displaystyle n-4\notin A\) vagy \(\displaystyle n=4\). Az \(\displaystyle n=4\) esetben tehát ez azt jelenti, hogy egyedül az \(\displaystyle A'=\{1,2,3\}\) nem ad megfelelő \(\displaystyle A\)-t, így \(\displaystyle f(4)=2f(3)-1\). Ha \(\displaystyle n-4\notin A\), de \(\displaystyle n-3,n-2,n-1\in A\), akkor ez azt is jelenti, hogy \(\displaystyle n\geq 6\). Tehát \(\displaystyle 2\leq n\leq 3\)-ra és \(\displaystyle n=5\)-re \(\displaystyle f(n)=2f(n-1)\). Nézzük most az \(\displaystyle n\geq 6\) esetet, amikor \(\displaystyle n-4\notin A\), de \(\displaystyle n-3,n-2,n-1\in A\). Ekkor \(\displaystyle A\cap \{1,2,\dots,n-5\}=A'\cap \{1,2,\dots,n-5\}\) tetszőleges a feltételeknek megfelelő halmaz lehet, hiszen \(\displaystyle n-4\notin A\). Így a nem megfelelő \(\displaystyle A=A'\cup \{n\}\) halmazok száma \(\displaystyle f(n-5)\), vagyis ekkor \(\displaystyle f(n)=2f(n-1)-f(n-5)\).
A rekurzió alapján az értékeket sorban meghatározva:
\(\displaystyle f(1)=1,\)
\(\displaystyle f(2)=2f(1)=2,\)
\(\displaystyle f(3)=2f(2)=4,\)
\(\displaystyle f(4)=2f(3)-1=7,\)
\(\displaystyle f(5)=2f(4)=14,\)
\(\displaystyle f(6)=2f(5)-f(1)=27,\)
\(\displaystyle f(7)=2f(6)-f(2)=52,\)
\(\displaystyle f(8)=2f(7)-f(3)=100.\)
Tehát 100-féleképpen uralkodhatnak.
Statisztika:
159 dolgozat érkezett. 5 pontot kapott: 77 versenyző. 4 pontot kapott: 22 versenyző. 3 pontot kapott: 15 versenyző. 2 pontot kapott: 8 versenyző. 1 pontot kapott: 8 versenyző. 0 pontot kapott: 9 versenyző. Nem versenyszerű: 1 dolgozat. Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt: 1 dolgozat.
A KöMaL 2021. októberi matematika feladatai