2015 Canadian Intermediate
Mathematics Contest
Solutions

Wednesday, November 25, 2015
(in North America and South America)

Thursday, November 26, 2015
(outside of North American and South America)

©2015 University of Waterloo

PART A

1. If \(\dfrac{8}{24} = \dfrac{4}{x+3}\), then \(8(x+3) = 24(4)\) or \(8x + 24 = 96\). Thus, \(8x = 72\) and so \(x = 9\).
   Alternatively, we could note that \(\dfrac{8}{24}= \dfrac{4}{12}\) and so we have \(\dfrac{8}{24}=\dfrac{4}{12} = \dfrac{4}{x+3}\) which gives \(x+3 = 12\) or \(x=9\)

   Answer: \(9\)

2. We start by considering the ones (units) column of the given sum.
   From the units column, we see that the units digits of \(3C\) must equal 6.
   The only digit for which this is possible is \(C=2\). (We can check that no other digit works.)
   Thus, the sum becomes \[\begin{array}{cccc} &&\!\!B\!\!&\!2\!\\ &\!\!A\!\!&\!\!B\!\!&\!2\!\\ +&\!A\!\!&\!\!B\!\!&\!2\!\\ \hline &\!8\!\!&\!\!7\!\!&\!6\! \end{array}\] We note that there is no “carry” from the ones column to the tens column.
   Next, we consider the tens column.
   From the tens column, we see that the units digit of \(3B\) must equal 7.
   The only digit for which this is possible is \(B=9\).
   Thus, the sum becomes \[\begin{array}{cccc} &&\!9\!&\!\!2\!\!\\ &\!\!A\!\!&\!9\!&\!\!2\!\!\\ +&\!A\!\!&\!9\!&\!\!2\!\!\\ \hline &\!8\!\!&\!7\!&\!\!6\!\! \end{array}\] The “carry” from the tens column to the hundreds column is 2.
   Next, we consider the hundreds column.
   We see that the units digit of \(2A+2\) (the two digits plus the carry) must equal 8.
   Thus, the units digit of \(2A\) must equal 6. This means that \(A=3\) or \(A=8\).
   The value of \(A=8\) is too large as this makes \(A92=892\) which is larger than the sum.
   Therefore, \(A=3\).
   (Putting this analysis another way, we have \(92 + (100A+92) + (100A+92) = 876\). Simplifying, we obtain \(200A + 276 = 876\) or \(200A = 600\) and so \(A=3\).)
   We can check that \(92+392+392 = 876\).) Therefore, \(A+B+C=3+9+2=14\).

   Answer: \(14\)

3. Since the roof measures 5 m by 5 m, then its area is \(5^2 = 25\mbox{ m}^2\).
   When this roof receives 6 mm (or 0.006 m) of rain, the total volume of rain that the roof receives is \(25 \cdot 0.006 = 0.15\mbox{ m}^3\). (We can imagine that the rain that falls forms a rectangular prism with base that is 5 m by 5 m and height 6 mm.)
   The rain barrel has diameter 0.5 m (and so radius 0.25 m) and a height of 1 m, and so has volume \(\pi\cdot 0.25^2 \cdot 1 = 0.0625 \pi \mbox{ m}^3\).
   Thus, the percentage of the barrel that is full is \[\dfrac{0.15}{0.0625\pi} \times 100\% \approx 76.39 \%\] To the nearest tenth of a percent, the rain barrel will be \(76.4\%\) full of water.

   Answer: \(76.4\%\)

4. Using exponent laws, we obtain the following equivalent equations: \[\begin{aligned} \left(2 \cdot 4^{x^2-3x}\right)^2 & = 2^{x-1} \\ 2^2 \cdot 4^{2(x^2-3x)} & = 2^{x-1} \\ 2^2 \cdot 4^{2x^2-6x} & = 2^{x-1} \\ 2^2 \cdot (2^2)^{2x^2-6x} & = 2^{x-1} \\ 2^2 \cdot 2^{2(2x^2 - 6x)} & = 2^{x-1}\\ \dfrac{2^2 \cdot 2^{4x^2-12x}}{2^{x-1}} & = 1 \\ 2^{2+4x^2-12x - (x-1)} & = 1\\ 2^{4x^2-13x + 3} & = 1\end{aligned}\] Since \(2^0=1\), this last equation is true exactly when \(4x^2-13x+3 = 0\) or \((4x-1)(x-3) = 0\).
   Therefore, \(x = \frac{1}{4}\) or \(x=3\).
   We can check by substitution that each of these values of \(x\) satisfies the original equation.

   Answer: \(\frac{1}{4},3\)

