CEMC Banner

Problem of the Month 2023-2024

Problem 0: September 2023

Problem

In this problem, \(f\) will always be a function defined by \(f(r) = \dfrac{ar+b}{cr+d}\) where \(a\), \(b\), \(c\), and \(d\) are integers. These integers will vary throughout the parts of the problem.

Given such a function \(f\) and a rational number \(r_1\), we can generate a sequence \(r_1,r_2,r_3,\dots\) by taking \(r_n=f(r_{n-1})\) for each \(n\geq 2\). That is, \(r_2=f(r_1)\), \(r_3=f(r_2)\), \(r_4=f(r_3)\), and so on. Unless there is some point in the sequence where \(f(r_{n-1})\) is undefined, a sequence of this form can be made arbitrarily long.

These sequences behave in different ways depending on the function \(f\) and the starting value \(r_1\). This problem explores some those behaviours.

  1. Suppose \(f(r) = \dfrac{2r-1}{r+2}\).

    1. With \(r_1=\frac{3}{2}\), compute \(r_2\), \(r_3\), and \(r_4\).

    2. Find a rational number \(r_1\) with the property that \(r_2\) is defined, but \(r_3\) is not defined.

  2. Suppose \(f(r) = \dfrac{r+3}{2r-1}\).

    1. With \(r_1=\frac{3}{7}\), compute \(r_2\), \(r_3\), \(r_4\), and \(r_5\).

    2. Determine all rational values of \(r_1\) with the property that there is some integer \(n\geq 1\) for which \(f(r_n)\) is undefined. For all other values of \(r_1\), find simplified formulas for \(r_{2023}\) and \(r_{2024}\) in terms of \(r_1\).

  3. Suppose \(f(r) = \dfrac{r+2}{r+1}\).

    1. With \(r_1=1\), compute \(r_2\) through \(r_9\). Write down decimal approximations of \(r_2\) through \(r_9\) (after computing them exactly).

    2. Suppose \(r\) is a positive rational number. Prove that \[\left|\frac{f(r)-\sqrt{2}}{r-\sqrt{2}}\right| = \left|\dfrac{1-\sqrt{2}}{r+1}\right|\]

    3. Suppose \(r_1\) is a positive rational number. Prove that \(\left|r_n-\sqrt{2}\right| < \dfrac{1}{2^{n-1}}\left|r_1-\sqrt{2}\right|\) for each \(n\geq 2\). Use this result to convince yourself that as \(n\) gets large, \(r_n\) gets close to \(\sqrt{2}\), regardless of the choice of the positive value \(r_1\). Can you modify \(f\) slightly so that the sequence always approaches \(\sqrt{3}\)?

  4. Explore the behaviour of the sequences generated by various values of \(r_1\) for each of the functions below. Detailed solutions will not be provided, but a brief discussion will. \[f(r)=\dfrac{r-3}{r-2},\,\,\,\, f(r)=\dfrac{r-1}{5r+3},\,\,\,\, f(r) = \dfrac{r-1}{r+2},\,\,\,\, f(r) = \dfrac{2r+2}{3r+3},\,\,\,\, f(r)=\frac{r+1}{r-2}\]

Hint

  1. \(f(r)\) is undefined only when \(r=-2\). For what value of \(r\) is \(f(r)=-2\)?

  2. The sequence in part (i) is periodic. Can you show that the sequence is periodic for other values of \(r_1\)?

    1. No hint given.

    2. After substituting the expression for \(f(r)\), multiply the numerator and denominator by \(r+1\). Try to find a common factor in the numerator and denominator.

    3. Use (ii) and the fact that when \(r\) is positive, \(\left|\dfrac{1-\sqrt{2}}{r+1}\right| < \frac{1}{2}\). Try to establish the given inequality for a few small values of \(n\) and observe how knowing the inequality for \(n\) can help you to deduce it for \(n+1\).

  3. Three of these sequences are periodic, one of them is constant (after the first term), and one of them always approaches the fixed value \(\dfrac{3-\sqrt{13}}{2}\) as long as there are no undefined values in the sequence.

