2022 Galois Contest
Solutions
(Grade 10)

Tuesday, April 12, 2022
(in North America and South America)

Wednesday, April 13, 2022
(outside of North American and South America)

1. The ratio of Alice’s contribution to Bello’s contribution was $3:8$.
  This means that for every $\$3+\$8=\$11$ contributed to starting the business, Bello contributed $8, and so Bello contributed $\dfrac{8}{11}$ of the cost of starting the new business.
  If the cost of starting the new business was $9240, then Bello’s contribution to this cost was $\dfrac{8}{11}\times\$9240=\$6720$.
2. The ratio of Alice’s share of the first year profits to Bello’s share was $3:8$.
  This means that for every $\$3+\$8=\$11$ of profit in the first year, Alice’s share was $3.
  Let the first year profit be $\$P$.
  Since Alice’s share of the first year profit was $1881, then $\dfrac{3}{11}\times P=1881$ or $P=\dfrac{1881\times11}{3}$, and so $P=\dfrac{20\,691}{3}=6897$.
  The total profit of the business for the first year was $6897.
3. The ratio of Alice’s share of the second year profits to Bello’s share was $3:(8+x)$.
  This means that for every $\$3+\$(8+x)=\$(11+x)$ of profit in the second year, Bello’s share was $$(8+x)$.
  Since Bello’s share of the second year profit was $5440, and the profit that year was $6400, then $\dfrac{(8+x)}{(11+x)}\times 6400=5440$.
  Solving this equation, we get \[\begin{align*} \dfrac{(8+x)}{(11+x)}\times 6400&=5440\\ 6400(8+x) &= 5440(11+x)\\ 20(8+x) &= 17(11+x) & \text{(dividing both sides by 320)}\\ 160+20x&=187+17x\\ 3x&=27\end{align*}\] and so $x=9$.
1. Line $L_1$ has equation $y=\frac32x+k$, and thus has slope $\frac32$.
  Since $L_2$ is perpendicular to $L_1$, then its slope is $-\frac23$.
2. Since $L_1$ has equation $y=\frac32x+k$, its $y$-intercept is $k$.
  Line $L_2$ has the same $y$-intercept as $L_1$ (which is at $P(0,k)$).
  Thus, $L_2$ has slope $-\frac23$ and $y$-intercept $k$, and so it has equation $y=-\frac23x+k$.
  Since $L_2$ intersects the $x$-axis at $Q$, the $x$-coordinate of point $Q$ is the $x$-intercept of $L_2$.
  Setting $y=0$ in the equation for $L_2$ and solving for $x$, we get $0=-\frac23x+k$ or $\frac23x=k$, and so $x=\frac{3k}{2}$.
  Written in terms of $k$, the $x$-coordinate of point $Q$ is $\frac{3k}{2}$.
3. From part (b), the coordinates of $P$ are $(0,k)$, and the coordinates of $Q$ are $\left(\frac{3k}{2},0\right)$.
  To determine an expression for the area of $\triangle PQR$, we first need to determine the coordinates of point $R$.
  $L_3$ is parallel to $L_1$ and thus has slope $\frac32$ and equation $y=\frac32x+b$, for some $y$-intercept $b$.
  Line $L_3$ passes through point $Q\left(\frac{3k}{2},0\right)$, and so $0=\frac32\left(\frac{3k}{2}\right)+b$ or $b=-\frac{9k}{4}$.
  Therefore the $y$-intercept of $L_3$ is $-\frac{9k}{4}$ and so $R$ has coordinates $\left(0,-\frac{9k}{4}\right)$.
  
  If we call the origin $O(0,0)$, then the area of $\triangle PQR$ is given by $\frac12\times PR\times OQ$, since height $OQ$ is perpendicular to the base $PR$.
  Since $PR=k-\left(-\frac{9k}{4}\right)=\frac{13k}{4}$ and $OQ=\frac{3k}{2}$, then the area of $\triangle PQR$ is $\frac12\times\frac{13k}{4}\times\frac{3k}{2}=\frac{39k^2}{16}$.
  The area of $\triangle PQR$ is 351, and so $\frac{39k^2}{16}=351$ or $k^2=\frac{351\times16}{39}$ or $k^2=144$, and so $k=12$ (since $k>0$).
