A B. 5132. feladat (2020. november)

B. 5132. A, B és C-betűkből hány olyan 2021 hosszúságú szó készíthető, amelyben az A-betűk száma páros, és a B-betűk száma $\displaystyle 3k+2$ alakú?

(6 pont)

A beküldési határidő 2020. december 10-én LEJÁRT.

1. megoldás. Először az olyan, $\displaystyle n$ hosszú szavakat fogjuk megszámolni, amelyekben a $\displaystyle B$-betűk száma kongruens $\displaystyle n$-nel modulo $\displaystyle 3$, de az $\displaystyle A$-betűk száma tetszőleges lehet.

Bármely nemnegatív egész $\displaystyle n$ és egész $\displaystyle b$ esetén jelölje $\displaystyle x_{n,b}$ az olyan, $\displaystyle n$ hosszú szavak számát, amelyekben a $\displaystyle B$-betűk száma kongruens $\displaystyle b$-vel modulo $\displaystyle 3$. Megengedjük az $\displaystyle \emptyset$ üres szót is. A legfeljebb $\displaystyle 2$ hosszúságú szavakat ($\displaystyle \emptyset$; $\displaystyle A$, $\displaystyle B$, $\displaystyle C$; $\displaystyle AA$, $\displaystyle AB$, $\displaystyle AC$, $\displaystyle BA$, $\displaystyle BB$, $\displaystyle BC$, $\displaystyle CA$, $\displaystyle CB$, $\displaystyle CC$) összeszámolva,

Az összes $\displaystyle n$-hosszú szavak száma

Ha egy $\displaystyle n\ge1$ hosszú szóban a $\displaystyle B$-betűk száma kongruens $\displaystyle b$-vel modulo $\displaystyle 3$, és az első betű $\displaystyle A$, $\displaystyle B$, illetve $\displaystyle C$, akkor a többi $\displaystyle n-1$ betű egy olyan, $\displaystyle n-1$ hosszú szót alkot, amelyben a $\displaystyle B$-betűk száma kongruens $\displaystyle b$-vel, $\displaystyle (b-1)$-gyel, illetve $\displaystyle b$-vel; az ilyen szavak száma $\displaystyle x_{n-1,b}$, $\displaystyle x_{n-1,b-1}$, illetve $\displaystyle x_{n-1,b}$. Tehát, $\displaystyle n\ge1$ esetén

A (2) rekurziót még egyszer alkalmazva, $\displaystyle n\ge2$ esetén

Mi az $\displaystyle x_{2021,2}=x_{2021,2021}$ értékét szeretnénk kiszámítani. Írjuk fel az $\displaystyle x_{2k+1,2k+1}$ sorozat első néhány elemét: $\displaystyle x_{1,1}=1$, $\displaystyle x_{3,3}=4\cdot3-3x_{1,1}=9$, $\displaystyle x_{5,5}=4\cdot3^3-3x_{3,3}=81$; megsejthetjük, hogy $\displaystyle x_{2k+1,2k+1}=3^{2k}$. Ezt $\displaystyle k=0,1,2$-re már láttuk, és teljes indukcióval igazolhatjuk: ha $\displaystyle x_{2k-1,2k-1}=3^{2k-2}$, akkor

$\displaystyle x_{2k+1,2k+1} = 4\cdot3^{2k-1}-3x_{2k-1,2k-1} = 4\cdot3^{2k-1}-3\cdot 3^{2k-2} = 3^{2k-2}\cdot(4\cdot3-3) = 3^{2k-2}\cdot9 = 3^{2k}.$

A $\displaystyle k=1010$ esetben azt kaptuk, hogy az olyan, $\displaystyle 2021$ hosszú szavak száma, amelyekben a $\displaystyle B$-betűk száma $\displaystyle 3k+2$ alakú, pontosan $\displaystyle 3^{2020}$.

Ezen szavak között szerepel a csupa $\displaystyle B$-betűből álló szó (amelyben az $\displaystyle A$-betűk száma páros), és $\displaystyle 3^{2020}-1$ olyan szó, amelyben szerepel $\displaystyle A$- vagy $\displaystyle C$ betű is. Az utóbbi szavakat állítsuk párokba a következőképpen. Mindegyik szóban keressük meg az első $\displaystyle A$- vagy $\displaystyle C$-betűt; ha ez $\displaystyle A$, akkor cseréljük $\displaystyle C$-re, és fordítva. Mindegyik párban az egyik szó páros, a másik páratlan számú $\displaystyle A$-betűt tartalmaz, tehát mindegyik párban az egyik szó megfelelő. A párok száma $\displaystyle \frac{3^{2020}-1}2$, tehát az olyan szavak száma, amelyekben az $\displaystyle A$-betűk száma páros és a $\displaystyle B$-betűk száma $\displaystyle 3k+2$ alakú,

$\displaystyle 1+\frac{3^{2020}-1}2 = \frac{3^{2020}+1}2.$