Solution


    1. \[\begin{align*} r_2 = f(r_1) &= \frac{2r_1-1}{r_1+2} \\ &= \frac{2\left(\frac{3}{2}\right) -1}{\frac{3}{2}+2} \\ &= \frac{4}{7}\end{align*}\] \[\begin{align*} r_3 = f(r_2) &= \frac{2\left(\frac{4}{7}\right)-1}{\frac{4}{7}+2} \\ &= \frac{1}{18}\end{align*}\] \[\begin{align*} r_4 = f(r_3) &= \frac{2\left(\frac{1}{18}\right)-1}{\frac{1}{18}+2} \\ &= -\frac{16}{37}\end{align*}\]

    2. Observe that \(f(r)\) is only undefined when \(r=-2\), so to choose \(r_1\) so that \(r_3=f(r_2)\) is undefined, we need \(r_2=-2\). Therefore, \(r_2=f(r_1)=-2\), which gives rise to the equation \(\dfrac{2r_1-1}{r_1+2}=-2\). Multiplying both sides by \(r_1+2\) gives \(2r_1-1 = -2(r_1+2)\), which can be rearranged to get \(4r_1=-3\), so \(r_1=-\frac{3}{4}\). Indeed, if \(r_1=-\frac{3}{4}\), then \(r_2=-2\) and \(r_3\) is undefined.

    1. \[\begin{align*} r_2=f(r_1) &=\dfrac{\frac{3}{7}+3}{2\left(\frac{3}{7}\right)-1} \\ &=-24.\end{align*}\] \[\begin{align*} r_3 = f(r_2) &= \frac{-24+3}{2(-24)-1} \\ &= \frac{-21}{-49} \\ &= \frac{3}{7} \\ &= r_1\end{align*}\] We have that \(r_3=r_1\), so this means \(r_4=f(r_3)=f(r_1)=r_2\), and using these facts, \(r_5=f(r_4)=f(r_2)=r_3=r_1\). This will continue to get that \(r_n=\frac{3}{7}\) when \(n\) is odd and \(r_n=-24\) when \(n\) is even.

    2. First observe that \(f(r)\) is undefined only when \(2r-1=0\), or \(r=\frac{1}{2}\). Therefore, if \(r_1=\frac{1}{2}\), then \(r_2=f(r_1)\) is undefined.

      Now suppose \(f(r)=\frac{1}{2}\). Then \(\dfrac{r+3}{2r-1}=\frac{1}{2}\), which can be rearranged to get the equation \(2r+6 = 2r-1\). This equation implies \(6=-1\), which is nonsense, and so we conclude that there is no \(r\) such that \(f(r)=\frac{1}{2}\).

      The only way that the sequence can fail to be defined somewhere is if \(r_n=\frac{1}{2}\) for some \(n\). This happens if \(r_1=\frac{1}{2}\), but since \(\frac{1}{2}\) is never the output of \(f\), it is not possible that \(r_n=\frac{1}{2}\) unless \(n=1\). Therefore, \(r_1=\frac{1}{2}\) is the only starting value for which the sequence is undefined somewhere.

      Assuming \(r\neq\frac{1}{2}\), we will now compute a general expression for \(f(f(r))\). Since \(r\neq\frac{1}{2}\) and \(f(r)\neq\frac{1}{2}\) regardless of \(r\), there will be no issues with the expression being undefined. \[\begin{align*} f(f(r)) &= \frac{\frac{r+3}{2r-1}+3}{2\left(\frac{r+3}{2r-1}\right)-1} \\ &= \frac{r+3 + 3(2r-1)}{2(r+3)-(2r-1)} & \text{(multiply through by $2r-1$)} \\ &= \frac{7r}{7} \\ &= r\end{align*}\] and so we have that \(f(f(r))=r\) for all \(r\neq\frac{1}{2}\). We can use this equation to get \(r_3=f(r_2)=f(f(r_1))=r_1\). Next, we can compute \(r_5=f(r_4)=f(f(r_3))=r_3=r_1\). Continuing, we see that \(r_n=r_1\) for all odd \(n\). Similarly, \(r_4=f(r_3)=f(f(r_2))=r_2\), and we can continue with this reasoning to get that \(r_n=f(r_1)=r_2=\dfrac{r_1+3}{2r_1-1}\) for all even \(n\).

      To answer the given question, since \(2023\) is odd, \(r_{2023}=r_1\) and since \(2024\) is even, \(r_{2024}=\dfrac{r_1+3}{2r_1-1}\).

    1. The values along with their decimal approximations are in the table below.

      Term Value Decimal Approximation
      \(r_1\) \(1\) \(1\)
      \(r_2\) \(\dfrac{3}{2}\) \(1.5\)
      \(r_3\) \(\dfrac{7}{5}\) \(1.4\)
      \(r_4\) \(\dfrac{17}{12}\) \(1.416667\)
      \(r_5\) \(\dfrac{41}{29}\) \(1.413793\)
      \(r_6\) \(\dfrac{99}{70}\) \(1.414286\)
      \(r_7\) \(\dfrac{239}{169}\) \(1.414201\)
      \(r_8\) \(\dfrac{577}{408}\) \(1.414216\)
      \(r_9\) \(\dfrac{1393}{985}\) \(1.414213\)
    2. We will work with the quantity \(\dfrac{f(r)-\sqrt{2}}{r-\sqrt{2}}\) and worry about the absolute value later. \[\begin{align*} \frac{f(r)-\sqrt{2}}{r-\sqrt{2}} &= \frac{\frac{r+2}{r+1}-\sqrt{2}}{r-\sqrt{2}} \\ &= \frac{r+2-\sqrt{2}(r+1)}{(r+1)(r-\sqrt{2})} & \text{(multiply through by $r+1$)}\\ &= \frac{r-\sqrt{2} + 2-\sqrt{2}r}{(r+1)(r-\sqrt{2})} \\ &= \frac{r-\sqrt{2} -\sqrt{2}(r-\sqrt{2})}{(r+1)(r-\sqrt{2})} \\ &= \frac{(r-\sqrt{2})(1-\sqrt{2})}{(r+1)(r-\sqrt{2})} \\ &= \frac{1-\sqrt{2}}{r+1} & \text{(cancel $r-\sqrt{2}$)}\end{align*}\] The result now follows by taking the absolute value of both sides.

    3. Observe that if \(r\) is positive, then \(f(r)=\dfrac{r+2}{r+1}\) is also positive since \(r+2\) and \(r+1\) are both positive. It follows that if \(r_1\) is positive, then \(r_n\) is positive for all \(n\). Since \(r_n>0\) for all \(n\), \(r_n+1>1\) for all \(n\), and taking reciprocals, we get \(\dfrac{1}{r_n+1}<1\) for all \(n\). Since \(r_n+1\) is positive, \(\left|\dfrac{1}{r_n+1}\right|=\dfrac{1}{r_n+1}\), so we actually get that \(\left|\dfrac{1}{r_n+1}\right|<1\) for all \(n\).

      We will now show that \(|1-\sqrt{2}|<\frac{1}{2}\) (you may already believe this to be true, but the proof presented does not assume that we have a known approximation of \(\sqrt{2}\)). To see this, observe that \(8<9\), and so \(\sqrt{8} < \sqrt{9}\) which is the same as \(2\sqrt{2} < 3\). Dividing both sides by \(2\), we get \(\sqrt{2} < \frac{3}{2}\). Subtracting \(\frac{1}{2}+\sqrt{2}\) from both sides gives \(-\frac{1}{2} < 1-\sqrt{2}\). Now observe that \(1<2\), so \(\sqrt{1}<\sqrt{2}\) or \(1<\sqrt{2}\). Therefore, \(1-\sqrt{2}<0\).

      We have shown that \(-\frac{1}{2} < 1-\sqrt{2} < 0\), which implies that \(|1-\sqrt{2}|<\frac{1}{2}\). Combining this with \(\left|\dfrac{1}{r_n+1}\right|<1\), we get \[\left|\frac{1-\sqrt{2}}{r_n+1}\right| = \left|\frac{1}{r_n+1}\right||1-\sqrt{2}| < 1\times\frac{1}{2}=\frac{1}{2}\] so \(\left|\dfrac{1-\sqrt{2}}{r_n+1}\right| < \frac{1}{2}\).

      Since \(r_n = f(r_{n-1})\) for all \(n\geq 2\), we can apply part (ii) to get \[\left|\frac{r_n-\sqrt{2}}{r_{n-1}-\sqrt{2}}\right| = \left|\frac{f(r_{n-1})-\sqrt{2}}{r_{n-1}-\sqrt{2}}\right|=\left|\frac{1-\sqrt{2}}{r_{n-1}+1}\right|<\frac{1}{2}\] where the final inequality comes from applying what we showed above.

      This implies that for all \(n\geq 2\) we have \[|r_n-\sqrt{2}|<\frac{1}{2}|r_{n-1}-\sqrt{2}|\tag{*}\]

      Now let’s return to the inequality in the question, which is \(|r_n-\sqrt{2}| < \dfrac{1}{2^{n-1}}|r_1-\sqrt{2}|\).

      When \(n=2\), this inequality is \(|r_2-\sqrt{2}| < \frac{1}{2}|r_1-\sqrt{2}|\), which is exactly \((*)\) when \(n=2\). We have already shown that \((*)\) is true for all \(n\), so this means the desired inequality is true for \(n=2\).

      When \(n=3\), we can apply \((*)\) to get \(|r_3-\sqrt{2}|<\frac{1}{2}|r_2-\sqrt{2}|\), but we have just shown that \(|r_2-\sqrt{2}|<\frac{1}{2}|r_1-\sqrt{2}|\). Therefore, \[|r_3-\sqrt{2}| < \frac{1}{2}|r_2-\sqrt{2}| < \frac{1}{2}\left(\frac{1}{2}|r_1-\sqrt{2}|\right) = \frac{1}{2^2}|r_1-\sqrt{2}|\] which shows that the desired inequality holds for \(n=3\).

      By similar reasoning, we can use the fact that the inequality holds for \(n=3\) to prove that it holds for \(n=4\), then we can use that it holds for \(n=4\) to prove that it holds for \(n=5\), and so on to show that the inequality holds for all positive integers \(n\geq 2\). We can formalize this using mathematical induction.

      Assume that \(k\geq 2\) is an integer for which the inequality \(|r_k-\sqrt{2}| < \dfrac{1}{2^{k-1}}|r_1-\sqrt{2}|\) is true. Using \((*)\) with \(n=k+1\), we have the following \[|r_{k+1}-\sqrt{2}| < \frac{1}{2}|r_k-\sqrt{2}|\] and now using the inductive hypothesis, that \(|r_k-\sqrt{2}|<\frac{1}{2^{k-1}}|r_1-\sqrt{2}|\), we get \[|r_{k+1}-\sqrt{2}| < \frac{1}{2}\left(|r_k-\sqrt{2}|\right) < \frac{1}{2}\left(\frac{1}{2^{k-1}}|r_1-\sqrt{2}|\right) = \frac{1}{2^k}|r_1-\sqrt{2}|\] but \(k=(k+1)-1\), so we have shown that the inequality holds for the integer \(k+1\).

      To summarize, we have shown that the inequality holds for \(n=2\), and we have shown that if the inequality holds for an integer, then it holds for the next integer. This shows that the inequality holds for all integers \(n\geq 2\).

      Finally, since \(|r_1-\sqrt{2}|\) is a fixed quantity, the quantity \(\dfrac{1}{2^{n-1}}|r_1-\sqrt{2}|\) must get closer and closer to \(0\) as \(n\) gets larger and larger. We also have that \(|r_n-\sqrt{2}| < \dfrac{1}{2^{n-1}}|r_1-\sqrt{2}|\) for all \(n\), which means the quantity \(|r_n-\sqrt{2}|\), which is positive, is also getting closer and closer to \(0\) as \(n\) gets larger and larger. It follows that \(r_n-\sqrt{2}\) is very close to zero for very large \(n\), which means \(r_n\) is very close to \(\sqrt{2}\) for very large \(n\). Keep in mind that this is true for any positive starting value \(r_1\).

  1. Here is a brief summary of the behaviours of the sequences.

    When \(f(r)=\dfrac{r-3}{r-2}\), the sequence will repeat with period \(3\) as long as at least three terms in the sequence are defined. The only values of \(r_1\) for which the sequence has an undefined term are \(r_1=2\) and \(r_1=1\).

    When \(f(r) = \dfrac{r-1}{5r+3}\), the sequence will repeat with period \(4\) as long as at least four terms are defined. The only values of \(r_1\) for which the sequence has an undefined term are \(r_1=-\frac{3}{5}\), \(r_1=-\frac{1}{5}\), and \(r_1=\frac{1}{5}\).

    When \(f(r) = \dfrac{r-1}{r+2}\), the sequence will repeat with period \(6\) as long as at least six terms are defined. The only values of \(r_1\) for which the sequence has an undefined term are \(r_1=-2\), \(r_1=-1\), \(r_1=-\frac{1}{2}\), \(r_1=0\), and \(r_1=1\).

    When \(f(r) = \dfrac{2r+2}{3r+3}\), the sequence is undefined after \(r_1\) if \(r_1=-1\). Otherwise, the sequence has \(r_n=\frac{2}{3}\) for all \(n\geq 2\), regardless of the value of \(r_1\).

    Note: These examples, together with the one in part (b), show that the sequences can be periodic with period \(1\), \(2\), \(3\), \(4\), or \(6\). Do you think that any other periods are possible?

    When \(f(r)=\dfrac{r+1}{r-2}\), the sequence converges to \(\dfrac{3-\sqrt{13}}{2}\) unless the sequence has an undefined term. To get an idea of why, try solving the equation \(\dfrac{r+1}{r-2}=r\) for \(r\) (this can be rearranged to a quadratic equation in \(r\)). There are infinitely many values of \(r_1\) for which \(r_n\) is undefined. The first few of them are \[2, 5, \frac{11}{4}, \frac{26}{7}, \frac{59}{19}, \frac{137}{40}, \frac{314}{97}, \frac{725}{217},\dots\] Can you determine how these values are calculated? You might be interested in computing decimal approximations of these values and looking for a pattern.

    As a final remark, we note that not all sequences are "well-behaved" (either periodic or approaching some value). For an example of a more chaotic sequence, try exploring the example in part (a) a little further. Can you see any pattern at all?