1. We begin by recognizing that a number is a perfect square if the exponent on each prime factor in its prime factorization is even, and conversely that the prime factorization of every perfect square has an even exponent on each prime factor.
  The prime factorization of 84 is $2^2\times3\times7$.
  For the product $84\times k=2^2\times3\times7\times k$ to be a perfect square, $k$ must at least include 3 and 7 as prime factors (since the exponent on each is an odd number), and so $k$ must be divisible by 21.
  If $k=3\times7$, then $84\times k$ is a perfect square because \[84\times 3\times 7=2^2\times3^2\times7^2=(2\times3\times7)\times(2\times3\times7).\] Thus, the smallest value of the positive integer $k$ for which $84\times k$ is a perfect square is $k=3 \times 7 =21$.
2. The prime factorization of 572 is $2^2\times11\times13$, and so $\ell$ must at least include 11 and 13 as prime factors (since the exponent on each is an odd number).
  Since $572\times \ell$ is a perfect square, then any factor of $\ell$ in addition to 11 and 13 must be a perfect square.
  That is, $\ell$ is a number of the form $11\times13\times n^2$ for some positive integer $n$, because \[572\times \ell = 572\times 11\times 13\times n^2=(2\times11\times13\times n)\times(2\times11\times13\times n).\] Since $\ell=11\times13\times n^2=143n^2$ and $\ell<6000$, then $143n^2<6000$, and so $n^2<\frac{6000}{143}\approx 41.96$.
  The greatest value of the positive integer $n$ for which $n^2\leq41$ is $n=6$.
  Therefore, the greatest possible value of $\ell$ is $11\times13\times6^2=5148$.
3. The prime factorization of 525 000 is $2^3\times3\times5^5\times7$, and so if $525\,000\times m$ is a perfect square, then $m$ must at least include $2, 3, 5$, and 7 as prime factors (since the exponent on each is an odd number).
  If $m$ includes the prime factors 2, 3, 5, and 7, then $m$ is greater than or equal to $2\times3\times5\times7=210$.
  Therefore, if $m$ is a positive integer less than 200, then $525\,000\times m$ cannot be a perfect square.
4. Suppose that the three powers of 10 chosen from the list are $10^a, 10^b$, and $10^c$, where $a,b,c$ are odd positive integers between 1 and 99 inclusive, and $a<b<c$.
  Since $a<b$ and $a<c$, the sum of these three powers, $S=10^a+10^b+10^c$, can be factored so that $S=10^a(1+10^{b-a}+10^{c-a})$.
  Since $b-a$ is a positive integer, then $10^{b-a}$ is an even positive integer.
  Similarly, $10^{c-a}$ is an even positive integer, and so $1+10^{b-a}+10^{c-a}$ is an odd positive integer.
  Thus for some odd positive integers $a,b,c$, and $d$, \[S=10^a(1+10^{b-a}+10^{c-a})=10^a\times d=(2\times5)^a\times d=2^a\times5^a\times d\] Since $d$ is an odd integer, then 2 is not a prime factor of $d$, and so the prime factor 2 occurs an odd number of times in the prime factorization of $S$ (since $a$ is odd).
  Therefore, the sum of every choice of three different powers of 10 from the list is not a perfect square.

Solution 1

For each Bauman string of length 5 in which the first and last letters are both $A$, the second and fourth letters are not $A$.
For such Bauman strings, either the third letter is $A$, or the third letter is not $A$.

Case 1: The third letter is $A$.

In this case, the string is of the form $A\underline{\hspace{5mm}}A\underline{\hspace{5mm}}A$.
There are 4 choices for the second letter ($B,C,D$, or $E$) and 4 choices for the fourth letter, and so there are $4\times4=16$ such Bauman strings.

Case 2: The third letter is not $A$.

In this case, the string is of the form $A\underline{\hspace{5mm}}x\underline{\hspace{5mm}}A$, where the third letter $x$ is $B,C,D$, or $E$, and so there are 4 choices for the third letter.
The second letter must be different than the third letter and must not be $A$, and so there are 3 choices for the second letter.
Similarly, there are 3 choices for the fourth letter, and so there are $4\times3\times3=36$ such Bauman strings.

