Problem B. 5132. (November 2020)
B. 5132. How many different strings of 2021 letters can be made of letters A, B and C such that the number of A's is even and the number of B's is of the form \(\displaystyle 3k+2\)?
(6 pont)
Deadline expired on December 10, 2020.
Sorry, the solution is available only in Hungarian. Google translation
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,
| \(\displaystyle x_{0,0}=1\), | \(\displaystyle x_{0,1}=0\), | \(\displaystyle x_{0,2}=0\), |
| \(\displaystyle x_{1,0}=2\), | \(\displaystyle x_{1,1}=1\), | \(\displaystyle x_{1,2}=0\), |
| \(\displaystyle x_{2,0}=4\), | \(\displaystyle x_{2,1}=4\), | \(\displaystyle x_{2,2}=1\). |
Az összes \(\displaystyle n\)-hosszú szavak száma
| \(\displaystyle x_{n,0}+x_{n,1}+x_{n,2} = 3^n. \) | \(\displaystyle (1) \) |
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
| \(\displaystyle x_{n,b} = 2x_{n-1,b}+x_{n-1,b-1}. \) | \(\displaystyle (2) \) |
A (2) rekurziót még egyszer alkalmazva, \(\displaystyle n\ge2\) esetén
$$\begin{gather*} x_{n,b} = 2x_{n-1,b}+x_{n-1,b-1} =\\ = 2(2x_{n-2,b}+x_{n-2,b-1}) + (2x_{n-2,b-1}+x_{n-2,b-2}) =\\ = 4(x_{n-2,b}+x_{n-2,b-1}+x_{n-2,b-2})-3x_{n-2,b-2} =\\ = 4\cdot3^{n-2}-3x_{n-2,b-2}. \tag3 \end{gather*}$$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
| \(\displaystyle (A+B+C)^n = \sum_{w\in W} w(A,B,C). \) | \(\displaystyle (*)\) |
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
$$\begin{align*} \chi(w) &= \frac{1+(-1)^a+\varepsilon^{b+1}+(-1)^a\varepsilon^{b+1}+\varepsilon^{2b+21}+(-1)^a\varepsilon^{2b+2}}{6}= \\ &= \frac{1+(-1)^a}{2} \cdot \frac{1+\varepsilon^{b+1}+\varepsilon^{2(b+1)}}{3}. \end{align*}$$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
$$\begin{align*} \sum_{w\in W} w(1,1,1) &= (1+1+1)^n = 3^n, \\ \sum_{w\in W} w(-1,1,1) &= (-1+1+1)^n = 1, \\ \sum_{w\in W} w(1+\varepsilon+1)\varepsilon &= (2+\varepsilon)^n\varepsilon = \Big(\sqrt3(\cos30^\circ+i\sin30^\circ)\Big)^{2021}(\cos120^\circ+i\sin120^\circ) = -\big(\sqrt3\big)^n i, \\ \sum_{w\in W} w(-1+\varepsilon+1)\varepsilon &= \varepsilon^{n+1} = 1, \\ \sum_{w\in W} w(1+\varepsilon^2+1)\varepsilon^2 &= (2+\varepsilon^2)^n\varepsilon^2 = \Big(\sqrt3(\cos30^\circ-i\sin30^\circ)\Big)^{2021}(\cos120^\circ-i\sin120^\circ) = \big(\sqrt3\big)^n i, \\ \sum_{w\in W} w(-1+\varepsilon^2+1)\varepsilon^2 &= \varepsilon^{2n+4} = 1; \end{align*}$$összeadva
\(\displaystyle \sum_{w\in W} \chi(w) = \frac{3^n+3}{6} = \frac{3^{2020}+1}{2}. \)
Statistics:
50 students sent a solution. 6 points: 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 points: Andó Viola. 4 points: 4 students. 3 points: 1 student. 2 points: 2 students. 1 point: 7 students. 0 point: 10 students. Unfair, not evaluated: 2 solutionss. Not shown because of missing birth date or parental permission: 1 solutions.
Problems in Mathematics of KöMaL, November 2020