Problem 1: October 2023

Problem

Given a positive integer \(n\), the digit sum of \(n\) is the sum of the base \(10\) digits of \(n\). We will denote the digit sum of \(n\) by \(D(n)\). For example, \(D(1409)=1+4+0+9=14\).

Suppose that \(m\) is a positive integer. We will call a list of consecutive positive integers \[a,a+1,a+2,\dots,a+k\] an \(m\)-list if none of \(D(a)\), \(D(a+1)\), \(d(a+2)\), and so on up to \(D(a+k)\) is a multiple of \(m\). For example, the list \(997, 998, 999, 1000, 1001, 1002\) is a \(4\)-list because the digit sums of the integers in the list are \(25\), \(26\), \(27\), \(1\), \(2\), and \(3\), respectively, none of which is a multiple of \(4\).

This problem explores the maximum length of an \(m\)-list for a few values of \(m\).

  1. Show that the maximum length of a \(2\)-list is \(2\). To do this, you must show that there is a \(2\)-list of length \(2\) and you must also show that no list of three or more consecutive positive integers can be a \(2\)-list.

  2. Show that the maximum length of a \(7\)-list is \(12\).

  3. Determine the maximum length of a \(9\)-list.

  4. Determine the maximum length of an \(11\)-list.

Hint

For an integer \(a\), think about how \(D(a)\) and \(D(a+1)\) compare to each other. The relationship is most interesting when \(a+1\) is a multiple of \(10\).

Our solution will make use of some basic properties of remainders. For positive integers \(a\) and \(b\), the remainder when dividing \(a\) by \(b\) can be found by first determining \(qb\), the greatest multiple of \(b\) with \(qb\leq a\), then computing the remainder as \(r=a-qb\). The integer \(q\) can be found by computing \(\dfrac{a}{b}\) and rounding down. For example, the remainder when dividing \(38\) by \(5\) is \(3\) because \(35\) is the greatest multiple of \(5\) that does not exceed \(38\) (in this case, \(q=7\)), and so the remainder is \(38-35=3\). We assume this idea is familiar, but here are a couple of things to think about and keep in mind.

If you have seen modular arithmetic before, it could be useful in writing a solution. Our solution will not use modular arithmetic, but we suggest reading about it anyway since it is quite useful.

Below are some specific hints for the given questions.

  1. Show that if \(D(a)\) and \(D(a+1)\) are both odd, then \(a+1\) is a multiple of \(10\).

  2. First, try to find the maximum length of a \(7\)-list that does not contain a multiple of \(10\). For an integer \(a\), how do the remainders when \(D(a)\) and \(D(a+1)\) are divided by \(7\) relate to each other?

  3. By a rather famous divisibility rule, a positive integer is a multiple of \(9\) if and only if the sum of its digits is a multiple of \(9\).

  4. First show that an \(11\)-list that starts with a multiple of \(10\) has length at most \(29\). Think about the remainders when \(D(a)\) and \(D(a+1)\) are divided by \(11\).

Solution

Before presenting solutions to the various parts of this question, we present a few general facts that will be used throughout the solutions. As well, we will often denote a list of integers enclosed in brackets. For example, we might write \([1,2,3,4,5]\) instead of \(1,2,3,4,5\). This is to emphasize when we want to think of a list is a single object to which we can refer.

Fact 1: If \(n\) is a positive integer with units digit different from \(9\), then \(D(n+1)=D(n)+1\).

Proof. Suppose that \(n\) is a \(k\)-digit positive integer with digits \(A_{1}, A_{2}, \ldots, A_{k-1}, A_{k}\), when read from left to right. That is, \(n\) is \(A_{1}A_{2}\cdots A_{k-1}A_{k}\). Then \(D(n) = A_{1} + A_{2} + \cdots + A_{k-1} + A_k\). Since \(A_{k} \neq 9\), no "carry" occurs when adding \(1\) to \(n\). In other words, \(n+1\) is a \(k\)-digit positive integer with digits \(A_{1},A_{2},\ldots, A_{k-1}, A_{k}+1\) when read from left to right. Therefore, \(D(n+1) = A_{1} + A_{2} + \cdots + A_{k-1} + (A_{k} + 1) = (A_{1} + A_{2} + \cdots + A_{k-1} + A_{k}) + 1 = D(n) + 1\). ◻

Fact 2: Suppose that \(L=[n,n+1,n+2,\dots,n+k]\) is a list of consecutive non-negative integers. If none of \(n+1,n+2,\dots,n+k\) is a multiple of \(10\), then the integers \(D(n),D(n+1),\dots, D(n+k)\) are consecutive.