In total, the number of Bauman strings of length 5 in which the first and last letters are both $A$ is $16+36=52$.

Solution 2

For each Bauman string of length 5 in which the first and last letters are both $A$, either the second and fourth letters are the same, or they are different.

Case 1: The second and fourth letters are the same.

In this case, the string is of the form $Ax\underline{\hspace{5mm}}xA$.
There are 4 choices for the second letter ($B,C,D$, or $E$) and 1 choice for the fourth letter since it is the same as the second letter.
The third letter must be different than the second and fourth letters (which are the same) and so there are 4 choices for the third letter.
Thus, there are $4\times1\times4=16$ such Bauman strings.

Case 2: The second and fourth letters are different.

In this case, the string is of the form $Ax\underline{\hspace{5mm}}\, yA$, where $x$ and $y$ represent different letters.
There are 4 choices for the second letter ($B,C,D$, or $E$) and 3 choices for the fourth letter (it is different than the second letter and not $A$).
The third letter must be different than the second and fourth letters (which are different) and so there are 3 choices for the third letter.
Thus, there are $4\times3\times3=36$ such Bauman strings.

In total, the number of Bauman strings of length 5 in which the first and last letters are both $A$ is $16+36=52$.
Solution 1

We may determine the number of Bauman strings of length 6 that contain more than one $B$ indirectly.
That is, we may subtract the number of Bauman strings that contain 0 $B$’s and the number of Bauman strings that contain exactly 1 $B$ from the total number of Bauman strings of length 6.

For a Bauman string of length 6 (with no restrictions), there are 5 choices for the first letter and 4 choices for each of the remaining letters, and so there are a total of $5\times4^5=5120$ such strings.

For a Bauman string of length 6 that contains 0 $B$’s, there are 4 choices for the first letter and 3 choices for each of the remaining letters, and so there are a total of $4\times3^5=972$ such strings.

Next, we count the number of Bauman strings that contain exactly 1 $B$.
If the first letter of the string is a $B$, then there are 4 choices for the second letter and 3 choices for each of the remaining four letters.
Similarly, if the last letter is a $B$, then there are 4 choices for the letter adjacent to the $B$ and 3 choices for each of the remaining four letters.
Thus, there are $1\times4\times3^4=324$ strings that begin with a $B$ and 324 strings that end with a $B$.
If the second letter of the string is a $B$, then there are 4 choices for the first letter, 4 choices for the third letter, and 3 choices for each of the fourth, fifth and sixth letters.
Thus, there are $4\times1\times4\times3^3=432$ such strings.
Similarly, if the third, fourth or fifth letter in the string is a $B$, then there are 432 such strings.

In total, there are $5120-972-2\times324-4\times432=1772$ Bauman strings of length 6 that contain more than one $B$.
Solution 2

A Bauman string of length 6 cannot contain more than 3 $B$’s (confirm for yourself why this is true before proceeding).
We may determine the number of Bauman strings of length 6 that contain more than one $B$ directly.
That is, we may count the number of strings that contain exactly 3 $B$’s and the number of strings that contain exactly 2 $B$’s.
Thus, there are two cases to consider.

Case 1: The Bauman string has exactly 3 $B$’s

In this case, the string must take one of four possible forms: \[B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}},~~ B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B ,~~ B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B ,~~ \underline{\hspace{5mm}}\,B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B.\] We begin by counting the number of strings of the form $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$.
There are 4 choices for the second letter ($A,C,D$, or $E$), 4 choices for the fourth letter, and 4 choices for the sixth letter, and so there are $4^3=64$ such strings.
Similarly, there are $4^3=64$ strings of the form $\underline{\hspace{5mm}}\,B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B$.
It is worth noting that $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$ and $\underline{\hspace{5mm}}\,B\underline{\hspace{5mm}}B\underline{ }B$ have identical forms when one is read left to right and the other right to left.
We may call such pairs of forms symmetric, and recognize that under the same restrictions, symmetric forms have an equal number of Bauman strings.