5. Suppose that Anna guesses “cat” \(c\) times and guesses “dog” \(d\) times.
   When she guesses “dog”, she is correct \(95\%\) of the time.
   When she guesses “cat”, she is correct \(90\%\) of the time.
   Thus, when she guesses “cat”, she is shown \(0.9c\) images of cats and so \(c-0.9c = 0.1c\) images of dogs.
   Thus, when she guesses “dog”, she is shown \(0.95d\) images of dogs and so \(d - 0.95d = 0.05d\) images of cats.
   (We assume that \(c\) and \(d\) have the property that \(0.9c\) and \(0.95d\) are integers.)
   Therefore, the total number of images of cats that she is shown is \(0.9c + 0.05d\) and the total number of images of dogs that she is shown is \(0.1c + 0.95d\).
   But the number of images of cats equals the number of images of dogs.
   Thus, \(0.9c + 0.05d = 0.1c + 0.95d\), which gives \(0.8c = 0.9d\) or \(\dfrac{d}{c} = \dfrac{0.8}{0.9}\).
   Therefore, the ratio of the number of times that she guessed “dog” to the the number of times that she guessed “cat” is \(8:9\).

   Answer: \(8:9\)

6. Since \(X+Y = 45^\circ\), then \(\tan(X+Y) = \tan 45^\circ = 1\).

   Now, \[\begin{aligned} \tan(X+Y) & = \dfrac{\tan X + \tan Y}{1 - \tan X \tan Y} \\ & = \dfrac{\dfrac{1}{m} + \dfrac{a}{n}}{1 - \dfrac{1}{m}\cdot \dfrac{a}{n}} \\ & = \dfrac{mn\left(\dfrac{1}{m} + \dfrac{a}{n}\right)}{mn\left(1 - \dfrac{1}{m}\cdot \dfrac{a}{n}\right)} \\ & = \dfrac{n + am}{mn - a} \end{aligned}\]
   Thus, we have \(\dfrac{n+am}{mn-a} = 1\).
   We want to determine the number of positive integers \(a\) for which this equation has exactly 6 pairs of positive integers \((m,n)\) that are solutions.
   Re-arranging the equation, we obtain \[\begin{aligned} \dfrac{n+am}{mn-a} &= 1\\ n+am & = mn - a \\ a & = mn - am - n\\ a + a & = mn - am - n + a \\ 2a & = m(n-a) - (n-a) \\ 2a & = (m-1)(n-a)\end{aligned}\] So we want to determine the number of positive integers \(a\) for which \((m-1)(n-a) = 2a\) has exactly 6 pairs of positive integers \((m,n)\) that are solutions.
   Since \(a \neq 0\), then \(m-1 \neq 0\) and so \(m \neq 1\).
   Since \(m\) is a positive integer and \(m \neq 1\), then \(m \geq 2\); in other words, \(m-1 > 0\).
   Since \(m-1>0\) and \(2a > 0\) and \(2a = (m-1)(n-a)\), then \(n-a > 0\) or \(n>a\).
   Now, the factorizations of \(2a\) as a product of two positive integers correspond with the pairs \((m,n)\) of positive integers that are solutions to \((m-1)(n-a) = 2a\).
   This is because a factorization \(2a = r \cdot s\) gives a solution \(m-1 = r\) (or \(m=r+1\)) and \(n-a = s\) (or \(n = s+a\)) and vice-versa.
   So the problem is equivalent to determining the number of positive integers \(a\) with \(a \leq 50\) for which \(2a\) has three factorizations as a product of two positive integers, or equivalently for which \(2a\) has six positive divisors.
   Given an integer \(d\) and its prime factorization \(d = p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k}\), where \(p_1,p_2,\ldots,p_k\) are distinct prime numbers and \(c_1,c_2,\ldots,c_k\) are positive integers, the number of positive divisors of \(d\) is \((c_1+1)(c_2+1)\cdots(c_k+1)\).
   In order for this product to equal 6, \(d\) must have the form \(p^5\) for some prime number \(p\) or \(p^2 q\) for some prime numbers \(p\) and \(q\). This is because the only way for 6 to be written as the product of two integers each larger than one is \(2 \cdot 3\).
   In other words, we want \(2a\) to be the fifth power of a prime, or the square of a prime times another prime.
   If \(2a\) is of the form \(p^5\), then \(p=2\) since \(2a\) is already divisible by 2. Thus, \(2a=2^5 = 32\) and so \(a=16\).
   If \(2a\) is of the form \(p^2 q\), then \(p=2\) or \(q=2\) since \(2a\) is already divisible by 2.
   If \(p=2\), then \(2a = 4q\). Since \(a \leq 50\), then \(2a \leq 100\) or \(q \leq 25\), and so \(q\) can equal \(3, 5, 7, 11,13,17,19,23\), giving \(a = 6, 10, 14, 22, 26, 34, 38, 46\). (Note that \(q \neq 2\).)
   If \(q = 2\), then \(2a = 2p^2\). Since \(2a \leq 100\), then \(p^2 \leq 50\) and so the prime \(p\) can equal \(3, 5, 7\) giving \(a = 9, 25, 49\). (Note that \(p \neq 2\).)
   Therefore, in summary, there are 12 such values of \(a\).

   Answer: \(12\)

