Baltic Way Shortlist, 2023

For $k \in \mathbb{N}_0$ we denote by $b_k$ the number of words from the alphabet $\{b, @, l, t, i, c, w, a, y\}$ of maximum length $k$, so that $b_{2023} = |B|$. Furthermore, we denote by $m_k$ the number of words of maximum length $k+2$ from the alphabet $\{m, a, t, h\}$, that contain the letter $t$ exactly twice, so that $m_{2023} = |M|$.
For example, we have $b_0 = 1$ (coming from the empty word), $b_1 = b_0 + 9 = 10$ (adding $9$ one-letter words) and $b_2 = b_1 + 9^2 = 91$ (adding $9^2$ two-letter words). More generally, we have
$$b_k = b_{k-1} + 9^k \quad (*)$$
for all $k \ge 1$, since we can form exactly $9^k$ words of length $k$ from the given alphabet. The recursion
$$b_k = 1 + 9b_{k-1} \quad (**)$$
is also true for all $k \ge 1$, since every word of maximum length $k$ from the given alphabet is either the empty word (1 case) or the concatenation of a word of maximum length $k-1$ and one of the nine letters from the given alphabet ($9b_{k-1}$ cases).

On the other hand, we have $m_0 = 1$ (coming from the word $tt$), $m_1 = m_0 + 9 = 10$ (adding $9$ words of the form $tx$, $txt$ and $xtt$ with $x \in \{h, a, m\}$) and $m_2 = m_1 + 54 = 64$ (adding $6 \cdot 9 = 54$ words of the form $ttxy$, $txty$, $txyt$, $xtty$, $xtyt$ and $xytt$ with $x, y \in \{h, a, m\}$).

Lemma. The recursion
$$m_{k+2} = 9m_{k+1} - 27m_k + 27m_{k-1} + 1$$
is true for $k \ge 1$.

Proof of the lemma. We will consider two further sequences, first the sequence $(p_k)_{k \in \mathbb{N}_0}$, where $p_k$ is the number of words of maximum length $k+2$ from the alphabet $\{m, a, t, h\}$, that contain the letter $t$ exactly once. We will also consider the sequence $(q_k)_{k \in \mathbb{N}_0}$, where $q_k$ is the number of words of maximum length $k+2$ from the alphabet $\{m, a, t, h\}$, that do not use the letter $t$ at all (i.e. words of maximum length $k+2$ from the alphabet $\{h, a, m\}$).

Let $k \ge 1$ for the moment. A word of maximum length $k+2$ from the alphabet $\{m, a, t, h\}$, that contains the letter $t$ exactly twice, is either
* the concatenation of the letter $t$ with a word of maximum length $k+1$ with exactly one occurrence of the letter $t$ (of which there are $p_{k-1}$ cases) or
* the concatenation of a letter $x \in \{h, a, m\}$ with a word of maximum length $k+1$ with exactly two occurrences of the letter $t$ (of which there are $3 \cdot m_{k-1}$ cases).

We conclude that
$$m_k = p_{k-1} + 3m_{k-1}. \qquad (***)$$
In a similar spirit, we obtain
$$p_k = q_{k-1} + 3p_{k-1} \qquad (****)$$
and
$$q_k = 1 + 3q_{k-1}. \qquad (†)$$
Equation (***) tells us that $p_{k-1} = m_k - 3m_{k-1}$, from which we obtain $p_k = m_{k+1} - 3m_k$ by shifting indices. We plug both expressions into equation (****) and obtain
$$\begin{align*} m_{k+1} - 3m_k &= q_{k-1} + 3(m_k - 3m_{k-1}) && (††) \\ \Leftrightarrow q_{k-1} &= m_{k+1} - 6m_k + 9m_{k-1}. \end{align*}$$
Plugging equation (††) and its index shift into equation (†) yields the recursion from the lemma. $\square$

Thanks to the lemma. By induction hypothesis, there exist natural numbers $r, s, t \in \mathbb{N}$ such that $m_{k-1} = b_{k-1} + 3^{k-1}r$, $m_{k-2} = b_{k-2} + 3^{k-2}s$ and $m_{k-3} = b_{k-3} + 3^{k-3}t$. It follows that
$$m_k \equiv 9b_{k-1} - 27b_{k-2} + 27b_{k-3} + 1 \pmod{3^k},$$
from which we conclude
$$\begin{align*} m_k - b_k &\equiv -b_k + 9b_{k-1} - 27b_{k-2} + 27b_{k-3} + 1 \\ &\equiv -b_k + 9b_{k-1} - 27(b_{k-1} - 9^{k-1}) + 27(b_{k-1} - 9^{k-1} - 9^{k-2}) + 1 \\ &\equiv -b_k + 9b_{k-1} + 1 \pmod{3^k}. \end{align*}$$
thanks to equation (). By equation (*) we have $m_k - b_k \equiv 0 \pmod{3^k}$, which finishes the induction step.