For strings of the form $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B$, there are 4 choices for the second letter, 4 choices for the fourth letter, and 3 choices for the fifth letter (since the fifth letter must be different than $B$ and different than the fourth letter, which is not $B$), and so $4^2\times3=48$ such strings.
Since $B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B$ is symmetric to $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B$, there are similarly $4^2\times3=48$ strings of this form.
Thus, there are $2\times64+2\times48=224$ Bauman strings with exactly 3 $B$’s.

Case 2: The Bauman string has exactly 2 $B$’s

In this case, the string must take one of ten possible forms.
Eight of these occur in one of the following four symmetric pairs \[B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}} \textrm{ \ and \ } \underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B \textrm{,\ \ \ \ \ \ \ } B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}} \textrm{ \ and \ } \underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B,\] \[B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{ }B\underline{\hspace{5mm}} \textrm{ \ and \ } \underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B \textrm{,\ \ \ \ \ \ \ } \underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}} \textrm{ \ and \ } \underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\] and the final two forms (which are not a symmetric pair) are \[B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B \textrm{ \ and \ }\] \[\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}.\] We begin by counting the number of strings of the form $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}$.
There are 4 choices for the second letter ($A,C,D$, or $E$), 4 choices for the fourth letter, 3 choices for each of the fifth and sixth letters, and so there are $4^2\times3^2=144$ such strings.
Similarly, there are $4^2\times3^2=144$ strings for each of the next five forms listed above, $\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B,\, B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,, \,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B, \, B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,, \textrm{ and } \underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B$.

For strings of the form $\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}$, there are 4 choices for the first letter, 4 choices for the third letter, 4 choices for the fifth letter, and 3 choices for the sixth letter, and so there are $4^3\times3=192$ such strings.
Since $\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$ is symmetric to $\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}$, there are similarly $4^3\times3=192$ strings of this form.

Finally, there are $4\times3^3=108$ strings of the form $B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B$, and $4^3\times3=192$ strings of the form $\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$.
Thus, there are $6\times144+2\times192+ 108+192 =1548$ Bauman strings with exactly 2 $B$’s.

In total, there are $224+1548=1772$ Bauman strings of length 6 that contain more than one $B$.

Solution 1

Consider all Bauman strings of length $n$ that begin with $C$.
There are 4 choices for each of the remaining $n-1$ letters, and so there are $4^{n-1}$ such Bauman strings.
Each of these strings either ends with $D$, or it does not end with $D$.
We call those that end with $D$, $d_n$, and we define $|d_n|$ to be the number of such strings.
Similarly, we call those that do not end in $D$, $x_n$, and we define $|x_n|$ to be the number of such strings.
For example, $d_1$ represents the Bauman strings of length $1$ that begin with $C$ and end with $D$, and since no such string exists, then $|d_1|=0$.
Similarly, $x_1$ represents the Bauman strings of length $1$ that begin with $C$ and do not end with $D$, and so $|x_1|=1$ (the string is $C$).
We may confirm that $4^{n-1}=|d_n|+|x_n|$ when $n=1$, since $4^{1-1}=|d_1|+|x_1|=0+1$.
Further, we know that $|d_2|=1$ (the string is $CD$), and $|x_2|=3$ (the strings are $CA$, $CB$, $CE$), and again confirm that $4^{2-1}=1+3$.

Next, consider the Bauman strings of length $n$ that begin with $C$ and do not end with $D$, that is, $x_n$.
Each of these strings could have a $D$ added to its end to form a Bauman string of length $n+1$ that begins with $C$ and ends with $D$, or $d_{n+1}$.
Since adding a $D$ to the end of every string $x_n$ gives all possible strings $d_{n+1}$, then $|d_{n+1}| = |x_n|$.
From our earlier work, we may confirm that $|d_2|=|x_1|=1$.

