5. Problem: A sequence of $A$ s and $B \mathrm{~s}$ is called antipalindromic if writing it backwards, then turning all the $A$ s into $B \mathrm{~s}$ and vice versa, produces the original sequence. For example $A B B A A B$ is antipalindromic. For any sequence of $A \mathrm{~s}$ and $B \mathrm{~s}$ we define the cost of the sequence to be the product of the positions of the $A \mathrm{~s}$. For example, the string $A B B A A B$ has cost $1 \cdot 4 \cdot 5=20$. Find the sum of the costs of all antipalindromic sequences of length 2020 .
Solution: For each integer $0 \leq k \leq 1009$ define a $k$-pal to be any sequence of $2020 \mathrm{As}$ and $B \mathrm{~s}$, where the first $k$ terms are $B$, the last $k$ terms are $B$, and the middle $(2020-2 k)$ terms form an antipalindromic sequence.
Now for any $k$, define $f(k)$ to be sum of the costs of all $k$-pals. Note that any $k$-pal can be created from a $(k+1)$-pal by either
- (A) replacing the $B$ in position $(k+1)$ with an $A$, or
- (B) replacing the $B$ in position $(2021-k)$ with an $A$.

Therefore the sum of the costs of all $k$-pals formed using operation (A) is $(k+1) \times f(k+1)$. Similarly the sum of the costs of all $k$-pals formed using operation (B) is $(2021-k) \times$ $f(k+1)$. Hence
$$
f(k)=(k+1) f(k+1)+(2020-k) f(k+1)=((k+1)+(2020-k)) f(k+1)=2021 f(k+1) \text {. }
$$

Now we note that there are two different 1009-pals, with costs equal to 1010 and 1011 respectively. So
$$
f(1009)=1010+1011=2021 .
$$

Now if we use the formula $f(k)=2021 f(k+1)$ iteratively, we get $f(1010-i)=2021^{i}$ for each $i=1,2,3, \ldots$ Therefore
$$
f(0)=2021^{1010}
$$
which is our final answer.
Alternative Solution:
Let $n$ be a positive integer. We will find an expression (in terms of $n$ ) for the sum of the costs of all antipalindromes of length $2 n$. Note that a string of $A$ s and $B$ s of length $2 n$ is an antipalindrome if and only if for each $i$, exactly one of the $i^{\text {th }}$ and $(2 n+1-i)^{\text {th }}$ letters is an $A$ (and the other is a $B$ ).
Let $x_{1}, x_{2}, \ldots, x_{2 n}$ be variables. For any $1 \leq a(1)<a(2)<\cdots<a(k) \leq 2 n$, consider the string of $A \mathrm{~s}$ and $B \mathrm{~s}$ of length $2 n$, such that the $a(j)^{\text {th }}$ letter is $A$ for all $j$ (and all the other letters are $B)$. Let this string correspond to the term $t=x_{a(1)} x_{a(2)} x_{a(3)} \ldots x_{a(k)}$. If $x_{i}=i$ for all $i$ then the value of $t$ is equal to the cost of it's corresponding string. Now consider the expression
$$
y=\left(x_{1}+x_{2 n}\right)\left(x_{2}+x_{2 n-1}\right) \cdots\left(x_{n}+x_{n+1}\right)=\prod_{j=1}^{n}\left(x_{j}+x_{2 n+1-j}\right) .
$$

If we expand the brackets then we get $2^{n}$ terms, each in the form $t=x_{a(1)} x_{a(2)} x_{a(3)} \ldots x_{a(n)}$ such that for each $j=1,2, \ldots, n$ either $a(j)=j$ or $a(j)=2 n+1-j$. Therefore $y$ is the sum of all terms that correspond to antipalindromes. Hence if we substitute $x_{i}=i$ for all $i$, then the value of $y$ would be the sum of the costs of all antipalindromes. So the final answer is:
$$
\prod_{j=1}^{n}(j+(2 n+1-j))=\prod_{j=1}^{n}(2 n+1)=(2 n+1)^{n} .
$$

Alternative Solution 2:
Let $n$ be a positive integer. We will find an expression (in terms of $n$ ) for the sum of the costs of all antipalindromes of length $2 n$. Let $\mathcal{P}$ denote the set of all antipalindromes of length $2 n$, and let $P$ be an antipalindrome chosen uniformly from $\mathcal{P}$. Note that for each $j=1,2, \ldots, n$ the $j^{\text {th }}$ and $(2 n+1-j)^{\text {th }}$ must be an $A$ and a $B$ in some order. Let $X_{j}$ be the random variable defined by:
- $X_{j}=j$ if the $j^{\text {th }}$ letter of $P$ is an $A$ and the $(2 n+1-j)^{\text {th }}$ letter is a $B$.
- $X_{j}=2 n+1-j$ if the $j^{\text {th }}$ letter of $P$ is a $B$ and the $(2 n+1-j)^{\text {th }}$ letter is an $A$.

Notice that the cost of $P$ is given by the product $X_{1} X_{2} X_{3} \cdots X_{n}$. Now consider $f_{j}: \mathcal{P} \rightarrow$ $\mathcal{P}$ to be the function which swaps the $j^{\text {th }}$ and $(2 n+1-j)^{\text {th }}$ letters of the string. Notice that $f_{j}$ is a bijection that toggles the value of $X_{j}$. This means that $X_{j}$ is equal to $j$ or $(2 n+1-j)$ with equal probabilities. Therefore
$$
\mathbb{P}\left(X_{j}=j\right)=\mathbb{P}\left(X_{j}=2 n+1-j\right)=\frac{1}{2} .
$$

Furthermore $f_{j}$ preserves the value of $X_{i}$ for all $i \neq j$. Therefore the variables $X_{i}$ and $X_{j}$ are independent. Therefore the expected value of the cost of $P$ is given by:
$$
\begin{aligned}
\mathbb{E}[\operatorname{cost}(P)] & =\mathbb{E}\left[\prod_{i=1}^{n} X_{i}\right] \\
& =\prod_{i=1}^{n} \mathbb{E}\left[X_{i}\right] \\
& =\prod_{i=1}^{n}\left(\frac{1}{2}(i)+\frac{1}{2}(2 n+1-i)\right) \\
& =\prod_{i=1}^{n} \frac{2 n+1}{2} \\
& =\left(\frac{2 n+1}{2}\right)^{n} .
\end{aligned}
$$

Now the number of antipalindromes of length $2 n$ is simply $2^{n}$ (one for each choice of the variables $X_{j}$ ). Therefore the sum of the costs of all antipalindromes of length $2 n$ is simply $2^{n}$ multiplied by the expected value of the cost of $P$. This is
$$
2^{n} \times\left(\frac{2 n+1}{2}\right)^{n}=(2 n+1)^{n}
$$