Proof. None of \(n,n+1,\dots,n+k-1\) has a units digit of \(9\). This is because the alternative would imply that one of \(n+1,n+2,\dots,n+k\) has a units digit of \(0\) and so is a multiple of \(10\). Therefore, we can repeatedly apply Fact 1 to get that \(D(n+1)\) is one more than \(D(n)\), \(D(n+2)\) is one more than \(D(n+1)\), and so on up to \(D(n+k)\) is one more than \(D(n+k-1)\). ◻

Fact 3: Suppose \(m\) is an integer with \(m>1\) and that \([a,a+1,a+2,\dots,a+(m-2)]\) is a list of \(m-1\) consecutive integers with the property that no integer in the list is a multiple of \(m\). Then the remainder after \(a\) is divided by \(m\) is \(1\) and the remainder after \(a+m-2\) is divided by \(m\) is \(m-1\).

Proof. In the hint, it was stated that the remainders after dividing the positive integers \(1,2,3,4,5,\dots\) by \(m\) are \[1,2,3,\dots,m-2,m-1,0,1,2,3,\dots,m-2,m-1,0,1,2,\dots\] That is, the remainders cycle through the values \(1,2,3,\dots,m-2,m-1,0\) in that order.

Consider the list \([a,a+1,a+2,\dots,a+(m-2)]\). Since none of the \(m-1\) integers in this list are multiples of \(m\), none of the remainders after dividing by \(m\) can be \(0\), so the remainders must be \(1,2,3,\dots,m-2,m-1\) in that order. In particular, the remainder after dividing \(a\) by \(m\) is \(1\) and the remainder after dividing \(a+(m-2)\) by \(m\) is \(m-1\). ◻

For a positive integer \(n\) with units digit \(d\), we say that \(n\) has \(k\) trailing \(d\)s if the rightmost \(k\) digits of \(n\) are \(d\) but the rightmost \(k+1\) digits are not equal to \(d\). For example, the integer \(123\) has one trailing \(3\), \(45000\) has three trailing \(0\)s, and \(29199\) has two trailing \(9\)s.

By Fact 1, it is "usually" easy to predict \(D(n+1)\) from \(D(n)\) since if the units digit of \(n\) is not \(9\), then \(D(n+1)=D(n)+1\). However, if the units digit of \(n\) is \(9\), then adding \(1\) causes a carry to happen, so the digit sum can go down. For example, the digit sum of \(2499\) is \(D(2499)=2+4+9+9=24\), but the digit sum of \(2499+1=2500\) is \(D(2500)=2+5+0+0=7\). Fact 4 establishes a relationship between \(D(n)\) and \(D(n+1)\) when \(n\) has a units digit of \(9\).

Fact 4: Suppose \(n\) is a positive integer with \(t\) trailing \(9\)s. Then \(D(n+1) - D(n) = 1-9t\).

Proof. Suppose \(n\) has \(t\) trailing \(9\)s, which means we can assume that \(n\) takes the form \(n=A_1A_2A_3\cdots A_{r-1} A_r99\cdots 99\) where the \(A_i\) are the first \(r\) digits and \(A_r\neq 9\). Since \(A_r\) is a digit that is not \(9\), it must be less than \(9\). Therefore, when we add \(1\) to \(n\), the first \(r-1\) digits do not change, the \(r\)th digit increases by \(1\), and all of the trailing \(9\)s become trailing \(0\)s. In symbols, \(n+1\) is the integer \(A_1A_2\cdots A_{r-1}(A_r+1)00\cdots 00\).

Computing digit sums, \(D(n) = A_1+A_2+\cdots+A_r+9t\) and \(D(n+1) = A_1+A_2+\cdots+A_{r-1}+(A_r+1)\). Subtracting, we get cancellation of \(A_1\) through \(A_r\) and are left with \(D(n+1) - D(n) = 1 - 9t\). ◻

