2025 Canadian Intermediate
Mathematics Contest
Solutions
Wednesday, November 12, 2025
(in North America and South America)
Thursday, November 13, 2025
(outside of North American and South America)
Wednesday, November 12, 2025
(in North America and South America)
Thursday, November 13, 2025
(outside of North American and South America)
©2025 University of Waterloo
Solution 1
Since \(85\%\) of the donkeys in the
sanctuary are adults and the rest are babies, \(100\%-85\% = 15\%\) of the donkeys in the
sanctuary are babies.
Since \(10\%\) of \(140\) is \(14\), \(5\%\) of \(140\) is \(7\), and so \(15\%\) of \(140\) is \(14+7=21\).
Therefore, there are \(21\) baby
donkeys in the sanctuary.
Solution 2
Since \(85\%\) of the \(140\) donkeys in the sanctuary are adults,
there are \(0.85 \times 140 = 119\)
adult donkeys in the sanctuary.
The remaining donkeys are babies and so there are \(140 - 119 = 21\) baby donkeys in the
sanctuary.
Answer: \(21\)
Solution 1
Since the number of stamps that Paige has is a multiple of \(5\) and the total number of stamps that
Jimmy and Paige have together is \(18\), Paige must have \(5\), \(10\), or \(15\) stamps.
Since Jimmy has an even number of stamps and the total number of stamps
is even, Paige must also have an even number of stamps.
Therefore, Paige has \(10\) stamps and
Jimmy has \(18 - 10 = 8\) stamps.
Solution 2
Since the number of stamps that Jimmy has is even, we can represent
this number by \(2a\) where \(a\) is a positive integer.
Since the number of stamps that Paige has is a multiple of \(5\), we can represent this number by \(5b\) where \(b\) is a positive integer.
Since the total number of stamps that they have together is \(18\), we have that \(2a + 5b = 18\).
Since \(18\) and \(2a\) are even, \(5b\) must be even and so \(b\) must be even.
Since \(5\times 4 = 20\) is greater
than \(18\), \(b\) must be less than \(4\).
This means \(b=2\) and so Paige has
\(5b = 5\times 2 = 10\) stamps.
Therefore, Jimmy has \(18 - 10 = 8\)
stamps.
Answer: \(8\)
Solution 1
From the information given, increasing the volume of water from \(\frac{1}{3}\) of the capacity of the vase
to \(\frac{2}{3}\) of the capacity of
the vase results in an increase in mass of \(800 \text{ g}- 600 \text{ g} = 200 \text{
g}\).
In other words, adding a volume of water equal to \(\frac{1}{3}\) of the capacity of the vase
results in an increase in mass of \(200 \text{
g}\).
This means that the mass of the water when the vase is filled to \(\frac{1}{3}\) of its capacity is \(200 \text{ g}\).
Therefore, the mass of the empty vase is \(600
\text{ g}- 200 \text{ g}= 400 \text{ g}\).
Solution 2
Suppose that the mass, in grams, of the empty vase is \(v\) and that the mass, in grams, of the
volume of water needed to fill the vase to \(\frac{1}{3}\) of its capacity is \(w\).
From the information given, we have that \(v +
w = 600\) and \(v + 2w =
800\).
Rearranging the first equation gives \(w =
600-v\).
Substituting this expression into the second equation gives \(800 = v + 2w = v + 2(600-v)\) which
simplifies to \(800 = v + 1200 - 2v\)
or \(800 = 1200 - v\).
Therefore, \(v = 1200-800 = 400\) and
so the mass of the empty vase is \(400\text{
g}\).
Answer: \(400 \text{ g}\)
First, we plot \(\triangle AOB\) on the Cartesian plane and draw a line segment from point \(C\) on side \(AB\) to each of sides \(OA\) and \(OB\), meeting each side at a right angle.
Solution 1
A base of \(\triangle AOC\) is \(OA = 2\) and the corresponding height is
the horizontal distance from the \(y\)-axis to point \(C\), which is equal to \(9a\).
Thus, the area of \(\triangle AOC\) is
\(\frac{1}{2} \times 2 \times 9a =
9a\).
A base of \(\triangle BOC\) is \(OB = 6\) and the corresponding height is
the vertical distance from the \(x\)-axis to point \(C\), which is equal to \(a\).
Thus, the area of \(\triangle BOC\) is
\(\frac{1}{2} \times 6 \times a =
3a\).
Therefore, the ratio of the area of \(\triangle AOC\) to the area of \(\triangle BOC\) is \(9a:3a\) or \(3:1\).
Solution 2
The slope of the line through points \(A(0,2)\) and \(B(6,0)\) is \(m =
\frac{2-0}{0-6} = - \frac{1}{3}\) and so an equation for this
line is \(y = -\frac{1}{3}x +
2\).
Since \(C(9a,a)\) is on line segment
\(AB\), it must satisfy the equation of
the line given above.
This means \(a = -\frac{1}{3}(9a) + 2\)
which simplifies to \(a = -3a + 2\) or
\(4a = 2\) and so \(a = \frac{1}{2}\).
Therefore, the coordinates of \(C\) are
\(\bigr(\frac{9}{2}, \frac{1}{2}\bigr) =
(4.5,0.5)\).
Using the coordinates of \(C\), we can
calculate the area of each triangle.
The base of \(\triangle AOC\) is \(OA = 2\) and the corresponding height is
the horizontal distance from the \(y\)-axis to point \(C\), which is \(\frac{9}{2}\).
Thus, the area of \(\triangle AOC\) is
\(\frac{1}{2} \times 2 \times \frac{9}{2} =
\frac{9}{2}\).
The base of \(\triangle BOC\) is \(OB = 6\) and the corresponding height is
the vertical distance from the \(x\)-axis to point \(C\), which is \(\frac{1}{2}\).
Thus, the area of \(\triangle BOC\) is
\(\frac{1}{2} \times 6 \times \frac{1}{2} =
\frac{3}{2}\).
Therefore, the ratio of the area of \(\triangle AOC\) to the area of \(\triangle BOC\) is \(\frac{9}{2}:\frac{3}{2}\) or \(3:1\).
Answer: \(3:1\)
The total number of minutes from the beginning of the first meeting to the end of the last meeting is \(3\times 60=180\). Let \(m\) be the number of minutes in each meeting, and let \(b\) be the number of minutes in each break. As defined in the problem, let \(n\) be the number of meetings.
Since the afternoon starts with a meeting and ends with a meeting, the number of breaks should be one less than the number of meetings. One way to think about this is to note that every meeting except for the final meeting has a break after it.
Thus, the total number of minutes that Raya will spend in meetings is \(n\times m\), and the total number of minutes that Raya will spend in breaks is \((n-1)\times b\). Thus, we have the equation \(nm + (n-1)b = 180\), which can be expanded to get \(nm+nb-b=180\).
From the third condition of the problem statement, we also have that each meeting is \(10\) minutes longer than each break, which means \(b=m-10\). If we substitute this into \(nm+nb-b=180\), we get \[nm+n(m-10)-(m-10)=180\] After expanding, we get \(nm+nm-10n-m+10=180\), which can be rearranged to get \(2nm-10n = m+170\). Factoring leads to \(2n(m-5) = m+170\) and solving for \(2n\) gives \[2n=\dfrac{m+170}{m-5}\] We note that \(m\) must be greater than \(10\) since the length of each break, which is \(m-10\), must be positive. This can be rewritten as \(2n = \dfrac{(m-5) + 175}{m-5}\), from which it follows that \(2n = 1+\dfrac{175}{m-5}\).
The quantity \(2n\) is an even positive integer. For it to be equal to \(1+\dfrac{175}{m-5}\), we need \(\dfrac{175}{m-5}\) to be an odd positive integer. Note that, since the numerator is odd, \(\dfrac{175}{m-5}\) will automatically be odd if it is an integer. Therefore, we need to determine values of \(m\) so that \(m-5\) is a positive factor of \(175\).
The positive factors of \(175\) are \(1\), \(5\), \(7\), \(25\), \(35\), and \(175\). Since \(m\) must be greater than \(10\), the values of \(m-5=1\) and \(m-5=5\) must be rejected. This means \(m-5\) is equal to \(7\), \(25\), \(35\), or \(175\). These correspond to \(m\) values of \(12\), \(30\), \(40\), and \(180\), respectively.
If \(m=180\), then there could only be one meeting that takes up the entire afternoon. We are told that \(n\geq 2\), so we also reject \(m=180\).
The other three cases work. If \(m=12\), then \(2n= 1 + \dfrac{175}{7}=26\), or \(n=13\). Indeed, if there are \(13\) meetings of length \(12\) minutes with \(13-1=12\) breaks of length \(12-10=2\) minutes, then the total time would be \(13\times 12 + 12\times 2 = 156+24=180\) minutes. Similarly, one can check that when the meeting length is \(30\) minutes, the number of meetings is \(4\), and when the meeting length is \(40\) minutes, the number of meetings is \(3\).
Therefore, there are three possibilities for \(n\) and they are \(3\), \(4\), and \(13\).
Answer: \(3\), \(4\), \(13\)
We will start by considering the values of \([2x]+[3x]+[5x]+[7x]\) for \(x\) with \(0\leq x < 1\).
The value of \([2x]\) is either \(0\) or \(1\) depending on if \(0\leq x < \frac{1}{2}\) or \(\frac{1}{2} \leq x < 1\), respectively. To see this suppose \(0\leq x < \frac{1}{2}\). Then \(2(0) \leq 2x < 2\left(\frac{1}{2}\right)\) or \(0 \leq 2x < 1\). Therefore \([2x]=0\) in this case. On the other hand, if \(\frac{1}{2}\leq x < 1\), then multiplying through by \(2\) gives \(1\leq 2x < 2\), and so \([2x]=1\).
We have shown that for \(0 \leq x <1\), the contribution of \([2x]\) to the sum is determined by whether \(x<\frac{1}{2}\) or not.
Similar reasoning can be used to determine the value of \([3x]\) depending on whether \(0\leq x <\frac{1}{3}\) or \(\frac{1}{3} \leq x < \frac{2}{3}\) or \(\frac{2}{3} \leq x < 1\). (Note that all \(x\) with \(0\leq x<1\) satisfy exactly one of these three conditions.)
Multiplying the inequalities in each of these three cases by \(3\) gives \(0 \leq 3x < 1\), \(1\leq 3x < 2\), and \(2\leq 3x < 3\). Thus, \([3x]\) is equal to \(0\), \(1\), or \(2\), depending on which of \(0\leq x <\frac{1}{3}\), \(\frac{1}{3} \leq x < \frac{2}{3}\), and \(\frac{2}{3} \leq x < 1\) is true.
Continuing this reasoning, we can determine the values of \([5x]\) and \([7x]\) depending on where \(x\) lies on the number line between \(0\) and \(1\). The results are summarized in the tables below.
| \(x\) | \(0\leq x < \frac{1}{7}\) | \(\frac{1}{7} \leq x < \frac{2}{7}\) | \(\frac{2}{7} \leq x < \frac{3}{7}\) | \(\frac{3}{7} \leq x < \frac{4}{7}\) | \(\frac{4}{7} \leq x < \frac{5}{7}\) | \(\frac{5}{7} \leq x < \frac{6}{7}\) | \(\frac{6}{7} \leq x < 1\) |
|---|---|---|---|---|---|---|---|
| \([7x]\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) |
| \(x\) | \(0\leq x < \frac{1}{5}\) | \(\frac{1}{5} \leq x < \frac{2}{5}\) | \(\frac{2}{5} \leq x < \frac{3}{5}\) | \(\frac{3}{5} \leq x < \frac{4}{5}\) | \(\frac{4}{5} \leq x < 1\) |
|---|---|---|---|---|---|
| \([5x]\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) |
| \(x\) | \(0\leq x < \frac{1}{3}\) | \(\frac{1}{3} \leq x < \frac{2}{3}\) | \(\frac{2}{3} \leq x < 1\) |
|---|---|---|---|
| \([3x]\) | \(0\) | \(1\) | \(2\) |
| \(x\) | \(0\leq x < \frac{1}{2}\) | \(\frac{1}{2} \leq x < 1\) |
|---|---|---|
| \([2x]\) | \(0\) | \(1\) |
We now imagine \(x\) starting at \(0\) and moving very slowly from \(0\) to \(1\) but not actually reaching \(1\). The sum \([2x]+[3x]+[5x]+[7x]\) will start at \(0\) since \([0]=0\). The sum will only increase when \(x\) reaches and crosses one of the values \[\frac{1}{2},\frac{1}{3},\frac{2}{3},\frac{1}{5},\dots,\frac{4}{5},\frac{1}{7},\dots,\frac{6}{7}\] If, for example, \(x\) goes from slightly below \(\frac{4}{7}\) to slightly above \(\frac{4}{7}\), then the value of \([7x]\) will increase by \(1\), so the sum \([2x]+[3x]+[5x]+[7x]\) will also increase by \(1\). We note that the fractions listed above are all distinct, so this sum will only ever increase by \(1\) at a time. In fact, placing these fractions on a number line, we have the following:
When \(0 \leq x < \frac{1}{7}\), \([2x]=[3x]=[5x]=[7x]=0\), so the sum is \(0\). Just as \(x\) crosses \(\frac{1}{7}\), that is, when \(\frac{1}{7}\leq x < \frac{1}{5}\), we have \([7x]=1\), while \([2x]=[3x]=[5x]=0\), so the sum is \(1\). Then when \(x\) crosses \(\frac{1}{5}\) and \(\frac{1}{5}\leq x < \frac{2}{7}\), we have \([5x]=[7x]=1\) while \([2x]=[3x]=0\), so the sum is \(0+0+1+1=2\). Thus, the values of \([2x]+[3x]+[5x]+[7x]\) will increase from \(0\), incrementally by \(1\), until \(13\) since there are \(13\) special values that \(x\) will cross. Thus, if \(0\leq x < 1\), there are \(14\) distinct integer values that \([2x]+[3x]+[5x]+[7x]\) can take.
We will use the following observation. Suppose \(a\) is an integer and \(x\) is a real number. Then \([a+x] = a+[x]\). This is really saying that if \(x\) is increased by an integer value, then its integer part will increase by that integer. We leave it to the reader to become convinced of this.
Now, consider a fixed positive integer \(k\) and a real number \(x\) satisfying \(k \leq x < k+1\). Then there is some real number \(y\) with \(0\leq y < 1\) such that \(x=k+y\). Then we have \[\begin{align*} + [3x] + [5x] + [7x] &= [2(k+y)] + [3(k+y)] + [5(k+y)] + [7(k+y)] \\ &= [2k+2y] + [3k+3y] + [5k+5y] + [7k+7y] \\ &= 2k+[2y] + 3k+[3y] + 5k+[5y] + 7k+[7y] \\ &= 17k + [2y]+[3y]+[5y]+[7y]\end{align*}\] As \(x\) ranges from \(k\) to \(k+1\), \(y\) ranges from \(0\) to \(1\) (not including \(1\)), and so the value of \([2y]+[3y]+[5y]+[7y]\) takes on the integers from \(0\) through \(13\) inclusive. Since \(k\) is fixed, we have that \([2x]+[3x]+[5x]+[7x]\) ranges from \(17k+0\) to \(17k+13\) inclusive.
We now have that when \(0 \leq x < 1\), \([2x]+[3x]+[5x]+[7x]\) takes on the values from \(0\) through \(13\) inclusive, when \(1 \leq x < 2\), \([2x]+[3x]+[5x]+[7x]\) takes on the values from \(17(1)+0 = 17\) through \(17(1)+13 =30\) inclusive, and so on. It remains to count the integers in these lists that are in the given range: \(1 \leq n \leq 2025\).
Excluding the value of \(n=0\), the first range for \(x\) contributes \(13\) integers to the count (\(1\) through \(13\)). Since \(2025 = 17(119) + 2\), the ranges corresponding to \(k=1\) through \(k=118\) each contribute \(14\) integers to the count for a total of \(118 \times 14 = 1652\) additional integers. The range corresponding to \(k=119\) contributes three additional integers: \(17(119) + 0 = 2023\), \(17(119) + 1 = 2024\), and \(17(119) + 2 = 2025\).
Therefore, there are \(13 + 1652 + 3 = 1668\) integers \(n\) with \(1 \leq n \leq 2025\) and the given property.
Answer: \(1668\)
Using the given formula with width \(x = 3\), length \(y = 6\), and height \(z = 11\), we calculate \[2(xy + xz + yz) = 2(3 \times 6 + 3\times 11 + 6 \times 11) = 2(18+33+66) = 2(117) = 234.\] Therefore, the surface area of the prism is \(234 \text{ cm}^{2}\).
Using the given formula with width \(x=2a\), length \(y=4a\), and height \(z = a\), we find that \[xy + xz + yz = (2a)(4a) + (2a)(a) + (4a)(a) =
8a^{2} + 2a^{2} + 4a^{2} = 14a^{2}.\] Therefore, the surface area
of the prism is equal to \(2(14a^{2}) =
28a^{2} \text{ cm}^{2}\).
The surface area of the prism is also equal to \(9072\text{ cm}^{2}\) and so \(28 a^{2} = 9072\) or \(a^{2} = 324\).
Since \(a > 0\), \(a = 18\).
Solution 1
Let \(AB = x\).
Then the prism has width \(x\), height
\(z = AD = x\), and length \(y = CH = 2x\).
This means that \(xy = (x)(2x) =
2x^{2}\), \(xz = (x)(x) =
x^{2}\), and \(yz = (2x)(x) =
2x^{2}\).
Therefore, the surface area of the prism is given by \[2(xy + xz+ yz) = 2 (2x^{2} + x^{2} + 2x^{2}) =
2(5x^{2}) = 10x^{2}.\] Since \(GH\) is equal to the height of the prism,
we have \(GH = AD = x\).
Since face \(BGHC\) is a rectangle with
diagonal \(CG\), \(\triangle CHG\) is right-angled at \(H\).
By the Pythagorean theorem, \(CG^{2} = CH^{2}
+ GH^{2}\) or \(10^{2} = (2x)^2 +
x^{2}\) which simplifies to \(100 =
4x^{2} + x^{2} = 5x^{2}\).
Since \(5x^{2} = 100\), we have \(10x^{2} = 2(5x^{2}) = 2(100) = 200\).
Therefore, the surface area of the rectangular prism is \(200 \text{ cm}^{2}\).
Solution 2
Let \(AB = x\).
Then \(GH = BC = AD = AB = x\) and
\(CH = 2x\).
Since face \(BGHC\) is a rectangle with
diagonal \(CG\), \(\triangle CHG\) is right-angled at \(H\).
By the Pythagorean theorem, \(CG^{2} = CH^{2}
+ GH^{2}\) or \(10^{2} = (2x)^2 +
x^{2}\) which simplifies to \(100 =
4x^{2} + x^{2} = 5x^{2}\).
Therefore, \(x^{2} = 20\).
Since \(x > 0\), \(x = \sqrt{20}\).
This means that the width of the prism is \(x
=\sqrt{20}\), the length of the prism is \(y = 2x = 2\sqrt{20}\), and the height of
the prism is \(z = x =
\sqrt{20}\).
We calculate that \[\begin{align*}
xy & = \bigr(\sqrt{20}\bigr)\!\bigr(2 \sqrt{20}\bigr) =
2\bigr(\sqrt{20}\bigr)^{2} = 2(20) = 40\\
xz & = \bigr(\sqrt{20}\bigr)\!\bigr(\sqrt{20}\bigr) =
\bigr(\sqrt{20}\bigr)^{2} = 20 \\
yz & = \bigr(2\sqrt{20}\bigr)\!\bigr(\sqrt{20}\bigr) =
2\bigr(\sqrt{20}\bigr)^{2} = 2(20) = 40\end{align*}\] and so
\(2(xy+xz+yz) = 2(40 + 20 + 40) = 2(100) =
200\).
Therefore, the surface area of the rectangular prism is \(200 \text{ cm}^{2}\).
Note: These calculations can also be completed by first simplifying \(\sqrt{20}\) to \(2\sqrt{5}\).
There are \(5\) possible lists and they are \[1,2\quad 2,1\quad 2,2\quad 2,3,\quad 3,2\]
Each of the first two integers could be either \(1\) or \(2\), so there are \(2\times 2\) possibilities for the first two integers. Hence, there are \(4\) possibilities for the list.
Suppose the list ends with a \(3\). Then there cannot be another \(3\) in the list since Blaise would have stopped generating integers earlier if this were the case. There are \(2\times 2\times 2=8\) possibilities for the first three integers if the last integer is \(3\) but no others are \(3\). However, if this includes two \(2\)s in a row, then the list would have ended earlier. Thus, we need to exclude the following possibilities for the first three integers: \(2,2,1\) and \(1,2,2\) and \(2,2,2\). Therefore, there are \(8-3=5\) possibilities for the list, assuming it ended because a \(3\) was generated.
Otherwise, the list must end with two consecutive \(2\)s. Note that the second integer in the list cannot be \(3\) since this would have caused the list to end earlier, and it also cannot be \(2\) since this also would have caused the list to end earlier. Thus, the second integer in the list is \(1\). The first integer in the list can be either \(1\) or \(2\), so the possibilities for the list are \(2,1,2,2\) and \(1,1,2,2\), if the list ends because two consecutive \(2\)s were generated.
This gives a total of \(5+2=7\) lists.
If the list ends because a \(3\) was generated, then the first \(9\) integers are all either \(1\) or \(2\) with the property that there are not two consecutive \(2\)s among them. If the list ends because two consecutive \(2\)s were generated, then the eighth (third from last) integer in the list must be \(1\) (as argued in the solution to part (c)). The first \(7\) integers are all either \(1\) or \(2\) and there are not two consecutive \(2\)s among them.
Thus, to solve this problem, we need to determine the number of lists of length \(7\) and \(9\) with the property that every integer is either \(1\) or \(2\), but a \(2\) cannot be next to another \(2\).
As argued above, the answer to the question is the sum of these two counts. We include two different approaches to finding these counts.
Approach 1: Direct count.
To count the number of lists of seven \(1\)s and \(2\)s with the property that there are not two consecutive \(2\)s, we observe that such a list has zero, one, two, three, or four \(2\)s in it. If there are at least five \(2\)s, then there must be at least two next to each other.
If there are zero \(2\)s, then every integer in the list is \(1\), so there is \(1\) list in this case.
If there is one \(2\), then there are \(7\) possible positions for the \(2\) and every other integer in the list is \(1\). There are \(7\) lists in this case.
Suppose that the list has two \(2\)s. If the leftmost \(2\) is in the first (leftmost) position, then there are \(5\) choices for the location of the other \(2\) (it cannot go in the second position). If the leftmost \(2\) is in the second position, then there are \(4\) choices for where the other \(2\) can go. Continuing in this way, we see that there are \(5+4+3+2+1=15\) ways to place the two \(2\)s so that they are not consecutive. There is only one way to complete the list in each case since every other integer is \(1\). Therefore, there are \(15\) lists in this case.
Suppose that the list has three \(2\)s and consider the leftmost and rightmost \(2\)s. Because there has to be a space between two \(2\)s, there must be at least three integers between them (one \(2\) and at least two \(1\)s). Thus, the possible placements for the leftmost and rightmost \(2\) are as follows:
For these \(6\) possibilities, there are \(1\), \(1\), \(1\), \(2\), \(2\), and \(3\) ways to place the third \(2\) between them, respectively. Thus, there are \(1+1+1+2+2+3=10\) ways to place the three \(2\)s so that no two are consecutive. Therefore, there are \(10\) lists in this case.
There is only one way to place four \(2\)s so that they are not consecutive. So there is \(1\) list in this case.
Therefore, the number of lists of \(1\)s and \(2\)s of length \(7\) without two consecutive \(2\)s is \(1+7+15+10+1=34\).
For lists of length \(9\), we can use very similar reasoning. This time, however, there can be up to five \(2\)s. Some of the reasoning will be suppressed here since it essentially repeats earlier reasoning.
If there are zero \(2\)s, then there is \(1\) list.
If there is one \(2\), then there are \(9\) lists.
If there are two \(2\)s, then there are \(7+6+5+4+3+2+1=28\) lists.
If there are three \(2\)s, then there are \(5\) ways to place the leftmost and rightmost \(2\)s three spaces apart. There is one way to place the remaining \(2\) in each case. This gives \(5\) lists. There are \(4\) ways to place the leftmost and rightmost \(2\) four spaces apart, and there are \(2\) lists in each case, for a total of \(4\times 2=8\) lists. Continuing in this way, there are \(3\times 3=9\) lists where the leftmost and rightmost \(2\) are \(5\) apart, there are \(2\times 4=8\) lists when they are \(6\) apart, and there are \(1\times 5=5\) lists when they are \(7\) apart. This gives a total of \(5+8+9+8+5=35\) lists in this case.
Suppose that there are four \(2\)s. Consider the list \(2,1,2,1,2,1,2\). There are seven integers in this list, and so we can build a list by inserting the remaining two \(1\)s anywhere in the list (to the left of the leftmost \(2\), between the first two \(2\)s, etc.). There are \(5\) possible gaps, so there are \(5\) ways to place both remaining \(1\)s in the same gap. There are \(10\) ways to choose two gaps out of the \(5\), so there are \(10\) ways to place them in different gaps. This gives a total of \(15\) lists in this case.
Finally, if there are five \(2\)s, then there is only one possible list.
The total number of lists of \(1\)s and \(2\)s of length \(9\) without two consecutive \(2\)s is \(1+9+28+35+15+1=89\).
As mentioned above, the answer to the question is \(34+89=123\).
Approach 2: Recursion.
For each \(n\) from \(1\) through \(9\), let \(a_n\) be the number of lists of \(1\)s and \(2\)s of length \(n\) that do not have two consecutive \(2\)s.
For example, with \(n=1\), there are two lists of \(1\)s and \(2\)s (the lists are "\(1\)" and "\(2\)"), and neither has two consecutive \(2\)s, so \(a_1=2\).
As another example, with \(n=2\), there are four lists of \(1\)s and \(2\)s of length \(2\) which are \(1,1\) and \(1,2\) and \(2,1\) and \(2,2\). The fourth list has two consecutive \(2\)s but the first three do not, so \(a_2=3\).
Now consider a list of length \(n\geq 3\) with the desired properties. This list must end with either \(1\) or \(2\). If it ends with \(1\), then the first \(n-1\) integers form a list of \(1\)s and \(2\)s that does not have two consecutive \(2\)s. (If the entire list does not have two consecutive \(2\)s, then a "sublist" also cannot.) Thus, there are \(a_{n-1}\) lists of length \(n\) that end with \(1\). If the list ends with \(2\), then the second last integer must be \(1\) since there cannot be two consecutive \(2\)s. The initial \(n-2\) integers can be any list of length \(n-2\) with the given properties, so there are \(a_{n-2}\) lists of length \(n\) that end with \(2\).
This exhausts all possibilities, so we conclude that \(a_n = a_{n-1}+a_{n-2}\) for all \(n\geq 3\). We can now easily compute \(a_3 = a_2+a_1=3+2=5\). This enables us to compute \(a_4 = a_3+a_2 = 5+3=8\). Continuing in this way, we get the following \[\begin{align*} a_1 &= 2 \\ a_2 &= 3 \\ a_3 &= 5 \\ a_4 &= 8 \\ a_5 &= 8+5 = 13 \\ a_6 &= 13+8 = 21 \\ a_7 &= 21+13 = 34 \\ a_8 &= 34+21 = 55 \\ a_9 &= 55+34 = 89\end{align*}\] So the answer to the question is \(a_{7}+a_{9} = 123\).
The multiples of \(8\) between \(200\) and \(300\) are \[208, 216, 224, 232, 240, 248, 256, 264, 272, 280, 288, 296\] Of these, \(224\), \(248\), \(264\), and \(288\) have no digits equal to \(0\) and no odd digits. Because \(200=8\times 25\) is a multiple of \(8\), the integers that we want between \(400\) and \(500\) are exactly these four integers with \(200\) added to them (or, with the hundreds digit changed to \(4\)). Similarly, we get multiples of \(8\) by changing the hundreds digit to \(6\) or to \(8\), for a final list of \[224, 248, 264, 288, 424, 448, 464, 488, 624, 648, 664, 688, 824, 848, 864, 888\]
Suppose that the integer formed by the new \(m\) digits is \(x\) and that the new integer is \(y\). Then \(y\) is equal to \(n\) plus the integer formed by appending \(13\) zeros to the right of \(x\). In symbols, \(y = 10^{13}x+n\).
It is given that \(n\) is a multiple of \(17^2=289\), and we want \(y\) to also be a multiple of \(289\). Since \(y-n = 10^{13}x\), and the difference of two multiples of \(289\) must be a multiple of \(289\), it follows that we need \(10^{13}x\) to be a multiple of \(289\). Since the only prime factors of \(10^{13}\) are \(2\) and \(5\), we actually need \(x\) itself to be a multiple of \(289\).
We also need \(x\) to have only odd digits, so we are really looking for the number of digits in the smallest positive integer that is a multiple of \(289\) and has only odd digits.
If \(k\) is an even positive integer, then \(289k\) is also even, so its units digit is even. Hence, the multiple of \(289\) we are looking for is \(289\) times an odd positive integer. Checking the first few such integers, we get \[\begin{align*} 289\times1 &= 289 \\ 289\times 3 &= 867 \\ 289\times 5 &= 1445 \\ 289\times 7 &= 2023 \\ 289\times 9 &= 2601 \\ 289\times 11 &= 3179\end{align*}\] and so we find that the first multiple of \(289\) with all odd digits is \(289\times 11 = 3179\). Therefore, the smallest number of digits that Melaku could have placed is \(m=4\), and one way to do it would be to place the digits \(3\), \(1\), \(7\), \(9\) in that order from left to right.
Consider the following factorizations of integers \[\begin{align*} 5 &= 5^1 \\ 75 &= 5^2\times 3 \\ 375 &= 5^3 \times 3 \\ 9375 &= 5^4\times 15 \\ 59\,375 &= 5^5\times 19\end{align*}\] This shows that for \(n=1\), \(n=2\), \(n=3\), \(n=4\), and \(n=5\), there is an \(n\)-digit integer with only odd digits that is divisible by \(5^n\). We want to show that this is true for \(n=2025\). Another thing to notice from the list above is that the integers on the left side of the equations all have the same units digit. Also, those with a tens digit all have the same tens digit, those with a hundreds digit all have the same hundreds digit, and so on.
This suggests that the "next" integer can be found by introducing a new odd digit to the left of the previous digit. For example, to find a \(6\)-digit integer with only odd digits that is divisible by \(5^6\), we guess that it can be found by including a new odd digit to the left of \(59\,375\). If you divide each of the five integers \[159\,375, \quad 359\,375, \quad 559\,375, \quad 759\,375, \quad 959\,375\] by \(5^6=15625\), you will get an answer that is not an integer, except for \(\dfrac{359\,375}{15625}=23\). Therefore, \(359\,375=5^6\times23\), and so there is indeed a \(6\)-digit integer with all odd digits that is divisible by \(5^6\). Moreover, it is obtained by taking the integer for \(n=5\) and including one new odd digit to the left.
To prove the result, we will prove that this process can be done in general. Specifically, we will show the following:
Suppose \(n\) is a positive integer and \(x=d_nd_{n-1}\dots d_3d_2d_1\) is an \(n\)-digit integer with digits \(d_1\), \(d_2\), and so on, to \(d_n\), all of which are odd. If \(x\) is a multiple of \(5^n\), then there is an odd digit \(d\) so that the integer \(y=dd_nd_{n-1}\dots d_3d_2d_1\) (with \(n+1\) digits) is a multiple of \(5^{n+1}\).
With notation as in the statement above, we get that \(y = d\times 10^n + x\). The only possibilities for \(d\) are \(d=1\), \(d=3\), \(d=5\), \(d=7\), or \(d=9\). Assuming that \(x\) is a multiple of \(5^n\), we want to show that \(d\times 10^n +x\) is a multiple of \(5^{n+1}\) for one of these values of \(d\).
Suppose \(z\) is the integer such that \(x=5^n\times z\). Then we have \[\begin{align*} y &= d\times 10^n + x \\ &= d\times 2^n5^n + 5^nz \\ &= 5^n(d\times 2^n + z)\end{align*}\] and so \(y\) already has a factor of \(5^n\). This means that to show it has a factor of \(5^{n+1}\), we need to show that \(d\) can be chosen so that \(d\times 2^n + z\) has a factor of \(5\). Note that \(x\) has all odd digits, so \(x\) is odd, which implies that \(z\) is odd.
We will examine the possibilities for the units digit of \(d\times 2^n\). The units digit of \(2^n\) is one of \(2\), \(4\), \(6\), or \(8\), and \(d\) is one of \(1\), \(3\), \(5\), \(7\), or \(9\). In the table below, the columns correspond to the possible values of the units digit of \(2^n\) and the rows correspond to the values of \(d\). The cells are the corresponding units digit of \(d\times 2^n\). For example, if \(d=3\) and \(2^n\) has a units digit of \(8\), then \(d\times 2^n\) has the same units digit as \(3\times 8=24\), so there is a \(4\) in the cell corresponding to \(d=3\) and \(2^n\) having a units digit of \(8\).
| \(\boldsymbol{2}\) | \(\boldsymbol{4}\) | \(\boldsymbol{6}\) | \(\boldsymbol{8}\) | |
|---|---|---|---|---|
| \(\boldsymbol{1}\) | \(2\) | \(4\) | \(6\) | \(8\) |
| \(\boldsymbol{3}\) | \(6\) | \(2\) | \(8\) | \(4\) |
| \(\boldsymbol{5}\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(\boldsymbol{7}\) | \(4\) | \(8\) | \(2\) | \(6\) |
| \(\boldsymbol{9}\) | \(8\) | \(6\) | \(4\) | \(2\) |
Notice that in each column in this table, each of the five even digits occurs exactly once. This means that regardless of the integer \(n\), we can choose \(d\) so that \(d\times 2^n\) has any desired even units digit. We can now do the following:
If the units digit of \(z\) is \(1\), then choose \(d\) so that the units digit of \(d\times 2^n\) is \(4\).
If the units digit of \(z\) is \(3\), then choose \(d\) so that the units digit of \(d\times 2^n\) is \(2\).
If the units digit of \(z\) is \(5\), then choose \(d\) so that the units digit of \(d\times 2^n\) is \(0\).
If the units digit of \(z\) is \(7\), then choose \(d\) so that the units digit of \(d\times 2^n\) is \(8\).
If the units digit of \(z\) is \(9\), then choose \(d\) so that the units digit of \(d\times 2^n\) is \(6\).
This will result in the integer \(d\times 2^n + z\) having a units digit of \(5\) in all cases. Therefore, regardless of the value of \(z\) and \(n\), there is a way to choose \(d\) so that \(d\times 2^n+z\) has a units digit of \(5\). This will ensure \(d\times 2^n+z\) is a multiple of \(5\), which will in turn ensure that \(y = 5^n(d\times 2^n+z)\) is a multiple of \(5^{n+1}\). The new digit, \(d\), is odd and all of the digits of \(x\) are odd, so \(y\) also has only odd digits.
We have now shown that if there is an \(n\)-digit integer with all odd digits that is a multiple of \(5^n\), then there must be an \((n+1)\)-digit integer with all odd digits that is a multiple of \(5^{n+1}\). In the beginning of the solution, we showed that this is true for \(n=1\), \(n=2\), and so on, up to \(n=6\). This inductive reasoning means that there must be a \(7\)-digit integer with all odd digits that is divisible by \(5^7\), and there must be an \(8\)-digit integer with all odd digits that is divisible by \(5^8\), and so on. Continuing to build the desired integers one digit at a time, we must eventually reach a \(2025\)-digit integer with all odd digits that is divisible by \(5^{2025}\).