Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

A C. 1685. feladat értékelése még nem fejeződött be.


A KöMaL 2021. októberi matematika feladatai