Remark: We will repeatedly use the observation that if \(L=[a,a+1,a+2,\dots,a+k]\) is an \(m\)-list for some \(m\), then every sublist of \(L\) is also an \(m\)-list. One important consequence of this fact is that if we can show that there does not exist an \(m\)-list of length \(k\), then we can conclude that there is no \(m\)-list that is longer than \(k\). Thus, in general, if we want to prove that \(k\) is the maximum length of an \(m\)-list, it suffices to do the following:

  1. The list \([9,10]\) has \(D(9)=9\) and \(D(10)=1\), both of which are odd. Therefore, \([9,10]\) is a \(2\)-list of length \(2\). We will now show that a list of three consecutive positive integers cannot be a \(2\)-list.

    Suppose \(a\) is a positive integer with the property that \(D(a)\) and \(D(a+1)\) are both odd. Since \(D(a)\) is odd, \(D(a)+1\) is even. We are assuming that \(D(a+1)\) is odd, and since \(D(a)+1\) is even, we conclude that \(D(a+1)\neq D(a)+1\).

    By Fact 1, the units digit of \(a\) must be \(9\) (otherwise \(D(a+1)=D(a)+1\)), so the units digit of \(a+1\) is \(0\). Again by Fact 1, \(D(a+2)=D(a+1)+1\), and since \(D(a+1)\) is odd, \(D(a+1)+1=D(a+2)\) is even.

    Now consider the list \([a,a+1,a+2]\). If \(D(a)\) and \(D(a+1)\) are both odd, we have shown that \(D(a+2)\) is even. This means it is impossible for \(D(a)\), \(D(a+1)\), and \(D(a+2)\) to all be odd, so we conclude that a \(2\)-list of length \(3\) cannot exist.

  2. The arguments presented in this part and in part (d) rely on examining the location of multiples of \(10\) in lists of consecutive integers. For this part, because of Fact 2, seven consecutive integers will have seven consecutive digit sums unless a multiple of \(10\) causes a carry. To build a \(7\)-list of length more than six, there needs to be a multiple of \(10\) somewhere in the middle to avoid ever having seven consecutive digit sums. You might be able to guess from this that the maximum length should be around \(12\).

    Suppose \(L=[a,a+1,a+2,\dots,a+12]\) is an arbitrary list of \(13\) consecutive non-negative integers. We will show that \(L\) cannot be a \(7\)-list and this will show that a \(7\)-list cannot have length \(13\).

    Since \(L\) contains \(13\) consecutive integers, it must contain at least one multiple of \(10\). Thus, there must be some \(k\) with \(0\leq k\leq 12\) such that \(a+k\) is a multiple of \(10\).

    Case 1: \(0\leq k\leq 6\).

    Since \(k\leq 6\), \(a+k+6\leq a+12\). The list \(L\) contains the integers \(a\) through \(a+12\), so we conclude that the seven integers \(a+k,a+k+1,\dots,a+k+6\) are all in \(L\). Moreover, the smallest multiple of \(10\) after \(a+k\) is \(a+k+10\), so none of \(a+k+1,a+k+2,\dots,a+k+6\) is a multiple of \(10\) since they are all strictly between two consecutive multiples of \(10\).

    By Fact 2, the integers \(D(a+k),D(a+k+1),\dots,D(a+k+6)\) are consecutive. Any list of seven consecutive integers must contain a multiple of \(7\), so we conclude that \(L\) is not a \(7\)-list.

    Case 2: \(7\leq k\leq 12\).

    Since \(7\leq k\), \(a+7\leq a+k\) which can be rearranged to get \(a\leq a+k-7\). By similar reasoning to the beginning of Case 1, the seven integers \(a+k-7,a+k-6,\dots,a+k-1\) are all in \(L\). As well, they are strictly between \(a+k-10\) and \(a+k\), which are consecutive multiples of \(10\). Therefore, none of \(a+k-7,a+k-6,\dots,a+k-1\) is a multiple of \(10\).

    By Fact 2, \(D(a+k-7),D(a+k-6),\dots,D(a+k-1)\) are consecutive, so one of them must be a multiple of \(7\). Therefore, \(L\) is not a \(7\)-list.

    Cases 1 and 2 address all possibilities for the location of a multiple of \(10\) in \(L\). In both cases, \(L\) is not a \(7\)-list. We conclude that a list of \(13\) consecutive non-negative integers cannot be a \(7\)-list.

    To help find a \(7\)-list of length \(12\), we can modify the reasoning above slightly. To that end, suppose \(M=[a,a+1,a+2,\dots,a+11]\) is a \(7\)-list. In the previous paragraphs, we essentially used the fact that if seven consecutive non-negative integers do not include a multiple of \(10\), then one of their digit sums must be a multiple of \(7\). Therefore, for \(M\) to be a \(7\)-list, every sublist of seven-consecutive integers must contain a multiple of \(10\). We leave it to the reader to verify that this forces \(a+6\) to be a multiple of \(10\).

    Since \(a+6\) is a multiple of \(10\), the closest multiples of \(10\) to \(a+6\) are \(a-4\) and \(a+16\). Therefore, the list \(a,a+1,\dots,a+5\) does not contain a multiple of \(10\), and the only multiple of \(10\) in the list \(a+6,a+7,\dots,a+11\) is \(a+6\). By Fact 2, \[D(a), D(a+1), D(a+2), D(a+3), D(a+4), D(a+5)\] and \[D(a+6), D(a+7), D(a+8), D(a+9), D(a+10), D(a+11)\] are lists of six consecutive integers. We are assuming \(M\) is a \(7\)-list, so no integer in either of these lists is a multiple of \(7\). By Fact 3, the remainder after dividing \(D(a+5)\) by \(7\) is \(7-1=6\). Also by Fact 3, the remainder after dividing \(D(a+6)\) by \(7\) is \(1\).

    To summarize, if \(M=[a,a+1,\dots,a+11]\) is a \(7\)-list, then the following must be true.

    The first condition implies that \(a+5\) has a units digit of \(9\), so suppose that \(n+5\) has \(t\) trailing \(9\)s. By Fact 4, \(D(n+6) - D(n+5) = 1-9t\). The second two conditions imply that there are integers \(m\) and \(n\) such that \(D(a+5)=7n+6\) and \(D(a+6)=7m+1\). Substituting into \(D(a+6)-D(a+5)=1-9t\), we obtain \((7n+1) - (7m+6) = 1-9t\) which can be rearranged to get \(2t-6 = 7(m-n-t)\). We know that \(t\) is a positive integer, and this shows that \(2t-6\) must be a multiple of \(7\). The smallest positive integer \(t\) with the property that \(2t-6\) is a multiple of \(7\) is \(t=3\) since \(2(3)-6=0\), which is a multiple of \(7\).

    We are looking for an integer \(a\) such that \(a+5\) ends in three \(9\)s and has the property that \(D(n+5)\) is six more than a multiple of \(7\). Thus, \(a+5\) will have the form \(x999\) where \(x\) is some string of digits. In fact, \(D(999)=9+9+9=27\) has a remainder of \(6\) when divided by \(7\), so we set \(a+5=999\) or \(a=994\). Indeed, if we set \[M=[994, 995, 996, 997, 998, 999, 1000, 1001, 1002, 1003, 1004, 1005]\] the digit sums of the integers in \(M\) are \(22, 23, 24,25,26,27,1,2,3,4,5,6\), none of which is a multiple of \(7\). Therefore, \(M\) is a \(7\)-list of length \(12\).

    This is actually the earliest \(7\)-list of length \(12\). Others can be found by prepending digits to 994 in such a way that the number of trailing \(9\)s of \(a+5\) does not change, and the remainder after dividing the digit sum by \(7\) does not change. This can be done by prepending any digits that have a sum that is a multiple of \(7\), provided the rightmost new digit is not a \(9\).

    For example, we could take \(a\) to be \(7994\), \(16994\), \(25994\), \(662994\), and so on.

  3. Following the reasoning from (b), one might think that we can find a \(9\)-list of length \(8+8=16\). Specifically, we might expect that we can find a list of the form \([a, a+1, \dots, a+15]\) where \(a+8\) is a multiple of \(10\) so that there are never nine consecutive integers without a multiple of \(10\). In fact, the maximum length of a \(9\)-list is eight, so the approach in part (b) cannot be applied here. You might like to try to follow the reasoning from part (b) through to see exactly what goes wrong. The proof given here uses the well-known fact that a positive integer \(n\) is a multiple of \(9\) if and only if \(D(n)\) is a multiple of \(9\).

    A list of nine consecutive integers must contain a multiple of \(9\), so it must contain an integer whose digit sum is a multiple of \(9\). Therefore, a list of \(9\) consecutive integers cannot be a \(9\)-list.

    Any list of eight consecutive integers, none of which is a multiple of \(9\), must be a \(9\)-list since none of the digit sums are multiples of \(9\). An example of a \(9\)-list of length \(8\) is \([1,2,3,4,5,6,7,8]\).

  4. It might come as a surprise, but the maximum length of an \(11\)-list is \(38\).

    To get an idea of how one might guess this, we will first determine the maximum length of an \(11\)-list that starts with a multiple of \(10\).

    Suppose \(L=[a,a+1,a+2,\dots,a+19]\) is an \(11\)-list of length \(20\) with the property that \(a\) is a multiple of \(10\). By Fact 2, \(D(a), D(a+1), \dots,D(a+9)\) and \(D(a+10), D(a+11), \dots, D(a+19)\) are lists of ten consecutive integers. Since we are assuming that \(L\) is an \(11\)-list, no integer in either of these lists is a multiple of \(11\). Therefore, by Fact 3, the remainder after \(D(a+9)\) is divided by \(11\) is \(10\) and the remainder after \(D(a+10)\) is divided by \(11\) is \(1\). This implies the existence of integers \(m\) and \(n\) such that \(D(a+9) = 11m+10\) and \(D(a+10)=11n+1\).

    Since \(a\) is a multiple of \(10\), the units digit of \(a+9\) is \(9\). Suppose \(a+9\) has \(t\) trailing \(9\)s. By Fact 4, \(D(a+10)-D(a+9) = 1-9t\). Substituting \(D(a+9) = 11m+10\) and \(D(a+10)=11n+1\) into this equation, we get \[(11n+1) - (11m+10) = 1-9t\] which can be rearranged to get \(9t = 11(m-n)+10\). This means \(t\) is a positive integer with the property that \(9t\) is ten more than a multiple of \(11\). It can be checked that \(t=6\) is the smallest positive integer with this property.

    We have shown the following: if \([a,a+1,a+2,\dots,a+19]\) is an \(11\)-list of length \(20\) with the property that \(a\) is a multiple of \(10\), then \(a+9\) has at least six trailing \(9\)s. We can use this fact to prove the following:

    1. An \(11\)-list that starts with a multiple of \(10\) cannot have length \(30\).

    2. An \(11\)-list cannot have length \(39\).

    To prove (i), assume that \(L=[a,a+1,a+2,\dots,a+29]\) is an \(11\)-list of length \(30\) and that \(a\) is a multiple of \(10\). We will show that this implies something that is plainly false, which will allow us to conclude that such an \(11\)-list cannot exist.

    The fact that \(L\) is an \(11\)-list implies that the lists \(M=[a,a+1,\dots,a+19]\) and \(N=[a+10,a+11,\dots,a+29]\) are both \(11\)-lists. Moreover, \(a\) is a multiple of \(10\), so \(a+10\) is a multiple of \(10\). Thus, \(M\) and \(N\) are both \(11\)-lists of length \(20\) that start with a multiple of \(10\). By what was established earlier, both \(a+9\) and \(a+10+9=a+19\) have at least six trailing \(9\)s.

    The difference between two integers with at least six trailing \(9\)s must have at least six trailing \(0\)s. However, \((a+19)-(a+9)=10\) has only one trailing \(0\). We have shown that if an \(11\)-list starts with a multiple of \(10\) and has length \(30\), then \(10\) has at least six trailing \(0\)s. Since \(10\) has only one trailing \(0\), we conclude that it must be impossible for an \(11\)-list to have length \(30\) and start with a multiple of \(10\). Note: The technique just used is known as a proof by contradiction.

    To prove (ii), we can apply (i). Suppose \(L=[a,a+1,a+2,\dots,a+38]\) is a list of \(39\) consecutive positive integers. Among the first ten integers in \(L\), there must be a multiple of \(10\). Suppose \(k\) is an integer with \(0\leq k\leq 9\) such that \(a+k\) is a multiple of \(10\). Observe that \(a+k+29\leq a+9+29=a+38\), which means the list \(M=[a+k,a+k+1,\dots,a+k+29]\) is completely contained in \(L\). The list \(M\) has length \(30\) and starts with a multiple of \(10\), so it cannot be an \(11\)-list by (i). Since \(L\) contains a sub-list that is not an \(11\)-list, it cannot be an \(11\)-list. Therefore, an \(11\)-list cannot have length \(39\).

    We can now use what we have done to find an \(11\)-list of length \(38\). Suppose that \(L=[a,a+1,a+2,\dots,a+37]\) is an \(11\)-list. There must be an integer \(k\) with \(0\leq k\leq 9\) such that \(a+k\) is a multiple of \(10\). If \(0\leq k\leq 8\), then \(a+k+29\leq a+37\), so \([a+k,a+k+1,\dots,a+k+29]\) is entirely contained in \(L\). This would imply the existence of an \(11\)-list of length \(30\) that starts with a multiple of \(10\), which is impossible by (i). Since \(0\leq k\leq 8\) is impossible, we conclude that \(k=9\).

    We assumed that \(L=[a,a+1,a+2,\dots,a+37]\) was an \(11\)-list and deduced that \(a+9\) is a multiple of \(10\). The list \([a+9,a+10,\dots,a+28]\) is completely contained in \(L\), has length \(20\), and starts with a multiple of \(10\). Therefore, from the argument at the beginning of the solution to this part, \(a+9+9=a+18\) has at least six trailing \(9\)s. As well, Since \(a+9\) is a multiple of \(10\), we can apply Fact 2 to \(a+9,a+10,\dots,a+18\) to get that \(D(a+9), D(a+10),\dots,D(a+18)\) is a list of \(10\) consecutive integers. Since \(L\) is an \(11\)-list, none of them is a multiple of \(11\). By Fact 3, the remainder after \(D(a+18)\) is divided by \(11\) is \(10\).

    Therefore, we will look for an integer \(a\) with the property that \(a+18\) has \(6\) trailing \(9\)s and \(D(a+18)\) is \(10\) more than a multiple of \(11\). The integer \(999999\) has \(D(999999)=54\) which is \(10\) more than a multiple of \(11\), so we guess that \(a+18=999999\), or \(a=999981\). It can be checked that the list \([999981, 999982,\dots,1000018]\) is an \(11\)-list of length \(38\). It also follows from our reasoning that this is the first such \(11\)-list.