We now show that $b_k \equiv m_k \pmod{3^k}$ for all $k \in \mathbb{N}_{\ge 0}$, which yields the desired statement when we put $k = 2023$.
We are going to show our claim by strong mathematical induction on $k$. The claim is true for $k=0$, because the difference $b_0 - m_0 = 0 - 0 = 0$ is divisible by $3^0 = 1$. It is true for $k=1$, because the difference $b_1 - m_1 = 10 - 10 = 0$ is divisible by $3^1 = 3$. It is true for $k=2$, because the difference $b_2 - m_2 = 91 - 64 = 27$ is divisible by $3^2 = 9$.

Let $k = 2023$. Since there are exactly $9^i$ words of length $i$ in the set $B$ for every $i \in [0, k]$, we have
$$|B| = \sum_{i=0}^{k} 9^i = \frac{9^{k+1} - 1}{9 - 1} = \frac{1}{8} (9^{k+1} - 1)$$
thanks to the formula for the geometric series. In particular, multiplication by $16$ brings us to the congruence $16|B| \equiv -2 \pmod{3^k}$, since $2 \cdot 9^{k+1}$ is divisible by $3^k$.

Moreover, every word in $M$ is bounded by length by $k+2$. If $i$ parametrises the number of occurrences of letters different from $t$ in a word in $M$, then the word's length is $i+2$ and there are $\binom{i+2}{2}$ possibilities to choose two places for the two letters $t$. The other $i$ letters can be arbitrary elements from the set $\{h, a, m\}$. It follows that
$$|M| = \sum_{i=0}^{k} \binom{i+2}{2} 3^i.$$
Define a function $f:\mathbb{R} \setminus \{1\} \to \mathbb{R}$ by
$$f(x) = \sum_{i=0}^{k} x^{i+2} = \frac{x^{k+3} - 1}{x - 1} - x - 1$$
for all $x$. Its first derivative is given by
$$f'(x) = \sum_{i=0}^{k} (i+2)x^{i+1} = \frac{(k+2)x^{k+3} - (k+3)x^{k+2} + 1}{(x-1)^2} - 1;$$
its second derivative $f''(x) = \sum_{i=0}^{k} (i+2)(i+1)x^i$ is given by
$$\frac{(k+2)(k+1)x^{k+3} - 2(k+3)(k+1)x^{k+2} + (k+3)(k+2)x^{k+1} - 2}{(x-1)^3}.$$
If we plug in $x = 3$ in the last equation, every summand in the numerator of the previous fraction is divisible by $3^k$ except for $-2$. It follows that $-2 \equiv (3-1)^3 \cdot f''(3) = 8 \cdot 2|M| \pmod{3^k}$.
The congruence $16|M| \equiv -2 \equiv 16|B| \pmod{3^k}$ means that $16(|B| - |M|)$ is divisible by $3^k$. Since $16$ is coprime to $3^k$, the difference $|B| - |M|$ is also divisible by $3^k = 3^{2023}$.

We consider the 3-adic expansion of $x := -\frac{1}{2} = \frac{1}{1-3} = \sum_{k=0}^{\infty} 3^k$ and $y := -\frac{1}{8} = \frac{1}{1-9} = \sum_{\ell=0}^{\infty} 3^{2\ell}$. Observe that $y = x^3$ and, therefore,
$$\sum_{\ell=0}^{\infty} 3^{2\ell} = \left( \sum_{k=0}^{\infty} 1 \cdot 3^k \right)^3 = \sum_{k=0}^{\infty} a_k \cdot 3^k,$$
where $a_k$ is the number of presentations of $k$ as an ordered sum of three summands. Since we can place between $k$ objects two “plus” symbols in $\binom{k+2}{2}$ ways and interpret the number of objects before the first plus as the first summand, between the two pluses as the second and after the second plus sign as the third summand, we have $a_k = \binom{k+2}{2}$. Hence, we get
$$\sum_{\ell=0}^{\infty} 3^{2\ell} = \sum_{k=0}^{\infty} \binom{k+2}{2} \cdot 3^k.$$
Reducing this 3-adic identity modulo $3^{2023}$ gives
$$|B| \equiv |M| \pmod{3^{2023}}.$$