Further, $|x_{n+1}| = 4|d_n| + 3|x_n|$. Why is this true?
Every Bauman string of length $n+1$ that begins with $C$ and does not end with $D$, that is $x_{n+1}$, is either a string $d_n$ with an $A$, $B$, $C$, or $E$ added to its end, or it is a string $x_n$ that has a choice of 3 letters added to its end (the letter added can not be $D$ and it can not be the last letter of $x_n$, leaving 3 possibilities).
The number of strings $d_n$ that have $A$, $B$, $C$, or $E$ added to its end is $4|d_n|$.
The number of strings $x_n$ that have a choice of 3 letters added to its end is $3|x_n|$.
Therefore, we conclude that $|x_{n+1}| = 4|d_n| + 3|x_n|$.
From our earlier work, we may confirm that $|x_2|=4|d_1|+3|x_1|=4(0)+3(1)=3$.
We use these two formulas $|d_{n+1}| = |x_n|$ and $|x_{n+1}| = 4|d_n| + 3|x_n|$, which are equivalent to $|d_{n}| = |x_{n-1}|$ and $|x_{n}| = 4|d_{n-1}| + 3|x_{n-1}|$, to build the table below.

$n$	$\|d_n\|=\|x_{n-1}\|$	$\|x_n\|=4\|d_{n-1}\| + 3\|x_{n-1}\|$
1	$\|d_1\|=0$	$\|x_1\|=1$
2	$\|d_2\|=1$	$\|x_2\|=3$
3	$\|d_3\|=\|x_{2}\|=3$	$\|x_3\|=4\|d_{2}\| + 3\|x_{2}\|=4(1)+3(3)=13$
4	$\|d_4\|=\|x_{3}\|=13$	$\|x_4\|=4\|d_{3}\| + 3\|x_{3}\|=4(3)+3(13)=51$
5	$\|d_5\|=51$	$\|x_5\|=4(13)+3(51)=205$
6	$\|d_6\|=205$	$\|x_6\|=4(51)+3(205)=819$
7	$\|d_7\|=819$	$\|x_7\|=4(205)+3(819)=3277$
8	$\|d_8\|=3277$	$\|x_8\|=4(819)+3(3277)=13\,107$
9	$\|d_9\|=13\,107$	$\|x_9\|=4(3277)+3(13\,107)=52\,429$
10	$\|d_{10}\|=52\,429$	not needed

Therefore, the number of Bauman strings of length $10$ in which the first letter is $C$ and the last letter is $D$ is 52 429.

Solution 2

Let $S_{n}$ be the set of Bauman strings of length $n$ in which the first letter is $C$ and the last letter is $D$.
Further, we define $|S_{n}|$ to be the number of such strings.
For example, $S_2=\{CD\}$ and so $|S_{2}|=1$, and $S_3=\{CAD, CBD, CED\}$ and so $|S_{3}|=3$.
Each string in $S_{10}$ is of the form $C\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,D$ or $CT_8D$ where $T_8$ is a Bauman string of length 8 that does not begin with $C$ and does not end with $D$.
Therefore, $|S_{10}|=|T_8|$. The number of such strings, $|T_8|$, is equal to \[\begin{array}{cl} & \text{the total number of Bauman strings of length 8}\\ - & \text{the number of Bauman strings of length 8 that begin with } C\\ - & \text{the number of Bauman strings of length 8 that end with } D\\ + & \text{the number of Bauman strings of length 8 that begin with } C \text{ and end with } D \end{array}\] In the above, we note that strings beginning with $C$ include those that end with $D$, as well as others.
Similarly, strings that end with $D$ include those that begin with $C$, as well as others.
Since we have subtracted the number of strings that begin with $C$ and end with $D$ twice from the total, we conclude by adding the number of such strings.

For a Bauman string of length 8, there are 5 choices for the first letter and 4 choices for each of the remaining 7 letters.
Thus, the total number of Bauman strings of length 8 is equal to $5\times4^7$.
For a Bauman string of length 8 that begins with $C$, there is 1 choice for the first letter and 4 choices for each of the remaining 7 letters.
Thus, the total number of Bauman strings of length 8 that begin with $C$ is equal to $1\times4^7$.
Also, the total number of Bauman strings of length 8 that end with $D$ is equal to $1\times4^7$.
The number of Bauman strings of length 8 that begin with $C$ and end with $D$ is equal to $|S_8|$.
Therefore, we get \[|S_{10}|=|T_8|=5\times4^7-1\times4^7-1\times4^7+|S_8|=3\times4^7+|S_8|\] and so the number of Bauman strings of length 10 that begin with $C$ and end with $D$ is dependent on the number of Bauman strings of length 8 that begin with $C$ and end with $D$.
At this point, we could repeat the process above to determine $|S_8|$, however it may be more efficient to generalize the work above to determine a formula for $|S_n|$.