Problem 2: November 2023

Problem

This month’s problem is based on the following general question: If you draw a "loop" in the Cartesian plane, is it always possible to find four points on that loop that are the vertices of a square? For example, the diagram below has a loop (the solid line) and a square drawn (the dashed line) with its four vertices on the loop.

Although it is a bit informal, it should be sufficient to think of a "loop" as a curve that you could draw by starting your pencil somewhere on a page and moving the pencil around the page eventually ending up where it started. Such a loop could be "smooth" (like a circle), "jagged" (like a polygon), or some combination of the two.

  1. In each of parts (i) through (v), find four points on the loop that are the vertices of a square.

    1. the circle with equation \(x^2 + y^2 = 1\)

    2. the ellipse with equation \(\dfrac{x^2}{a^2} + \dfrac{y^2}{b^2} = 1\) where \(a\) and \(b\) are fixed positive real numbers

    3. the polygon with vertices \((1,0)\), \(\left(\frac{1}{2},\frac{\sqrt 3}{2}\right)\), \(\left(-\frac{1}{2},\frac{\sqrt 3}{2}\right)\), \((-1,0)\), \(\left(-\frac{1}{2},-\frac{\sqrt 3}{2}\right)\), and \(\left(\frac{1}{2},-\frac{\sqrt 3}{2}\right)\)

    4. the boundary of the region enclosed by the parabola with equation \(y = -\dfrac{1}{2}x^2 +\dfrac{1}{6}x+\dfrac{16}{9}\) and the line with equation \(y = x\)

    5. the boundary of the region enclosed by the parabolas with equations \(y = x^2 + \dfrac{2}{3}x - \dfrac{4}{3}\) and \(y = -x^2 + \dfrac{2}{3} x + \dfrac{4}{3}\)

  2. Show that for every acute triangle there are exactly three squares whose vertices all lie on the perimeter of the triangle.

Hint

    1. Because of the rotational symmetry of circles, there are lots of squares with their vertices lying on the circle with equation \(x^2+y^2=1\). In fact, given any point on the circle, there is a square with that point as one of its vertices and the other three vertices somewhere else on the circle. It might be useful for part (v) to spend some time thinking about this.

    2. Try looking for a square with the property that all four of its sides are parallel to either the \(x\)-axis or the \(y\)-axis. What are the coordinates of a square centred at the origin with its sides parallel to the axes?

    3. It will be helpful to have an accurate sketch of the hexagon. Similar to part (ii), there is a square with its sides parallel to the axes.

    4. After sketching the region, it shouldn’t be hard to believe that there is a square with one of its sides on the line with equation \(y=x\). The opposite side will lie on a line with the same slope.

    5. The figure has \(180\degree\) rotational symmetry about the origin, so try looking for a square that is centred at the origin. If such a square exists, it should also have \(108\degree\) rotational symmetry about the origin. Observations from part (i) might be useful when thinking about such squares.

  1. In our solution, we found it useful to coordinatize and assume that one the sides of the the triangle is on the \(x\)-axis in such a way that one of the vertices is at the origin.