PART B

1. 1. The \(y\)-intercept of the line with equation \(y = 2x + 4\) is 4.
      Since \(R\) is the point where this line crosses the \(y\)-axis, then \(R\) has coordinates \((0,4)\).
      Since \(O\) has coordinates \((0,0)\), the length of \(OR\) is 4.

   2. The point \(Q\) is the point of intersection of the line with equation \(y=2x+4\) and the vertical line with equation \(x=p\).
      Thus, the \(x\)-coordinate of \(Q\) is \(p\), and its \(y\)-coordinate is thus \(2p+4\).
      So the coordinates of \(Q\) are \((p,2p+4)\).

   3. When \(p=8\), the coordinates of \(P\) are \((8,0)\) and the coordinates of \(Q\) are \((8,20)\).
      Quadrilateral \(OPQR\) is a trapezoid with parallel sides \(OR\) and \(PQ\), and height equal to the length of \(OP\), since \(OP\) is perpendicular to \(OR\) and \(PQ\).
      Therefore, the area of \(OPQR\) is \(\frac{1}{2}(OR + PQ)\cdot OP = \frac{1}{2}(4+20)\cdot 8 = 96\).

   4. In general, quadrilateral \(OPQR\) is a trapezoid with parallel sides \(OR\) and \(PQ\), and height equal to the length of \(OP\), since \(OP\) is perpendicular to \(OR\) and \(PQ\).
      In terms of \(p\), the area of \(OPQR\) is \[\begin{aligned}\tfrac{1}{2}(OR + PQ)\cdot OP & = \tfrac{1}{2}(4 + (2p+4))\cdot p & \\ = \tfrac{1}{2}(2p+8)p & \\ = p(p+4)\end{aligned}\] If the area of \(OPQR\) is 77, then \(p(p+4) = 77\) and so \(p^2 + 4p - 77 = 0\) or \((p+11)(p-7) = 0\).
      Since \(p>0\), then \(p = 7\).
      We can verify that if \(p= 7\), then the area of \(OPQR\) is indeed 77.
      