For integers $n\geq3$, each string in $S_{n}$ is of the form $CT_{n-2}D$ where $T_{n-2}$ is a Bauman string of length $n-2$ that does not begin with $C$ and does not end with $D$.
The number of such strings, $|T_{n-2}|$, is equal to \[\begin{array}{cl} & \text{the total number of Bauman strings of length } n-2\\ - & \text{the number of Bauman strings of length } n-2 \text{ that begin with } C\\ - & \text{the number of Bauman strings of length } n-2 \text{ that end with } D\\ + & \text{the number of Bauman strings of length } n-2 \text{ that begin with } C \text{ and end with } D \end{array}\] For a Bauman string of length $n-2$, there are 5 choices for the first letter and 4 choices for each of the remaining $n-3$ letters.
Thus, the total number of Bauman strings of length $n-2$ is equal to $5\times4^{n-3}$.
For a Bauman string of length $n-2$ that begins with $C$, there is 1 choice for the first letter and 4 choices for each of the remaining $n-3$ letters.
Thus, the total number of Bauman strings of length $n-2$ that begin with $C$ is equal to $1\times4^{n-3}$.
Also, the total number of Bauman strings of length $n-2$ that end with $D$ is equal to $1\times4^{n-3}$.
The number of Bauman strings of length $n-2$ that begin with $C$ and end with $D$ is equal to $|S_{n-2}|$.
Therefore, we get \[|S_{n}|=|T_{n-2}|=5\times4^{n-3}-1\times4^{n-3}-1\times4^{n-3}+|S_{n-2}|=3\times4^{n-3}+|S_{n-2}|, \textrm{ for integers } n\geq3.\] Using this recursive formula and the fact that $|S_2|=1$, we get \[\begin{array}{lllllll} |S_4|&=&3\times4^{4-3}+|S_{4-2}|&=&3\times4+|S_2|&=&13\\ |S_6|&=&3\times4^{6-3}+|S_{6-2}|&=&3\times4^3+|S_4|&=&205\\ |S_8|&=&3\times4^{8-3}+|S_{8-2}|&=&3\times4^5+|S_6|&=&3277\\ |S_{10}|&=&3\times4^{10-3}+|S_{10-2}|&=&3\times4^7+|S_8|&=&52\,429 \end{array}\] The number of Bauman strings of length $10$ in which the first letter is $C$ and the last letter is $D$ is 52 429.

\(n\)	\(\|d_n\|=\|x_{n-1}\|\)	\(\|x_n\|=4\|d_{n-1}\| + 3\|x_{n-1}\|\)
1	\(\|d_1\|=0\)	\(\|x_1\|=1\)
2	\(\|d_2\|=1\)	\(\|x_2\|=3\)
3	\(\|d_3\|=\|x_{2}\|=3\)	\(\|x_3\|=4\|d_{2}\| + 3\|x_{2}\|=4(1)+3(3)=13\)
4	\(\|d_4\|=\|x_{3}\|=13\)	\(\|x_4\|=4\|d_{3}\| + 3\|x_{3}\|=4(3)+3(13)=51\)
5	\(\|d_5\|=51\)	\(\|x_5\|=4(13)+3(51)=205\)
6	\(\|d_6\|=205\)	\(\|x_6\|=4(51)+3(205)=819\)
7	\(\|d_7\|=819\)	\(\|x_7\|=4(205)+3(819)=3277\)
8	\(\|d_8\|=3277\)	\(\|x_8\|=4(819)+3(3277)=13\,107\)
9	\(\|d_9\|=13\,107\)	\(\|x_9\|=4(3277)+3(13\,107)=52\,429\)
10	\(\|d_{10}\|=52\,429\)	not needed

2022 Galois Contest Solutions (Grade 10)

2022 Galois Contest
Solutions
(Grade 10)