2018 Canadian Senior
Mathematics Contest
Solutions
Wednesday, November 18, 2018
(in North America and South America)
Thursday, November 19, 2018
(outside of North American and South America)
Wednesday, November 18, 2018
(in North America and South America)
Thursday, November 19, 2018
(outside of North American and South America)
©2018 University of Waterloo
Since each box contains 12 trays, then 6 boxes contain \(12 \times 6 = 72\) trays.
Since Paul has 4 extra trays, then he has \(72+4=76\) trays.
Since each tray can hold 8 apples, then the trays can hold \(76 \times 8 = 608\) apples.
Answer: 608 apples
Since the rabbit runs 3 times as quickly as the skunk, then the rabbit takes \(\frac{1}{3}\) of the time that the skunk takes, or 2 minutes.
Since the rabbit runs 5 times as quickly as the turtle, then the turtle takes 5 times as long as the rabbit, or 10 minutes, to finish the race.
Answer: 10 minutes
Solution 1
With 6 crayons in the box, there are \(\dfrac{6 \times 5}{2} = 15\) pairs of crayons that can be removed. (This is because there are 6 crayons that can be chosen first and 5 crayons that can chosen second; since there are 2 orders in which any specific pair of crayons can be chosen, we divide \(6 \times 5\) by 2.)
Using similar reasoning, with 3 red crayons in the box, there are \(\dfrac{3 \times 2}{2} = 3\) pairs of red crayons that can be removed.
Therefore, the probability that Jakob removes 2 red crayons is \(\dfrac{3}{15}\) or \(\dfrac{1}{5}\).
Solution 2
We label the crayons in the box R1, R2, R3, B1, B2, G1.
The possible pairs that Jakob can choose are
R1R2, R1R3, R1B1, R1B2, R1G1, R2R3, R2B1, R2B2, R2G1,
R3B1, R3B2, R3G1, B1B2, B1G1, B2G1
for a total of 15 pairs.
Of these 15 pairs, three pairs (R1R2, R1R3, R2R3) consist of two red crayons.
Therefore, the probability that Jakob removes 2 red crayons is \(\dfrac{3}{15}\) or \(\dfrac{1}{5}\).
Solution 3
We remove the two crayons one after the other. In order for both crayons to be red, both the first and second crayons removed must be red.
When the first crayon is removed, the probability that it is red is \(\frac{3}{6}\), since there are 6 crayons 3, of which are red.
After 1 red crayon is removed, there are 5 crayons remaining, 2 of which are red.
Therefore, the probability that the second crayon removed is red is \(\frac{2}{5}\).
Thus, the probability that both crayons are red is \(\frac{3}{6} \cdot \frac{2}{5} = \frac{1}{5}\).
Answer: \(\frac{1}{5}\)
Since \(x^2 - 1 = (x+1)(x-1)\), then setting \(x = 10^n\) gives \(10^{2n} - 1 = (10^n+1)(10^n-1)\).
Therefore, \[a = \dfrac{10^{2n}-1}{3(10^n+1)} = \dfrac{(10^n+1)(10^n-1)}{3(10^n+1)} = \dfrac{10^n-1}{3}\] because \(10^n + 1 \neq 0\).
Since \(10^n\) is the integer consisting of a 1 followed by \(n\) 0s, then \(10^n - 1\) is the integer consisting of \(n\) 9s.
Thus, \(a = \dfrac{10^n-1}{3}\) is the integer consisting of \(n\) 3s. This is because each digit 9 in \(10^n-1\) can be divided by 3 to obtain the new digit 3 without any re-grouping (borrowing).
Therefore, the sum of the digits of the integer \(a\) is \(3n\).
Since the sum of the digits of \(a\) is given to be 567, then \(3n = 567\) or \(n = 189\).
Answer: \(n=189\)
When we translate the parabola and hexagon horizontally, the distance between the \(x\)-intercepts of the parabola does not change.
This means that we can position the hexagon and parabola in a horizontal position that is more convenient.
Thus, we position the hexagon and parabola so that the \(y\)-axis passes through the midpoint of \(FE\) and so the hexagon and parabola are symmetric across the \(y\)-axis.
Since \(FE=2\), then the midpoint of \(FE\) is 1 unit from each of \(F\) and \(E\).
In other words, the coordinates of \(F\) and \(E\) are \((-1,0)\) and \((1,0)\), respectively.
Next, we drop a perpendicular from \(D\) to \(P\) on the \(x\)-axis.
Since \(ABCDEF\) is a regular hexagon, then each of its interior angles measures \(120^\circ\). This is because the sum of the interior angles is \(4 \cdot 180^\circ\) or \(720^\circ\) and so each angle is \(\frac{1}{6}\cdot 720^\circ\) which equals \(120^\circ\).
Thus, \(\angle DEP = 180^\circ - 120^\circ = 60^\circ\), which means that \(\triangle DEP\) is a \(30^\circ\)-\(60^\circ\)-\(90^\circ\) triangle.
Since \(DE=2\), then \(EP=1\) and \(DP = \sqrt{3}\).
Since the coordinates of \(E\) are \((1,0)\), then the coordinates of \(D\) are \((1+1,0+\sqrt{3})\) or \((2,\sqrt{3})\).
Similarly, \(C\) is one unit to the left of \(D\) and \(\sqrt{3}\) units above, which means that the coordinates of \(C\) are \((1,2\sqrt{3})\). This is because a right-angled triangle can be drawn with hypotenuse \(CD=2\), legs parallel to the axes, and one angle equal to \(60^\circ\) by reflecting \(\triangle EPD\) through the horizontal line through \(D\).
Since the hexagon is symmetric across the \(y\)-axis, then the coordinates of \(A\) and \(B\) are \((-2,\sqrt{3})\) and \((-1,2\sqrt{3})\), respectively.
Suppose that the parabola has equation \(y=ax^2+bx+c\).
Since the points \((-2,\sqrt{3})\), \((2,\sqrt{3})\) and \((1,2\sqrt{3})\) lie on the parabola, then \[\begin{aligned}
\sqrt{3} & = 4a -2b+ c \\
\sqrt{3} & = 4a +2b +c \\
2\sqrt{3} & = a + b + c\end{aligned}\] Subtracting the second equation from the first, we obtain \(4b=0\) and so \(b=0\). (We could also have determined this using a symmetry argument.)
Substituting into the second and third equations, we obtain \(4a+c=\sqrt{3}\) and \(a+c=2\sqrt{3}\). Subtracting these equations, we obtain \(3a= -\sqrt{3}\) and so \(a = -\frac{\sqrt{3}}{3}\).
Substituting \(a = -\frac{\sqrt{3}}{3}\) into \(a+c=2\sqrt{3}\), we obtain \(c = 2\sqrt{3} - a = 2 \sqrt{3} + \frac{\sqrt{3}}{3} = \frac{7\sqrt{3}}{3}\).
Therefore, the equation of the parabola is \(y = - \frac{\sqrt{3}}{3}x^2 + \frac{7\sqrt{3}}{3}\).
We find the \(x\)-intercepts of the parabola by setting \(y = 0\) to obtain \(0 = - \frac{\sqrt{3}}{3}x^2 + \frac{7\sqrt{3}}{3}\) or \(x^2 = 7\) and so \(x = \pm \sqrt{7}\).
Thus, the parabola crosses the \(x\)-axis at the points \((-\sqrt{7},0)\) and \((\sqrt{7},0)\).
The distance between these two points is \(\sqrt{7} - (-\sqrt{7}) = 2\sqrt{7}\).
Answer: \(2\sqrt{7}\)
Solution 1
When \(0^\circ < A < 90^\circ\) and \(0^\circ < B < 90^\circ\), we know that \(\tan A\) and \(\tan B\) are defined with \(\tan A > 0\) and \(\tan B > 0\).
For all real numbers \(x\) and \(y\), we know that \((x-y)^2 \geq 0\) with equality exactly when \(x = y\).
Rearranging, we obtain \(x^2 - 2xy + y^2 \geq 0\) and \(x^2 + y^2 \geq 2xy\) with equality exactly when \(x=y\).
Setting \(x = 2\) and \(y = \tan A\), we obtain \(4 + \tan^2 A \geq 2(2)(\tan A)\).
Thus, \(4 + \tan^2 A \geq 4\tan A\) with equality exactly when \(\tan A = 2\).
Setting \(x = \sqrt{5}\) and \(y = \tan B\), we obtain \(5 + \tan^2 B \geq 2(\sqrt{5})(\tan B)\).
Thus, \(5 + \tan^2 B \geq 2\sqrt{5}\tan B\) with equality exactly when \(\tan B = \sqrt{5}\).
Since \(4 + \tan^2 A \geq 4\tan A\) and \(5 + \tan^2 B \geq 2\sqrt{5}\tan B\), then \[(4+ \tan^2 A)(5 + \tan^2 B) \geq (4\tan A)(2\sqrt{5}\tan B)\] since all quantities are positive.
For equality to occur in this inequality, we need equality to occur in both of the component inequalities. (If one inequality is actually “\(>\)”, then the product becomes “\(>\)”.) In other words, \((4+ \tan^2 A)(5 + \tan^2 B) = (4\tan A)(2\sqrt{5}\tan B)\) exactly when \(\tan A = 2\) and \(\tan B = \sqrt{5}\).
We note that \[(4\tan A)(2\sqrt{5}\tan B) = 8\sqrt{5} \tan A \tan B = \sqrt{64 \cdot 5}\tan A \tan B = \sqrt{320}\tan A \tan B\] Therefore, \((4+ \tan^2 A)(5 + \tan^2 B) =\sqrt{320}\tan A \tan B\) exactly when \(\tan A = 2\) and \(\tan B = \sqrt{5}\).
We now need to determine the value of \(\cos A \sin B\).
Since \(0^\circ < A < 90^\circ\) and \(0^\circ < B < 90^\circ\), then \(\cos A, \sin A, \cos B, \sin B\) are all positive.
When \(\tan A = 2\), we obtain \(\dfrac{\sin A}{\cos A} = 2\) and so \(\dfrac{\sqrt{1-\cos^2 A}}{\cos A} = 2\) which gives \(1 - \cos^2 A = 4 \cos^2 A\) or \(5 \cos^2 A = 1\).
Since \(\cos A>0\), then \(\cos A = \dfrac{1}{\sqrt{5}}\).
When \(\tan B = \sqrt{5}\), we obtain \(\dfrac{\sin B}{\cos B} = \sqrt{5}\) and so \(\dfrac{\sin B}{\sqrt{1-\sin^2 B}} = \sqrt{5}\).
This gives \(\sin^2 B = 5 - 5\sin^2 B\) or \(6 \sin^2 B = 5\).
Since \(\sin B>0\), then \(\sin B = \dfrac{\sqrt{5}}{\sqrt{6}}\).
Finally, this gives \(\cos A \sin B = \dfrac{1}{\sqrt{5}} \cdot \dfrac{\sqrt{5}}{\sqrt{6}} = \dfrac{1}{\sqrt{6}}\).
Solution 2
Let \(X = \tan A\) and \(Y = \tan B\).
The given equation becomes successively: \[\begin{aligned}
(4+X^2)(5+Y^2) & = \sqrt{320}XY \\
X^2Y^2 + 5X^2 + 4Y^2 + 20 & = 8\sqrt{5}XY \\
X^2Y^2 - 8\sqrt{5}XY + 5X^2 + 4Y^2 + 20 & = 0 \\
X^2Y^2 - 2(2\sqrt{5})XY + 20 + 5X^2 + 4Y^2 - 4\sqrt{5}XY & = 0 \\
X^2Y^2 - 2(2\sqrt{5})XY + (2\sqrt{5})^2 + 5X^2 + 4Y^2 - 4\sqrt{5}XY & = 0 \\
(XY - 2\sqrt{5})^2 + 5X^2 - 4\sqrt{5}XY + 4Y^2 & = 0 \\
(XY - 2\sqrt{5})^2 + (\sqrt{5}X)^2 - 2(\sqrt{5}X)(2Y) + (2Y)^2 & = 0 \\
(XY - 2\sqrt{5})^2 + (\sqrt{5}X-2Y)^2 & = 0\end{aligned}\] For the sum of squares to be 0, each part must equal 0.
Therefore, \(XY = 2\sqrt{5}\) and \(\sqrt{5}X = 2Y\).
From the first equation, \(X(2Y) = 4\sqrt{5}\) and so \(X(\sqrt{5}X) = 4\sqrt{5}\) which gives \(X^2 = 4\) or \(X = \pm 2\).
Since \(0^\circ < A < 90^\circ\), then \(X = \tan A > 0\) and so \(X = \tan A = 2\).
Since \(2Y = \sqrt{5}X\), then \(Y = \tan B = \sqrt{5}\).
We can then proceed as in Solution 1 to obtain \(\cos A \sin B = \dfrac{1}{\sqrt{6}}\).
Answer: \(\dfrac{1}{\sqrt{6}}\)
To find the \(x\)-intercept of the line with equation \(y=3x+6\), we set \(y=0\) to obtain \(3x+6=0\) or \(3x=-6\) and so \(x=-2\).
Therefore, the \(x\)-intercept is \(-2\).
Solution 1
To find the equation of the line that is symmetric across the \(y\)-axis with the line with the equation \(y=3x+6\), we reverse the sign of the slope and keep the same \(y\)-intercept to obtain \(y=-3x+6\).
Solution 2
The line with equation \(y=3x+6\) has \(x\)-intercept \(-2\) (from (a)) and \(y\)-intercept 6 (from the equation of the line).
Since the letter A is symmetric about the \(y\)-axis, the right side of the letter A will lie along the line with \(x\)-intercept 2 (that is, \(-(-2)\)) and \(y\)-intercept 6.
The equation of this line is thus of the form \(y = mx + 6\) for some \(m\).
Since it passes through the point \((2,0)\), then \(0 = 2m+6\) and so \(2m=-6\) or \(m=-3\).
Thus, the equation of this line is \(y=-3x+6\).
Since the \(x\)-intercepts of the lines that form the sides are \(-2\) and \(2\), then the base of the triangle has length \(2-(-2)=4\).
Since both lines pass through \((0,6)\), then the height of the triangle is 6.
Therefore, the area of the triangle is \(\frac{1}{2} \cdot 4 \cdot 6 = 12\).
Solution 1
We note first that \(c<6\).
Since the top vertex of the shaded triangle lies at \(y=6\) and the base of the triangle lies along \(y=c\), then the height of the shaded triangle is \(6-c\).
The bottom right vertex of the shaded triangle lies at the point of intersection of the line with equation \(y=-3x+6\) and the line with equation \(y=c\).
At this point, \(c=-3x+6\) and so \(3x = 6-c\) and so \(x = \dfrac{6-c}{3}\).
By symmetry, the \(x\)-coordinate of the bottom left vertex is \(-\dfrac{6-c}{3}\).
Therefore, the base of the shaded triangle has length \(\dfrac{6-c}{3} - \left(-\dfrac{6-c}{3}\right) = \dfrac{2(6-c)}{3}\).
Since the area of the shaded triangle is \(\dfrac{4}{9}\) of the area of the original triangle, then the area of the shaded triangle is \(\dfrac{4}{9} \cdot 12 = \dfrac{16}{3}\).
Putting all of this together and using the area obtain in (c), we have \[\begin{aligned}
\dfrac{1}{2} \cdot \dfrac{2(6-c)}{3} \cdot (6-c) & = \dfrac{16}{3} \\
\dfrac{1}{3} (6-c)^2 & = \dfrac{16}{3} \\
(6-c)^2 & = 16 \\
6-c & = \pm 4\end{aligned}\] Since \(c<6\), then \(6-c>0\) and so \(6-c=4\) which gives \(c=2\).
Solution 2
Since the base of the shaded triangle is parallel to the base of the larger triangle, then their base angles are equal and so the triangles are similar.
Since the area of the shaded triangle is \(\dfrac{4}{9}\) of the area of the larger triangle, then the side lengths of the shaded triangle are \(\sqrt{\dfrac{4}{9}} = \dfrac{2}{3}\) of the corresponding side lengths of the larger triangle.
Furthermore, the height of the shaded triangle is \(\dfrac{2}{3}\) that of the larger triangle.
Since the height of the larger triangle is 6, then the height of the shaded triangle is \(\dfrac{2}{3} \cdot 6\) which equals \(4\).
Since the top vertex of the shaded triangle lies at \(y=6\) and the base of the triangle lies along \(y=c\), then the height of the shaded triangle is \(6-c\).
Thus, \(6-c=4\) and so \(c=2\).
Re-arranging and noting that \(x \neq 0\), we obtain the following equivalent equations: \[\begin{aligned} \dfrac{1}{4} - \dfrac{1}{x} & = \dfrac{1}{6} \\[1mm] \dfrac{1}{4} - \dfrac{1}{6} & = \dfrac{1}{x} \\[1mm] \dfrac{3}{12} - \dfrac{2}{12} & = \dfrac{1}{x} \\[1mm] \dfrac{1}{12} & = \dfrac{1}{x}\end{aligned}\] and so \(x=12\).
Factoring, we obtain the following equivalent equations: \[\begin{aligned}
ab - b + a - 1 & = 4 \\
b(a-1) + (a-1) & = 4 \\
(a-1)(b+1) & = 4\end{aligned}\] Since \(a\) and \(b\) are integers, then \(a-1\) and \(b+1\) are integers. Therefore, \(b+1\) and \(a-1\) are a divisor pair of 4.
Since \(b \geq 1\), then \(b+1 \geq 2\).
Since \(b+1 > 0\) and \(4>0\) and \((a-1)(b+1)=4\), then \(a-1>0\).
This means that \(b+1\) and \(a-1\) must form a positive divisor pair of 4 with \(b+1 \geq 2\).
There are two possibilities:
\(b+1=2\) and \(a-1 = 2\); this gives \((a,b) = (3,1)\).
\(b+1=4\) and \(a-1 = 1\); this gives \((a,b) = (2,3)\).
Therefore, the pairs of positive integers that solve the equation are \((3,1)\) and \((2,3)\).
Since \(y \neq 0\) and \(z \neq 0\), we multiply the given equation by \(12yz\) and manipulate to obtain the following equivalent equations: \[\begin{aligned}
\dfrac{1}{y} - \dfrac{1}{z} & = \dfrac{1}{12} \\
12z - 12y & = yz \\
0 & = yz +12y - 12z \\
0 & = y(z+12) - 12z \\
-144 & = y(z+12) - 12z - 144 \\
-144 & = y(z+12) - 12(z+12) \\
-144 & = (y-12)(z+12)\end{aligned}\] Since \(y\) and \(z\) are integers, then \(y-12\) and \(z+12\) are integers.
Since \(z > 0\), then \(z+12 > 0\).
Since \(-144<0\) and \(z+12>0\) and \((y-12)(z+12)=-144\), then \(y-12<0\).
Since \(y\) is a positive integer, then \(1 \leq y \leq 11\). This makes \(y-12 > -12\).
Since \((y-12)(z+12) = -144\) and \(y-12<0\), then \(y-12\) and \(z+12\) are a divisor pair of \(-144\) with \(-12 < y -12 < 0\).
We make a table to determine the possible values:
| \(y-12\) | \(z+12\) | \(y\) | \(z\) |
|---|---|---|---|
| \(-1\) | \(144\) | \(11\) | \(132\) |
| \(-2\) | \(72\) | \(10\) | \(60\) |
| \(-3\) | \(48\) | \(9\) | \(36\) |
| \(-4\) | \(36\) | \(8\) | \(24\) |
| \(-6\) | \(24\) | \(6\) | \(12\) |
| \(-8\) | \(18\) | \(4\) | \(6\) |
| \(-9\) | \(16\) | \(3\) | \(4\) |
Since \(r \neq 0\) and \(s \neq 0\) and \(p \geq 2\), we multiply the given equation by \(p^2rs\) and manipulate to obtain the following equivalent equations: \[\begin{aligned}
\dfrac{1}{r} - \dfrac{1}{s} & = \dfrac{1}{p^2} \\
p^2s - p^2r & = rs \\
0 & = rs +p^2r - p^2s \\
0 & = r(s+p^2) - p^2s \\
-p^4 & = r(s+p^2) - p^2s -p^4\\
-p^4 & = r(s+p^2) - p^2(s+p^2)\\
-p^4 & = (r-p^2)(s+p^2)\end{aligned}\] Since \(r\) and \(s\) are integers, then \(r-p^2\) and \(s+p^2\) are integers.
Since \(s > 0\), then \(s+p^2 > 0\).
Since \(-p^4<0\) and \(s+p^2>0\) and \((r-p^2)(s+p^2)=-p^4\), then \(r-p^2<0\).
Since \(r\) is a positive integer, then \(1 \leq r < p^2\).
Since \((r-p^2)(s+p^2) = -p^4\) and \(r-p^2<0\), then \(r-p^2\) and \(s+p^2\) are a divisor pair of \(-p^4\) with \(-p^2 < r - p^2 < 0\).
We consider the possibilities that \(r-p^2 = -1\) and \(r-p^2 = -p\).
In these cases, \(s+p^2 = p^4\) and \(s+p^2 = p^3\), respectively.
These give the pairs \((r,s) = (p^2-1,p^4-p^2)\) and \((r,s)=(p^2-p,p^3-p^2)\).
Since \(p\) is prime, then \(p \geq 2\), which means that these pairs are distinct and that each component is a positive integer.
Therefore, there are at least two pairs \((r,s)\) of positive integers for which \(\dfrac{1}{r} - \dfrac{1}{s} = \dfrac{1}{p^2}\).
If \(AB\) and \(BA\) both occur as substrings, they either overlap as \(ABA\) or \(BAB\) or they do not overlap.
If they do not overlap, then such a string must be \(ABBA\) or \(BAAB\). Since the strings have length 4, there are no other possibilities.
A 4 character string including the substring \(ABA\) can have this substring start in either the 1st or 2nd position, which gives the possibilities: \[ABAA \quad ABAB \quad ABAC \quad AABA \quad BABA \quad CABA\] A 4 character string including the substring \(BAB\) can have this substring start in either the 1st or 2nd position, which gives the possibilities: \[BABA \quad BABB \quad BABC \quad ABAB \quad BBAB \quad CBAB\] Removing duplicate strings, we obtain the list \[ABBA \quad BAAB \quad ABAA \quad ABAB \quad ABAC \quad AABA\] \[BABA \quad CABA \quad BABB \quad BABC \quad BBAB \quad CBAB\] (There are 12 such strings.)
Solution 1
Since there are 3 choices for each character in such a string, then there are \(3^7 = 2187\) strings of length 7 with characters from the set \(\{A,B,C\}\) and no further restrictions.
We count the number of such strings that do not include the substring \(CC\) and subtract this total from \(2187\) to obtain our desired answer.
Let \(t_n\) be the number of strings of length \(n\) with characters from \(\{A,B,C\}\) that do not contain the substring \(CC\).
Let \(a_n\) be the number of strings of length \(n\) with characters from \(\{A,B,C\}\) that do not contain the substring \(CC\) and whose \(n\)th character (i.e. rightmost character) is \(A\).
Let \(b_n\) be the number of strings of length \(n\) with characters from \(\{A,B,C\}\) that do not contain the substring \(CC\) and whose \(n\)th character (i.e. rightmost character) is \(B\).
Let \(c_n\) be the number of strings of length \(n\) with characters from \(\{A,B,C\}\) that do not contain the substring \(CC\) and whose \(n\)th character (i.e. rightmost character) is \(C\).
Note that \(t_n = a_n + b_n + c_n\) since each string ends in \(A\), \(B\) or \(C\).
Also, \(a_1 = b_1 = c_1 = 1\) (the strings \(A\), \(B\) and \(C\)), which means that \(t_1 = 1+1+1=3\).
Suppose that \(n \geq 2\).
Consider a string of length \(n\) that ends with \(A\) and does not contain \(CC\). The second last character can be any of \(A\), \(B\) or \(C\). This means that the first \(n-1\) characters are a string of length \(n-1\) that ends in \(A\), \(B\) or \(C\), and so \(a_n = a_{n-1} + b_{n-1} + c_{n-1}\).
Consider a string of length \(n\) that ends with \(B\) and does not contain \(CC\). The second last character can be any of \(A\), \(B\) or \(C\). This means that the first \(n-1\) characters are a string of length \(n-1\) that ends in \(A\), \(B\) or \(C\), and so \(b_n = a_{n-1} + b_{n-1} + c_{n-1}\).
Consider a string of length \(n\) that ends with \(C\) and does not contain \(CC\). The second last character can be either \(A\) or \(B\). (It cannot be \(C\) otherwise, there would be an occurrence of the substring \(CC\).) This means that the first \(n-1\) characters are a string of length \(n-1\) that ends in \(A\) or \(B\), and so \(c_n = a_{n-1} + b_{n-1}\).
Therefore, \[\begin{aligned}
a_2 & = a_1 + b_1 + c_1 = 1 + 1 + 1 = 3 \\
b_2 & = a_1 + b_1 + c_1 = 1 + 1 + 1 = 3 \\
c_2 & = a_1 + b_1 = 1 + 1 = 2\end{aligned}\] and \[\begin{aligned}
a_3 & = a_2 + b_2 + c_2 = 3 + 3 + 2 = 8 \\
b_3 & = a_2 + b_2 + c_2 = 3 + 3 + 2 = 8 \\
c_3 & = a_2 + b_2 = 3 + 3 = 6\end{aligned}\] Continuing in this way, we can build a table:
| \(n\) | \(a_n\) | \(b_n\) | \(c_n\) |
|---|---|---|---|
| \(1\) | \(1\) | \(1\) | \(1\) |
| \(2\) | \(3\) | \(3\) | \(2\) |
| \(3\) | \(8\) | \(8\) | \(6\) |
| \(4\) | \(22\) | \(22\) | \(16\) |
| \(5\) | \(60\) | \(60\) | \(44\) |
| \(6\) | \(164\) | \(164\) | \(120\) |
| \(7\) | \(448\) | \(448\) | \(328\) |
First, we calculate \(f(2097)\).
Every string counted by \(f(2097)\) has a first occurrence of the substring \(CC\).
Starting from the left, this first occurrence can begin in any of the positions \(1,2,3,\ldots, 2096\). (It cannot begin in the last position.)
Suppose that \(k\) is a positive integer with \(1 \leq k \leq 2096\).
We determine the number of strings counted by \(f(2097)\) whose first occurrence of \(CC\) begins in position \(k\).
In such a string, positions \(k\) and \(k+1\) are \(CC\).
This leaves \(k-1\) positions to the left of the \(CC\) and \(2097-(k+1)= 2096-k\) positions to the right.
Based on the restrictions for the string, there are no restrictions for the characters in each of the \(2096-k\) positions to the right of \(CC\).
Therefore, there are 3 choices for each of these positions and so \(3^{2096-k}\) ways to fill these \(2096-k\) positions.
For the \(k-1\) positions to the left of \(CC\), there are two restrictions: no substring \(AB\) or \(BA\) can occur (from the given restrictions) and no substring \(CC\) can occur (since the \(CC\) in positions \(k\) and \(k+1\) is the first such substring).
Since position \(k\) is \(C\), then position \(k-1\) cannot be \(C\) and so must be \(A\) or \(B\). Thus, there are 2 choices for position \(k-1\).
If position \(k-1\) were \(A\), then position \(k-2\) could be \(A\) or \(C\), but not \(B\) (as this would create a substring \(BA\)). In this case, there are 2 choices for position \(k-2\).
If position \(k-1\) were \(B\), then position \(k-2\) could be \(B\) or \(C\), but not \(A\) (as this would create a substring \(AB\)). In this case, there are 2 choices for position \(k-2\).
In general, if we consider the character at position \(j\) for some \(j\) with \(2 \leq j \leq k\), then
if position \(j\) is \(A\), position \(j-1\) must be \(A\) or \(C\),
if position \(j\) is \(B\), position \(j-1\) must be \(B\) or \(C\), and
if position \(j\) is \(C\), position \(j-1\) must be \(A\) or \(B\).
In other words, for each position from \(k-1\) back to \(1\), there are 2 choices for the character, giving \(2^{k-1}\) choices overall for these characters.
Note that this formula is valid when \(k=1\) since this gives “1 choice” for the non-existent preceding characters which does not affect the formula that follows.
Therefore, there are \(2^{k-1}3^{2096-k}\) strings that obey the given restrictions whose first occurrence of \(CC\) begins in position \(k\).
Adding from \(k=1\) to \(k=2096\), we obtain \[\begin{aligned}
f(2097)
& = 2^0 3^{2095} + 2^1 3^{2094} + 2^2 3^{2093} + \cdots + 2^{2093} 3^{2} + 2^{2094} 3^{1} + 2^{2095} 3^{0} \\
& = 3^{2095}\left( 1 + \dfrac{2}{3} + \dfrac{2^2}{3^2} + \cdots + \dfrac{2^{2093}}{3^{2093}} + \dfrac{2^{2094}}{3^{2094}}+ \dfrac{2^{2095}}{3^{2095}}\right)\\
& = 3^{2095}\left( 1 + \left(\dfrac{2}{3}\right)^1 + \left(\dfrac{2}{3}\right)^2 + \cdots +\left(\dfrac{2}{3}\right)^{2093} + \left(\dfrac{2}{3}\right)^{2094} +\left(\dfrac{2}{3}\right)^{2095}\right)\\
& = 3^{2095}\left(\dfrac{1\left(1-\left(\tfrac{2}{3}\right)^{2096}\right)}{1 - \tfrac{2}{3}}\right) \\
& = 3^{2095}\left(\dfrac{1-\left(\tfrac{2}{3})^{2096}\right)}{ \tfrac{1}{3}}\right) \\
& = 3^{2096}\left(1-\left(\tfrac{2}{3}\right)^{2096}\right)\\
& = 3^{2096} - 2^{2096}\end{aligned}\] To show that \(f(2097) = 3^{2096} - 2^{2096}\) is divisible by 97, we use the fact that, for all real numbers \(x\) and \(y\), \[x^n - y^n = (x-y)(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + \cdots + x^2y^{n-3} + xy^{n-2} + y^{n-1})\] Setting \(x=3^8\) and \(y=2^8\) and \(n=262\), we get \[\begin{aligned}
f(2097)
& = (3^8)^{262} - (2^8)^{262} \\
& = x^{262} - y^{262} \\
& = (x-y)(x^{261} + x^{260}y + \cdots + xy^{260} + y^{261}) \\
& = (3^8 - 2^8)((3^8)^{261} + (3^8)^{260}2^8 + \cdots + 3^8(2^8)^{260} + (2^8)^{261})\\
& = (3^4 + 2^4)(3^4-2^4)((3^8)^{261} + (3^8)^{260}2^8 + \cdots + 3^8(2^8)^{260} + (2^8)^{261})\end{aligned}\] factoring a difference of squares in the last step.
Since \(3^4+2^4=81+16=97\) and the remaining two factors are integers, then \(f(2097)\) is a multiple of 97, as required.