2. 1. If \(f(r) = r\), then \(\dfrac{r}{r-1} = r\).
      Since \(r \neq 1\), then \(r = r(r-1)\) or \(r = r^2 - r\) or \(0 = r^2 - 2r\) and so \(0 = r(r-2)\).
      Thus, \(r = 0\) or \(r=2\).
      We can check by substitution that each of these values of \(r\) satisfies the original equation.

   2. Since \(f(x) = \dfrac{x}{x-1}\), then \[f(f(x)) = \dfrac{\dfrac{x}{x-1}}{\dfrac{x}{x-1}-1} = \dfrac{x}{x - (x-1)} = \dfrac{x}{1} = x\] as required.
      (Note that above we have multiplied both the numerator and denominator of the complicated fraction by \(x-1\), which we can do since \(x \neq 1\).)

   3. When \(x \neq -k\), \(g(x) = \dfrac{2x}{x+k}\) is well-defined.
      When \(x \neq -k\) and \(g(x) \neq -k\), \(g(g(x)) = \dfrac{ 2\left(\dfrac{2x}{x+k}\right)}{\dfrac{2x}{x+k}+k}\) is well-defined.
      The following equations are equivalent for all \(x\) with \(x \neq -k\) and \(g(x) \neq -k\): \[\begin{aligned} g(g(x)) & = x \\ \dfrac{2\left(\dfrac{2x}{x+k}\right)}{\dfrac{2x}{x+k}+k} & = x \\ \dfrac{4x}{2x+k(x+k)} & = x \qquad \mbox{(multiplying numerator and denominator by $x+k$)}\\ 4x & = x(2x+k(x+k)) \\ 4x & = x(2x+kx + k^2) \\ 4x & = (k+2)x^2 + k^2x \\ 0 & = (k+2)x^2 + (k^2 - 4)x \\ 0 & = (k+2)(x^2 + (k-2)x)\end{aligned}\] Since there are values of \(x\) for which \(x^2 + (k-2)x \neq 0\), then to have \((k+2)(x^2 + (k-2)x) = 0\) for all \(x\), we need to have \(k+2 = 0\), or \(k=-2\). (For example, if \(k=1\), the equation would become \(3(x^2-x)=0\) which only has the two solutions \(x=0\) and \(x=1\).)
      Therefore, \(g(g(x)) = x\) for all \(x\) with \(x \neq -k\) and \(g(x) \neq -k\) exactly when \(k =-2\).

   4. When \(x \neq -\dfrac{c}{b}\), \(h(x) = \dfrac{ax+b}{bx+c}\) is well-defined.
      When \(x \neq -\dfrac{c}{b}\) and \(h(x) = \dfrac{ax+b}{bx+c} \neq -\dfrac{c}{b}\), \(h(h(x)) = \dfrac{a\left(\dfrac{ax+b}{bx+c}\right)+b}{b\left(\dfrac{ax+b}{bx+c}\right)+c}\) is well-defined.
      The following equations are equivalent for all \(x\) with \(x \neq -\dfrac{c}{b}\) and \(h(x) \neq -\dfrac{c}{b}\): \[\begin{aligned} h(h(x)) & = x \\ \dfrac{a\left(\dfrac{ax+b}{bx+c}\right)+b}{b\left(\dfrac{ax+b}{bx+c}\right)+c} & = x \\ \dfrac{a(ax+b)+b(bx+c)}{b(ax+b)+c(bx+c)} & = x \qquad\mbox{(multiplying numerator and denominator by $bx+c$)}\\ a(ax+b) + b(bx+c) & = x(b(ax+b)+c(bx+c)) \\ (a^2+b^2)x + (ab+bc) & = (ab+bc)x^2 + (b^2+c^2)x \\ 0 & = b(a+c)x^2 + (c^2-a^2)x - b(a+c)\end{aligned}\] Since this “quadratic equation” is satisfied for infinitely many real numbers \(x\), then it must be the case that all three of its coefficients are 0.
      In other words, we must have \(b(a+c)=0\) and \(c^2-a^2 = 0\), and \(b(a+c)=0\).
      Since \(b \neq 0\), then \(b(a+c)=0\) gives \(a+c=0\) or \(c=-a\).
      Note that if \(c=-a\), then \(c^2 - a^2 = 0\) and \(b(a+c)=0\) as well.
      Therefore, \(h(h(x)) = x\) for all triples \((a,b,c)\) of the form \((a,b,-a)\) where \(a\) and \(b\) are non-zero real numbers.
      