Solution

    1. Because a circle has so much symmetry, there are many squares whose four vertices all lie on the circle. For example, the points \((1,0)\), \((0,1)\), \((-1,0)\), and \((0,-1)\) are the vertices of a square and all lie on the circle with equation \(x^2+y^2=1\). As well, the four points \(\left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right)\), \(\left(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right)\), \(\left(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right)\), and \(\left(\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right)\) are the vertices of a square and all lie on the circle.

      Note: In general, if we start with a point \(P\) and rotate \(P\) repeatedly by \(90\degree\) counterclockwise about the origin, the four points obtained are always the vertices of a square. Starting with the point with coordinates \((a,b)\), the coordinates of the point obtained by a rotation of \(90\degree\) counterclockwise about the origin are \((-b,a)\). If we rotate \(90\degree\) counterclockwise two more times, we get the points with coordinates \((-a,-b)\) and \((b,-a)\). Thus, for any real numbers \(a\) and \(b\), the points with coordinates \((a,b)\), \((-b,a)\), \((-a,-b)\), and \((b,-a)\) are the vertices of a square. This will be useful in later parts. In addition, if \((a,b)\) is a point on the circle with equation \(x^2+y^2=1\), then \(a^2+b^2=1\). Then since \((\pm a)^2 + (\pm b)^2=a^2+b^2=1\), the four points \((a,b)\), \((-b,a)\), \((-a,-b)\), and \((b,-a)\), which are the vertices of a square, all lie on the circle.

    2. Observe that the four points \((a,0)\), \((0,b)\), \((-a,0)\), and \((0,-b)\) are on the ellipse with equation \(\dfrac{x^{2}}{a^{2}} + \dfrac{y^{2}}{b^{2}} = 1\), as shown in the illustration below.

      Because \(x^2=(-x)^2\) and \(y^2=(-y)^2\), if \((s,t)\) is a point on the ellipse, then \((s,-t)\) and \((-s,t)\) are both on the ellipse. Therefore, the ellipse has reflective symmetry in the \(x\)-axis and the \(y\)-axis, which is also evident from the diagram. It is reasonable to expect there to be a square inscribed in the ellipse that also has reflective symmetry in the two axes. The vertices of such a square should be of the form \((t,t)\), \((-t,t)\), \((-t,-t)\), and \((t,-t)\) for some real number \(t\neq0\).

      Notice that the point \((t,t)\) is on the line with equation \(y=x\), so assuming such a square exists, we should be able to find one of its vertices by solving the system of equations \[\begin{align*} y & = x \\ \frac{x^2}{a^2} + \frac{y^2}{b^2} &= 1.\end{align*}\] Substituting the first equation into the second and finding a common denominator gives \[\frac{b^2x^2 + a^2x^2}{a^2b^2} = 1\] which rearranges to give \[x^2 = \frac{a^2b^2}{a^2 + b^2}.\]

      Since \(a\) and \(b\) are positive, \(\sqrt{a^2b^2}=ab\), and so we get that \(x=\dfrac{ab}{\sqrt{a^2+b^2}}\). We therefore expect that the four points \[\left(\frac{ab}{\sqrt{a^2 + b^2}},\frac{ab}{\sqrt{a^2 + b^2}}\right), \left(-\frac{ab}{\sqrt{a^2 + b^2}},\frac{ab}{\sqrt{a^2 + b^2}}\right),\]\[ \left(-\frac{ab}{\sqrt{a^2 + b^2}},-\frac{ab}{\sqrt{a^2 + b^2}}\right), \left(\frac{ab}{\sqrt{a^2 + b^2}},-\frac{ab}{\sqrt{a^2 + b^2}}\right)\] are all on the ellipse and are the vertices of a square. As discussed in the solution to part (i), these points are of the form \((t,t)\), \((-t,t)\), \((-t,-t)\), and \((t,-t)\), so they are the vertices of a square. It is an exercise to verify that they are all on the ellipse.

      Below is a picture of the ellipse with a square inscribed.

      Follow up question: If \(a = b\), then the ellipse is a circle and there are infinitely many inscribed squares. If \(a \neq b\), is the square in the solution above the only square inscribed in the ellipse?

    3. In this case, the loop is the regular hexagon pictured below.

      A hexagon centred at the origin with top and