2. megoldás. Legyen $\displaystyle N=2021$, és legyen $\displaystyle W$ az $\displaystyle A$, $\displaystyle B$ és $\displaystyle C$ változókból készíthető $\displaystyle n$-tényezős szorzatok halmaza; tekintsük különbözőnek azokat a szorzatokat, amelyekben ugyanannyi $\displaystyle A$, $\displaystyle B$ és $\displaystyle C$ szerepel, de a tényezők sorrendje nem ugyanaz. A szorzatokat azonosítjuk az $\displaystyle n$ hosszúságú szavakkal. A szorzatok egyben háromváltozós függvények is, tehát beszélhetünk minden egyes $\displaystyle w\in W$ esetén a $\displaystyle w(A,B,C)$ függvényről.

Ha felbontjuk a zárójeleket az

$\displaystyle (A+B+C)^n = \underbrace{(A+B+C)\cdot(A+B+C)\cdot\ldots\cdot(A+B+C)}_{n}$

polinomban, minden $\displaystyle W$-beli szorzatot pontosan egyszer kapunk meg, ezért

A megfelelő szavak összeszámolásához felírunk egy indikátorfüggvényt, amely minden szóhoz a $\displaystyle 0$ vagy az $\displaystyle 1$ értéket rendeli.

Legyen $\displaystyle \varepsilon=\cos120^\circ+i\sin120^\circ$ az első komplex harmadik egységgyök, és minden $\displaystyle w\in W$ szorzatra legyen

$\displaystyle \chi(w) = \frac{ w(1,1,1)+w(-1,1,1)+w(1,\varepsilon,1)\varepsilon+w(-1,\varepsilon,1)\varepsilon+w(1,\varepsilon^2,1)\varepsilon+w(-1,\varepsilon^{-2},1)\varepsilon^2}{6}.$

Ha a $\displaystyle w$ szorzatban $\displaystyle a$ darab $\displaystyle A$ és $\displaystyle b$ darab $\displaystyle B$ tényező szerepel, vagyis $\displaystyle w(A,B,C)=A^aB^bC^{n-a-b}$, akkor

A két tényező értéke attól függ, hogy $\displaystyle a$ páros-e, illetve $\displaystyle b+1$ osztható-e $\displaystyle 3$-mal:

$\displaystyle \frac{1+(-1)^a}{2} = \begin{cases} \frac{1+1}{2}=1, & \text{ha \(\displaystyle a\) páros} \\ \frac{1-1}{2}=0, & \text{ha \(\displaystyle a\) páratlan;} \end{cases}$

$\displaystyle \frac{1+\varepsilon^{b+1}+\varepsilon^{2(b+1)}}{3} = \begin{cases} \frac{1+\varepsilon+\varepsilon^2}{3}=0, & \text{ha \(\displaystyle b\equiv0\pmod3\)} \\ \frac{1+\varepsilon^2+\varepsilon}{3}=0, & \text{ha \(\displaystyle b\equiv1\pmod3\)} \\ \frac{1+1+1}{3}=1, & \text{ha \(\displaystyle b\equiv2\pmod3\).} \end{cases}$

A kettő szorzata,

$\displaystyle \chi(w) = \begin{cases} 1, & \text{ha \(\displaystyle a\) páros és \(\displaystyle b\equiv2\pmod3\)} \\ 0, & \text{egyébként.} \end{cases}$

A jó szavak száma, amelyekben az A-betűk száma páros és a B-betűk száma $\displaystyle 3$-mal osztva $\displaystyle 2$ maradéket ad,

$\displaystyle \sum_{w\in W} \chi(w) = \sum_{w\in W} \frac{ w(1,1,1)+w(-1,1,1)+w(1,\varepsilon,1)\varepsilon+w(-1,\varepsilon,1)\varepsilon+w(1,\varepsilon^2,1)\varepsilon+w(-1,\varepsilon^{-2},1)\varepsilon^2}{6}.$

A számlálóban álló hat tagot külön-külön összegezzük. A $\displaystyle (*)$ alapján

összeadva

$\displaystyle \sum_{w\in W} \chi(w) = \frac{3^n+3}{6} = \frac{3^{2020}+1}{2}.$

Statisztika:

50 dolgozat érkezett.
6 pontot kapott:	Bán-Szabó Áron, Baski Bence, Ben Gillott, Duchon Márton, Hegedűs Dániel, Jánosik Máté, Kalocsai Zoltán, Kercsó-Molnár Anita, Kovács 129 Tamás, Lengyel Ádám, Mácsai Dániel, Márton Kristóf, Móricz Benjámin, Nádor Benedek, Nagy 551 Levente, Németh Márton, Nyárfádi Patrik, Seres-Szabó Márton, Sztranyák Gabriella, Török Ágoston, Wiener Anna, Zömbik Barnabás.
5 pontot kapott:	Andó Viola.
4 pontot kapott:	4 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	7 versenyző.
0 pontot kapott:	10 versenyző.
Nem versenyszerű:	2 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 2020. novemberi matematika feladatai