3. 1. When \(a_n=n^2\), we obtain

      \(n\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(\cdots\)
      \(a_{n}\)	\(1\)	\(4\)	\(9\)	\(16\)	\(25\)	\(36\)	\(49\)	\(64\)	\(81\)	\(100\)	\(\cdots\)
      \(b_{n}\)	\(1\)										\(\cdots\)

      Since \(b_1 \leq a_2\), then \(b_2 = b_1 + a_2 = 1+4=5\).
      Since \(b_2 \leq a_3\), then \(b_3 = b_2 + a_3 = 5+9=14\).
      Since \(b_3 \leq a_4\), then \(b_4 = b_3 + a_4 = 14+16=30\).
      Since \(b_4 > a_5\), then \(b_5 = b_4 - a_5 = 30-25 = 5\).
      Since \(b_5 \leq a_6\), then \(b_6 = b_5 + a_6 = 5+36 = 41\).
      Since \(b_6 \leq a_7\), then \(b_7 = b_6 + a_7 = 41+49 = 90\).
      Since \(b_7 > a_8\), then \(b_8 = b_7 - a_8 = 90 - 64 = 26\).
      Since \(b_8 \leq a_9\), then \(b_9 = b_8 + a_9 = 26 + 81 = 107\).
      Since \(b_9 > a_{10}\), then \(b_{10} = b_9 - a_{10} = 107 - 100 = 7\).

      In tabular form, we have

      \(n\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(\cdots\)
      \(a_{n}\)	\(1\)	\(4\)	\(9\)	\(16\)	\(25\)	\(36\)	\(49\)	\(64\)	\(81\)	\(100\)	\(\cdots\)
      \(b_{n}\)	\(1\)	\(5\)	\(14\)	\(30\)	\(5\)	\(41\)	\(90\)	\(26\)	\(107\)	\(7\)	\(\cdots\)

   2. As in (a), we start by calculating the first several values of \(b_n\):

      \(n\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(11\)	\(12\)	\(13\)	\(14\)	\(15\)	\(16\)	\(17\)	\(18\)	\(19\)	\(20\)	\(21\)	\(22\)	\(\cdots\)
      \(a_{n}\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(11\)	\(12\)	\(13\)	\(14\)	\(15\)	\(16\)	\(17\)	\(18\)	\(19\)	\(20\)	\(21\)	\(22\)	\(\cdots\)
      \(b_{n}\)	\(1\)	\(3\)	\(6\)	\(2\)	\(7\)	\(1\)	\(8\)	\(16\)	\(7\)	\(17\)	\(6\)	\(18\)	\(5\)	\(19\)	\(4\)	\(20\)	\(3\)	\(21\)	\(2\)	\(22\)	\(1\)	\(23\)	\(\cdots\)

      We will show that if \(k\) is a positive integer with \(b_k=1\), then \(b_{3k+3}=1\) and \(b_n \neq 1\) for each \(n\) with \(k < n< 3k+3\).
      We note that this is consistent with the table shown above.
      Using this fact without proof, we see that \(b_1=1\), \(b_6=1\), \(b_{21}=1\), \(b_{66}=1\), \(b_{201}=1\), \(b_{606}=1\), \(b_{1821}=1\), \(b_{5466}=1\), and no other \(b_n\) with \(n < 5466\) is equal to 1.
      (This list of values of \(b_n\) comes from the fact that \(6=3(1)+3\), \(21=3(6)+3\), \(66=3(21)+3\), and so on.)
      Thus, once we have proven this fact, the positive integers \(n\) with \(n<2015\) and \(b_n=1\) are \(n=1,6,21,66,201,606,1821\).
      Suppose that \(b_k=1\).
      Since \(a_{k+1} = k+1 > 1=b_k\), then \(b_{k+1}=b_k+a_{k+1}=k+2\).
      Since \(a_{k+2}=k+2=b_{k+1}\), then \(b_{k+2}=b_{k+1}+a_{k+2}=2k+4\).
      Continuing in this way, we find that \(b_{k+2m-1}=k+3-m\) for \(m = 1, 2, \ldots, k+2\) and that \(b_{k+2m} = 2k+m+3\) for \(m = 1, 2, \ldots, k+1\).
      To justify these statements, we note that each is true when \(m=1\) and that

      • if \(b_{k+2m} = 2k+m+3\) for some \(m\) with \(1 \leq m \leq k+1\), then since \(a_{k+2m+1}=k+2m+1\) and \(b_{k+2m}-a_{k+2m+1} = k-m+2 > 0\) when \(m \leq k+1\), then \[b_{k+2m+1} = b_{k+2m}-a_{k+2m+1} = k-m+2\] which can be re-written as \(b_{k+2(m+1)-1} = k+3-(m+1)\) and so is of the desired form; and

      • if \(b_{k+2m-1} = k+3-m\) for some with \(1 \leq m \leq k+1\), then since \(a_{k+2m} = k+2m\) and \(b_{k+2m-1}-a_{k+2m} = 3-3m \leq 0\) when \(m \geq 1\), then \[b_{k+2m} = b_{k+2m-1}+a_{k+2m} = (k+3-m)+(k+2m) = 2k + m + 3\] and so is of the desired form.

      This tells us that, for these values of \(m\), the terms in the sequence \(b_n\) have the desired form.
      Now \(b_{k+2m} = 2k+m+3 \neq 1\) for \(m = 1, 2, \ldots, k+1\) and \(b_{k+2m-1}=k+3-m = 1\) only when \(m=k+2\).
      Since \(k+2(k+2)-1=3k+3\), then \(b_{3k+3}=1\) and no other \(n\) with \(k < n< 3k+3\) gives \(b_n=1\).
      Thus, the positive integers \(n\) with \(n<2015\) and \(b_n=1\) are \(n=1,6,21,66,201,606,1821\).

   3. Suppose that \(a_1,a_2,a_3,\ldots\) is eventually periodic.
      Then there exist positive integers \(r\) and \(p\) such that \(a_{n+p} = a_n\) for all \(n \geq r\).
      Note that this means that the terms from \(a_r\) to \(a_{r+p-1}\) repeat to give the terms from \(a_{r+p}\) to \(a_{r+2p-1}\), which repeat to give the terms from \(a_{r+2p}\) to \(a_{r+3p-1}\), and so on.
      In other words, the sequence \(a_1,a_2,a_3,\ldots\) begins with \(r-1\) terms that do not necessarily repeat, and then continues with \(p\) terms (\(a_r\) to \(a_{r+p-1}\)) which repeat indefinitely.
      Let \(M\) be the maximum value of the terms \(a_1,a_2,\ldots,a_{r-1},a_r,a_{r+1},\ldots,a_{r+p-1}\).
      Since the terms in the sequence \(a_1,a_2,a_3,\ldots\) are all positive integers, then \(M \geq 1\).
      From the above comment, \(M\) is thus the maximum value of all of the terms in the sequence \(a_1,a_2,a_3,\ldots\).
      In other words, \(a_n \leq M\) for all positive integers \(n\).
      Next we prove that \(b_n \leq 2M\) for all positive integers \(n\).
      To do this, we first note that \(b_1 = a_1 \leq M < 2M\).
      Next, we consider a given term \(b_k\) in the sequence and assume that it satisfies \(b_k \leq 2M\).
      Note that \(b_{k+1}\) equals either \(b_k + a_{k+1}\) or \(b_k - a_{k+1}\).
      If \(b_k \leq M\), then \(b_{k+1}\) is at most \(b_k + a_{k+1}\).
      Since \(b_k \leq M\) and \(a_{k+1} \leq M\), then \(b_{k+1} \leq M+M =2M\).
      If \(M < b_k \leq 2M\), then since \(a_{k+1} \leq M\), we obtain \(b_{k+1} = b_k - a_{k+1} < b_k \leq 2M\).
      In either case, if \(b_k \leq 2M\), then \(b_{k+1} \leq 2M\).
      Therefore, \(b_n \leq 2M\) for all positive integers \(n\).
      Now we consider the \(2M\) pairs of terms \((a_r,b_r), (a_{r+p},b_{r+p}),\ldots,(a_{r+2Mp},b_{r+2Mp})\).
      Since \(a_r = a_{r+p} = a_{r+2p} = a_{r+3p} = \cdots\), then the first term in each of these pairs are equal.
      Since \(b_n\) is a positive integer for each positive integer \(n\) and since \(b_m \leq 2M\), then, by the Pigeonhole Principle, at least two of the terms \(b_r,b_{r+p},b_{r+2p},\ldots,b_{r+2Mp}\) must be equal.
      (We have a list of \(2M+1\) numbers each of which has at most \(2M\) possible values, so two of the numbers must be the same.)
      Suppose that \(b_{r+sp} = b_{r+tp}\) for some non-negative integers \(s<t\).
      Now each term \(b_{k+1}\) is completely determined by the numbers \(b_k\) and \(a_{k+1}\). (If \(b_{k_1} = b_{k_2}\) and \(a_{k_1+1} = a_{k_2+1}\), then \(b_{k_1+1} = b_{k_2+1}\).)
      Since \(a_{r+sp+1}=a_{r+tp+1}\) and \(a_{r+sp+2} = a_{r+tp+2}\) and \(a_{r+sp+3} = a_{r+tp+3}\) and so on, then \(b_{r+sp+1}=b_{r+tp+1}\) and \(b_{r+sp+2} = b_{r+tp+2}\) and so on. (Since the terms in the two sequences are equal at the same two points, then all subsequent terms will be equal.)
      In particular, if \(b_{r+sp} = b_{r+tp} > a_{r+sp+1}=a_{r+tp+1}\), then \[b_{r+sp+1} = b_{r+sp} - a_{r+sp+1} = b_{r+tp} - a_{r+tp+1} = b_{r+tp+1}\] and if \(b_{r+sp} = b_{r+tp} \leq a_{r+sp+1}=a_{r+tp+1}\), then \[b_{r+sp+1} = b_{r+sp} + a_{r+sp+1} = b_{r+tp} + a_{r+tp+1} = b_{r+tp+1}\] This argument then repeats at each step going forward.
      In other words, starting at each of \(b_{r+sp}\) and \(b_{r+tp}\), the terms going forward will be equal, which means that the sequence \(b_1,b_2,b_3,\ldots\) is eventually periodic. (We note that if \(R = r+sp\) and \(P = (t-s)p\), then \(b_N = b_{N+P}\) for each positive integer \(N \geq R\).)