Problem C. 1685. (October 2021)

C. 1685. In a royal dynasty, there are eight brothers. The present king is the eldest brother. As a rule, a brother will come to the throne when he is the oldest of those alive. However, there is a curse on the dynasty: whenever each of three successive brothers comes to the throne, the following brother will die from despair. In how many different ways may the brothers rule? (Only the set of those coming to throne matters.)

(5 pont)

Deadline expired on November 10, 2021.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

159 students sent a solution.
5 points:	77 students.
4 points:	22 students.
3 points:	15 students.
2 points:	8 students.
1 point:	8 students.
0 point:	9 students.
Unfair, not evaluated:	1 solutions.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, October 2021