bottom sides horizontal.

      Similar to the situation in part (ii), the loop has reflective symmetry in both the \(x\) and \(y\) axes. Thus, we might again guess that there is an inscribed square with reflective symmetry in both axes. If such a square exists, then one of the vertices will have the form \((t,t)\). Thus, we are looking for the points (there are two of them) where the line with equation \(y=x\) intersects the hexagon.

      The line with equation \(y=x\) must intersect the part of the hexagon that is in the first quadrant. Notice that \(\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)\) is above the line with equation \(y=x\), so the horizontal line segment in the first quadrant will not intersect the line with equation \(y=x\). Therefore, the intersection point we seek is on the line segment joining \((1,0)\) to \((\frac{1}{2},\frac{\sqrt 3}{2})\), which has equation \(y = -\sqrt{3}x+\sqrt{3}\). To find the point of intersection, we set \(x=-\sqrt{3}x+\sqrt{3}\) and solve to get \(x=\frac{\sqrt 3}{1 + \sqrt 3}\). Recall that we hope the square has vertices at \((t,t)\), \((-t,t)\), \((-t,-t)\), and \((t,-t)\). You can check that with \(t = \frac{\sqrt 3}{1 + \sqrt 3}\), these four points lie on the given hexagon. Below is a picture of the hexagon with the inscribed square.

      Follow up question: There are two other squares inscribed in the hexagon. They arise from rotating the square in the solution by \(60\degree\) clockwise or \(60\degree\) counterclockwise about the origin. Are these the only possible squares?

    4. The graphs of the relations \(y = -\frac{1}{2}x^2 +\frac{1}{6}x+\frac{16}{9}\) and \(y=x\) are pictured on the same axes below. The loop, which is the boundary of the region enclosed by the two graphs, is bold.

      One approach is to try to find a square with two adjacent vertices on the line with equation \(y=x\) and the other two vertices on the parabola. Why should we expect such a square even exists? Imagine drawing a line \(L\) that is parallel to the line with equation \(y=x\), lies above the line with equation \(y = x\), and intersects the parabola twice. By drawing lines with slope \(-1\) through these two points of intersection, we get a rectangle with two vertices on the parabola and two vertices on the line. The diagrams below show such configurations with the rectangle shaded in each case.

      If the points of intersection of \(L\) with the parabola are far apart, as in the left diagram, then the two sides of the rectangle that are parallel to the line \(y=x\) are longer than the other two sides. If the points of intersection are close together, as in the right diagram, then the two sides of the rectangle that are parallel to the line \(y=x\) are shorter than the other two sides. It seems reasonable to guess that somewhere in between those two extremes is a happy medium where the rectangle is a square. Formally, this kind of argument is an application of something called the Intermediate Value Theorem.

      Let’s use this thinking to find the coordinates of such a square. Let \(L\) be the line with equation \(y = x + b\) where \(b\) is the positive real number that will cause the rectangle to be a square. The vertices of the square we hope for are the points of intersection of \(L\) with the parabola. To find these points, we set \(x+b\) equal to \(-\frac{1}{2}x^2+\frac{1}{6}x+\frac{16}{9}\) and rearrange to get. \[\begin{align*} x+b &= -\frac{1}{2}x^2+\frac{1}{6}x+\frac{16}{9} \\ 0 &= \frac{1}{2}x^2+\frac{5}{6}x+b-\frac{16}{9} \\ 0 &= 9x^2+15x+(18b-32)\end{align*}\] where the last line is obtained by multiplying the second-last line by \(18\).

      We can now use the quadratic formula to get \[\begin{align*} x &= \dfrac{-15\pm\sqrt{15^2-4(9)(18b-32)}}{18} \\ &= \dfrac{-5\pm\sqrt{5^2-4(18b-32)}}{6} \\ &= \dfrac{-5\pm3\sqrt{17-8b}}{6}\end{align*}\]

      Note: Since we are assuming that the line \(y=x+b\) has two points of intersection with the parabola, this quadratic equation must have two distinct real solutions. This means we must have \(17-8b > 0\) and so \(b <\frac{17}{8}\). Revisiting the diagrams, it should be clear that there is an upper bound on the values of \(b\) that can result in the line intersecting the parabola. The diagrams also indicate that \(b > 0\).

      Therefore, the \(x\)-coordinates of the points of intersection are \(\dfrac{-5-3\sqrt{17-8b}}{6}\) and \(\dfrac{-5+3\sqrt{17-8b}}{6}\).

      The difference between the \(x\)-coordinates of these points is \[\dfrac{-5+3\sqrt{17-8b}}{6} - \dfrac{-5-3\sqrt{17-8b}}{6} = \sqrt{17-8b}\] and since the points are on a line of slope \(1\), the distance between the \(y\)-coordinates is also \(\sqrt{17-8b}\). Therefore, the distance between the two points is \[\begin{align*} \sqrt{\left(\sqrt{17-8b}\right)^2 + \left(\sqrt{17-8b}\right)^2 } &= \sqrt{2(17-8b)} \\ &= \sqrt{34-16b}\end{align*}\]

      We will leave it as an exercise to show that the perpendicular distance between \(L\) and the line with equation \(y=x\) is equal to \(\dfrac{b}{\sqrt{2}}\). This means our square has sides of length \(\sqrt{34-16b}\) and \(\dfrac{b}{\sqrt{2}}\). A square has four equal sides, so this implies the equation \(\sqrt{34-16b} = \dfrac{b}{\sqrt{2}}\). Squaring both sides, we have \(34-16b = \dfrac{b^2}{2}\) which can be rearranged to get \(b^2+32b-68=0\). Factoring gives \((b-2)(b+34)=0\), so the possible values of \(b\) are \(2\) and \(-34\).

      Since we need \(b\) to be positive, we conclude that \(b=2\), so the line \(L\) has equation \(y=x+2\). The \(x\)-coordinates of the points of intersection of \(L\) with the parabola were computed earlier. Substituting \(b=2\) into these expressions, we get \(x\)-coordinates of \(\dfrac{-5-3\sqrt{17-8b}}{6}=-\dfrac{4}{3}\) and \(\dfrac{-5+3\sqrt{17-8b}}{6} = -\dfrac{1}{3}\). These points lie on the line with equation \(y=x+2\), so the coordinates of two of the vertices of the square are \(\left(-\frac{4}{3},\frac{2}{3}\right)\) and \(\left(-\frac{1}{3},\frac{5}{3}\right)\).

      To find the other two vertices, we can find the equations of the lines of slope \(-1\) through each of these points, then find their intersection points with the line with equation \(y=x\). We will not include the calculations here, but the resulting points are \(\left(-\frac{1}{3},-\frac{1}{3}\right)\) and \(\left(\frac{2}{3},\frac{2}{3}\right)\).

      Indeed, it is not difficult to check that the points \[\left(-\frac{4}{3},\frac{2}{3}\right), \left(-\frac{1}{3},-\frac{1}{3}\right), \left(\frac{2}{3},\frac{2}{3}\right), \left(-\frac{1}{3},\frac{5}{3}\right)\] are the vertices of a square. Below is a plot of the loop along with the square with these four points as its vertices.

    5. The two parabolas are pictured below. The loop is bold.

      An upward opening parabola and a downward opening parabola intersect at two points and enclose a region with a bold border.

      By the discussion at the end of the solution to part (i), the four points \[\left(1,\frac{1}{3}\right), \left(-\frac{1}{3}, 1\right),\left(-1,-\frac{1}{3}\right),\left(\frac{1}{3},-1\right).\] are the vertices of a square. Furthermore, you can check that these four points all lie on the loop.

      For the rest of the solution to this part, we will show how one might find these four points. The task is a bit trickier here because, unlike in earlier parts, it is not easy to guess what the slope of the sides of the square should be. However, there is still some symmetry that we can use. Specifically, the loop has \(180\degree\) rotational symmetry about the origin because the two parabolas are each the result of rotating the other \(180\degree\) about the origin. This is not difficult to believe from the diagram, but it can also be verified algebraically.

      This symmetry suggests two things. The first is that we should look for a square that has \(180\degree\) rotational symmetry about the origin. The second is that each of the two parabolas should contain two vertices of the square.

      A square that has \(180\degree\) rotational symmetry about the origin must also have \(90\degree\) rotational symmetry about the origin (you might want to take some time to convince yourself of this). Again by the discussion from part (i), the vertices of the square should be at the points with coordinates \((a,b)\), \((-b,a)\), \((-a,-b)\), and \((b,-a)\) where \(a\) and \(b\) are some real numbers.

      The parabola with equation \(y=x^2+\frac{2}{3}x-\frac{4}{3}\) should contain two vertices of the square with the property that one of these vertices is the result of rotating the other vertex \(90\degree\) about the origin. Thus, for some \(a\) and \(b\), this parabola should contain the points \((a,b)\) and \((-b,a)\). This implies the following two equations in \(a\) and \(b\): \[\begin{align*} b &= a^2 + \frac{2}{3}a-\frac{4}{3} \\ a &= (-b)^2 + \frac{2}{3}(-b) - \frac{4}{3}\end{align*}\] The second equation gives an expression for \(a\) in terms of \(b\), so we can substitute this expression into the first equation and simplify as follows: \[\begin{align*} b &= \left((-b)^2 + \frac{2}{3}(-b) - \frac{4}{3}\right)^2 + \frac{2}{3}\left((-b)^2 + \frac{2}{3}(-b) - \frac{4}{3}\right) - \frac{4}{3} \\ &= \left(b^2-\frac{2}{3}b-\frac{4}{3}\right)^2 + \frac{2}{3}\left(b^2-\frac{2}{3}b-\frac{4}{3}\right) - \frac{4}{3} \\ 9b &= (3b^2-2b-4)^2+2(3b^2-2b-4)-12 & \text{(multiply by $9$)}\\ 9b &= 9b^4 - 12b^3-14b^2+12b-4 \\ 0 &= 9b^4-12b^3-14b^2+3b-4\end{align*}\] In general, we should not expect to easily find a closed expression for the root of a quartic polynomial. However, this question was designed to work out nicely. After some checking, you might notice that \(b=-1\) is a root of this equation. Indeed, \(9(-1)^4-12(-1)^3-14(-1)^2+3(-1)-4=0\). We could factor to get \[0 = (b+1)(9b^3-21b^2+7b-4)\] but \(b=-1\) is the value we seek, so the other roots of the quartic are not of any use in this solution (though you might want to think about whether they have any "geometric" meaning). With \(b=-1\), the equation \(a = (-b)^2 + \frac{2}{3}(-b) - \frac{4}{3}\) implies \(a=\frac{1}{3}\), so one of the points is \((-b,a)=\left(1,\frac{1}{3}\right)\). This is the first of the four points listed at the start of the solution to this part. Rotating the point \(\left(1,\frac{1}{3}\right)\) by \(90\degree\), \(180\degree\), and \(270\degree\) about the origin gives the other three points. You can check that each of the two parabolas contains two of these points. Below is a diagram of the loop with the square included.

  1. Given \(\triangle ABC\), there exists \(\triangle DEF\) so that \(\triangle ABC\) is similar to \(\triangle DEF\) and \(DE\) is horizontal with length 1. So we proceed by examining such a triangle \(\triangle DEF\) with vertices \(D(0,0)\), \(E(1,0)\), and \(F(a,b)\) where \(a>0\) and \(b>0\). Moreover, if \(\triangle ABC\) is acute, then so is \(\triangle DEF\) and we must have \(0<a<1\).

    We will show that there is a unique square whose vertices are on the perimeter of \(\triangle DEF\) with two of its vertices on \(DE\). To find such a square, we will assume there is such a square, deduce conditions on the location of the vertices of such a square, and then confirm that the four points we find actually satisfy the given conditions.

    Suppose \(W\), \(X\), \(Y\), \(Z\) are the vertices of the square, with \(W\) and \(X\) on \(DE\). The diagram below shows what this picture should look like.