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