Problem of the Month 2022-2023

Problem 0: September 2022

1. Consider the integers $392$, $487$, $638$, and $791$. For each of these integers, do the following.

   1. Determine whether the integer is a multiple of $7$.

   2. With the hundreds digit equal to $A$, the tens digit equal to $B$, and the units digit equal to $C$, compute $2A+3B+C$.

   What do you notice?

2. Suppose $n=ABC$ is a three-digit integer ($A$ is the hundreds digit, $B$ is the tens digit, and $C$ is the units digit). Show that if $ABC$ is a multiple of $7$, then $2A+3B+C$ is a multiple of $7$.

3. Show that if $2A+3B+C$ is a multiple of $7$, then the three-digit integer $n=ABC$ is a multiple of $7$.

4. Suppose $ABCDEF$ is a six-digit integer that has each of its digits different from $0$. Show that $ABCDEF$ is a multiple of $7$ if and only if $BCDEFA$ is a multiple of $7$.

5. Think of ways to generalize the fact in part (d).

Problem 1: October 2022

In any triangle, there is a unique circle called its incircle that can be drawn in such a way that it is tangent to all three sides of the triangle. For a given triangle, the radius of its incircle is known as its inradius and is denoted by $r$.

For each side of the triangle (which is tangent to the incircle), another tangent to the incircle can be drawn in such a way that it is parallel to that side. The three sides as well as these three new tangents give a total of six tangents to the incircle. They uniquely determine a hexagon that we will call the Seraj hexagon of the triangle.

Finally, for a given triangle, we will denote by $s$ its semiperimeter, which is defined to be half of its perimeter.

The diagram below is of a triangle showing its incircle and Seraj hexagon.

1. Sketch the $3$–$4$–$5$ triangle with its incircle and Seraj hexagon. Compute its inradius, semiperimeter, and the area of its Seraj hexagon.

2. Find a general expression for the area of a triangle in terms only of its inradius and semiperimeter.

3. Find a general expression for the area of the Seraj hexagon of a triangle in terms of its three side lengths, its semiperimeter, and its inradius.

4. What is the largest possible value that can be obtained by dividing the area of a triangle’s Seraj hexagon by the total area of the triangle?

Problem 2: November 2022

Let $\varphi ={\displaystyle \frac{1+\sqrt{5}}{2}}\approx 1.61803$. For integers $d_k,d_{k-1},\dots ,d_1,d_0,d_{-1},\dots ,d_{-r}$, each equal to $0$ or $1$, the expression $$(d_k{d}_{k-1}\cdots d_2{d}_1{d}_0.d_{-1}{d}_{-2}\cdots d_{-r}{)}_{\varphi }$$ is called a base $\varphi$ expansion and represents the real number $$d_k{\varphi }^k+d_{k-1}{\varphi }^{k-1}+\cdots +d_1\varphi +d_0+d_{-1}{\varphi }^{-1}+d_{-2}{\varphi }^{-2}+\cdots +d_{-r}{\varphi }^{-r}$$ The integers $d_k$ through $d_{-r}$ are called the digits of the expansion. For example, the base $\varphi$ expansion ${1101.011}_{\varphi }$ represents the real number $$(1\times {\varphi }^3)+(1\times {\varphi }^2)+(0\times \varphi )+1+(0\times {\varphi }^{-1})+(1\times {\varphi }^{-2})+(1\times {\varphi }^{-3})$$ which can be simplified to get $$\begin{array}{rl}{\varphi }^3+{\varphi }^2+1+\frac{1}{{\varphi }^2}+\frac{1}{{\varphi }^3}& ={\left(\frac{1+\sqrt{5}}{2}\right)}^3+{\left(\frac{1+\sqrt{5}}{2}\right)}^2+1+{\left(\frac{2}{1+\sqrt{5}}\right)}^2+{\left(\frac{2}{1+\sqrt{5}}\right)}^3\\ & =\frac{16+8\sqrt{5}}{8}+\frac{6+2\sqrt{5}}{4}+1+\frac{4}{6+2\sqrt{5}}+\frac{8}{16+8\sqrt{5}}\\ & =(2+\sqrt{5})+(\frac{3}{2}+\frac{1}{2}\sqrt{5})+1+(\frac{3}{2}-\frac{1}{2}\sqrt{5})-(2-\sqrt{5})\\ & =4+2\sqrt{5}\end{array}$$ and so ${1101.011}_{\varphi }=4+2\sqrt{5}$.

1. What are the real numbers represented by ${1011}_{\varphi }$ and ${10000}_{\varphi }$?

2. Find a base $\varphi$ expansion of the real number $4+3\sqrt{5}$.

3. Show that ${\varphi }^2=\varphi +1$ and use this to deduce that ${\varphi }^{n+1}={\varphi }^n+{\varphi }^{n-1}$ for all integers $n$.

4. Show that every positive integer has a base $\varphi$ expansion and find a base $\varphi$ expansion for each positive integer from $1$ through $10$. One approach is to prove and use the following two facts.

   • If a real number $n$ has a base $\varphi$ expansion, then it has a base $\varphi$ expansion that does not have two consecutive digits equal to $1$.

   • If a real number $n$ has a base $\varphi$ expansion, then it has a base $\varphi$ expansion that has its units digit, $d_0$, equal to $0$.

Problem 3: December 2022

This month’s problem is an extension of Problem 6 from the November 2022 Canadian Senior Mathematics Contest. Here is the original problem.

A bag contains exactly 15 marbles of which $3$ are red, $5$ are blue, and $7$ are green. The marbles are chosen at random and removed one at a time from the bag until all of the marbles are removed. One colour of marble is the first to have $0$ remaining in the bag. What is the probability that this colour is red?

Note: It might be useful to familiarize yourself with the notation of binomial coefficients before attempting this problem.

1. Suppose there are $r$ red marbles and $b$ blue marbles. As in the original problem, the marbles are chosen at random and removed from the bag one at a time until all marbles are removed. One colour of marble is the first to have $0$ marbles remaining in the bag. What is the probability that this colour is red?

2. Suppose there are $r$ red marbles, $b$ blue marbles, and $g$ green marbles. The marbles are chosen at random and removed one at a time until all marbles are removed. What is the probability that red is the colour of marble that is first to be completely removed from the bag?

3. Suppose there are $r$ red marbles, $b$ blue marbles, and $g$ green marbles with $r<b<g$. Let $p(r)$ be the probability that the red marbles are the first to be completely removed from the bag and define $p(b)$ and $p(g)$ similarly. Determine which of $p(r)$, $p(b)$, and $p(g)$ is the smallest and which is the largest. Does the result agree with your intuition?

4. Show that the values of $p(r)$, $p(b)$, and $p(g)$ depend only on the proportions of $r$, $b$, and $g$ to the total number of marbles. For example, if one bag has $r$ red, $b$ blue, and $g$ green marbles and another has $7r$ red, $7b$ blue, and $7g$ green marbles, then the probability that the red are removed first is the same for both bags.

Problem 4: January 2023

For each positive integer $k$, define a function $p_k(n)=1^k+2^k+3^k+\cdots +n^k$ for each integer $n$. That is, $p_k(n)$ is the sum of the first $n$ perfect $k$^th powers. It is well known that $p_1(n)={\displaystyle \frac{n(n+1)}{2}}$.

1. Fix a positive integer $n$. Let $S$ be the set of ordered triples $(a,b,c)$ of integers between $1$ and $n+1$, inclusive, that also satisfy $a<c$ and $b<c$. Show that there are exactly $p_2(n)$ elements in the set $S$.

2. With $S$ as in part (a), show that there are ${\displaystyle (\genfrac{}{}{0ex}{}{n+1}{2})}+2{\displaystyle (\genfrac{}{}{0ex}{}{n+1}{3})}$ elements in $S$ and use this to show that $$p_2(n)={\displaystyle \frac{n(n+1)(2n+1)}{6}}$$

3. For each $k$, show that there are constants $a_2,a_3,\dots ,a_k,a_{k+1}$ such that $$p_k(n)=a_2(\genfrac{}{}{0ex}{}{n+1}{2})+a_3(\genfrac{}{}{0ex}{}{n+1}{3})+\cdots +a_k(\genfrac{}{}{0ex}{}{n+1}{k})+a_{k+1}(\genfrac{}{}{0ex}{}{n+1}{k+1})$$ for all $n$.

   Note: Actually computing the constants gets more and more difficult as $k$ gets larger. While you might want to compute them for some small $k$, in this problem we only intend that you argue that the constants always exist, not that you deduce exactly what they are.

4. Use part (c) to show that $p_3(n)={\displaystyle \frac{n^2(n+1{)}^2}{4}}$ and $p_4(n)={\displaystyle \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}}$.

5. It follows from the fact in part (c) that $p_k(n)$ is a polynomial of degree $k+1$. With $k=5$, this means there are constants $c_0,c_1,c_2,c_3,c_4,c_5,$ and $c_6$ such that $$p_5(n)=c_0+c_{1}n+c_2{n}^2+c_3{n}^3+c_4{n}^4+c_5{n}^5+c_6{n}^6$$ Use the fact that $p_5(1)=1$ and $p_5(n)-p_5(n-1)=n^5$ for all $n\ge 2$ to determine $c_0$ through $c_6$, and hence, derive a formula for $p_5(n)$.

6. Show that $n(n+1)$ is a factor of $p_k(n)$ for every positive integer $k$ and that $2n+1$ is a factor of $p_k(n)$ for every even positive integer $k$.

Problem 5: February 2023

The sequence $(1,3,5,2,1,2,1)$ has the property that every integer in the sequence is a divisor of the sum of the integers adjacent to it. That is, $1$ is a divisor of $3$, $3$ is a divisor of $1+5=6$, $5$ is a divisor of $3+2=5$, and so on.

For $n\ge 3$, the sequence $(a_1,a_2,a_3,\dots ,a_n)$ of positive integers is called a splendid sequence of length $n$ if it satisfies conditions S1, S2, and S3 found below.

• S1. $a_1$ is a divisor of $a_2$ and $a_n$ is a divisor of $a_{n-1}$.

• S2. $a_i$ is a divisor of $a_{i-1}+a_{i+1}$ for each $i$ from $2$ through $n-1$ inclusive.

• S3. There is no prime number that is a divisor of every integer in the sequence.

For example, $(1,3,5,2,1,2,1)$ is a splendid sequence because it satisfies S1, S2, and S3. The sequence $(2,4,6,2)$ satisfies S1 and S2, but it is not a splendid sequence because it fails S3 since $2$ is a divisor of every integer in the sequence.

For $n=2$, $(a_1,a_2)$ is a splendid sequence of length $2$ if it satisfies S1 and S3. Mostly for notational convenience, we also define a splendid sequence of length $1$ to be the "sequence" $(1)$. That is, the only splendid sequence of length $1$ consists of a single integer equal to $1$.

1. Show that there is only one splendid sequence of length $2$.

2. Show that there is at least one splendid sequence of every possible length $n\ge 1$.

3. Suppose $(a_1,a_2,a_3,\dots ,a_n)$ is a splendid sequence of length $n\ge 2$. Show that for every integer $i$ with $1\le i\le n-1$ there is a positive integer $c$ so that $(a_1,a_2,\dots ,a_i,c,a_{i+1},\dots ,a_n)$ is a splendid sequence of length $n+1$.

4. Suppose $(a_1,a_2,a_3,\dots ,a_n)$ is a splendid sequence of length $n$. Show that $a_1=a_n=1$.

5. For each $n\ge 1$, show that there are only finitely many splendid sequences of length $n$.

6. Find a closed form for the number of splendid sequences of length $n$. Your answer should be an expression in terms of $n$.

Note: In part (f), we are asking you to find a closed form for the number of splendid sequences, the existence of which immediately implies that there are only finitely many. Hence, one way to answer part (e) is to answer part (f). With that said, we decided to include part (e) because it can be done without part (f) and (at least as far as we can tell) it is quite a bit easier than part (f). Part (f) is very challenging, so the hint will have more detail than usual.

Problem 6: March 2023

For a non-negative integer $n$, define $f(n)$ to be the first digit after the decimal point in the decimal expansion of $\sqrt{n}$. For example, $\sqrt{10}=3.162277\dots$ and so $f(10)=1$. Note that $f(0)=0$ and that $f(n)=0$ when $n$ is a perfect square. You will likely want a calculator that can compute square roots for this question.

1. Compute $f(n)$ for every integer $n$ strictly between $1$ and $4$ as well as every integer $n$ strictly between $36$ and $49$.

2. Compute $f(n)$ for every integer $n$ strictly between $4$ and $9$ as well as every integer $n$ strictly between $49$ and $64$.

3. Show that if $n$ is a positive multiple of $5$, then each digit from $0$ through $9$ appears in the list $$f(n^2+1),f(n^2+2),f(n^2+3),\dots ,f(n^2+2n-1),f(n^2+2n)$$ the same number of times.

4. For each digit $d$ from $0$ through $9$, determine how many times $d$ occurs in the list $$f(1),f(2),f(3),\dots ,f({10}^4)$$

5. Here are a couple of other things that you might like to think about. No solution will be provided for either of these questions, but as always, we would love to hear about any observations you make!

   • How are the digits $0$ through $9$ distributed among the infinite list $$f(1),f(2),f(3),f(4),\dots$$ For example, in the long run, are the ten digits distributed roughly "uniformly"? One way to make sense of this question is to think about the frequency of each digit among the list $f(1),f(2),f(3),\dots ,f(n)$ for very large $n$.

   • Are there similar patterns to those in the earlier parts of this problem if we consider the first two digits after the decimal place? What if we consider three or more digits?

Problem 7: April 2023

Let $A_n$ denote the set of all $n$-tuples of $0$s and $1$s. For example, $A_2$ is the set of all ordered pairs of $0$s and $1$s or $A_2=\{(0,0),(0,1),(1,0),(1,1)\}$. To improve readability, we will omit the commas and parentheses from the elements of $A_n$. For example, the elements of $A_3$ will be denoted by $000$, $001$, $010$, $011$, $100$, $101$, $110$, and $111$.

Variables referring to elements of $A_n$ will be bold lowercase letters. For example, we might refer to elements in $A_2$ as $\mathit{a}$, or $\mathit{b}$, and so on. To refer to the coordinates of elements in $A_n$, we will use square brackets. For example, if $\mathit{a}=11010$, an element in $A_5$, then $\mathit{a}[1]=1$, $\mathit{a}[2]=1$, $\mathit{a}[3]=0$, $\mathit{a}[4]=1$, and $\mathit{a}[5]=0$.

For two elements $\mathit{a}$ and $\mathit{b}$ in $A_n$, the Hamming distance, denoted $d(\mathit{a},\mathit{b})$ between $\mathit{a}$ and $\mathit{b}$ is equal to the number of coordinates where they differ. For example, if $\mathit{a}=11010$ and $\mathit{b}=01110$, then $d(\mathit{a},\mathit{b})=2$ because $\mathit{a}[1]\ne \mathit{b}[1]$ and $\mathit{a}[3]\ne \mathit{b}[3]$, but $\mathit{a}[i]=\mathit{b}[i]$ for $i=2$, $i=4$, and $i=5$. It is important to convince yourself that $d(\mathit{a},\mathit{b})=d(\mathit{b},\mathit{a})$ for any $\mathit{a}$ and $\mathit{b}$.

The notion of a graph was defined in the extra information about the February 2023 problem, but there are also plenty of places online that have definitions. We will keep things simple here and define a graph to be a collection of vertices, some of which are connected to each other by edges. When we draw a graph, a vertex will be represented by a circle and an edge will be represented by a line segment from one vertex to another. Two examples of graphs are depicted below. The one on the left has four vertices and the one on the right has eight. Note that two edges intersecting does not necessarily imply the presence of a vertex.

For each $n$, we define a graph with $2^n$ vertices called the natural graph of $A_n$. In the natural graph of $A^n$, it is possible to label every vertex by exactly one element of $A_n$ such that there is an edge between two vertices exactly when their Hamming distance is $1$. The two examples above are the natural graphs of $A_2$ and $A_3$. They are shown again below with their vertices labelled.

A walk in a graph from vertex $v$ to vertex $w$ is a sequence of vertices starting at $v$ and ending at $w$ with the property that there is an edge connecting every pair of consecutive vertices in the sequence. The length of a walk is the number of edges it uses. For example, let $v$, $w$, $x$, and $y$ be the vertices labelled by $000$, $110$, $100$, and $010$ in the natural graph of $A_3$, respectively. Then $v,x,w$ and $v,y,w$ are walks of length $2$ from $v$ to $w$. The distance between $v$ and $w$ in a graph is equal to the shortest possible length of a walk from $v$ to $w$. In the example above, $v$ and $w$ have a distance of $2$ because there are walks of length $2$, but there are no shorter walks from $v$ to $w$.

1. Let $\mathit{a}$ and $\mathit{b}$ be elements of $A_n$. Show that $d(\mathit{a},\mathit{b})$ is equal to the distance between $\mathit{a}$ and $\mathit{b}$ in the natural graph of $A_n$.

2. For each $k$ with $1\le k\le n$, determine the number of two-element subsets $\{\mathit{a},\mathit{b}\}$ of $A_n$ that satisfy $d(\mathit{a},\mathit{b})=k$.

3. Suppose we were to relabel the vertices of the natural graph of $A_n$ by permuting the labels. That is, we keep the graph the same but use the elements of $A_n$ to label a vertex of the graph in some other way. For example, in $A_2$, we might leave $00$ and $10$ where they are and swap the positions of $01$ and $11$, as shown.

   

   When this is done, the distance in the new graph between elements of $\mathit{a}$ and $\mathit{b}$ is not necessarily equal to $d(\mathit{a},\mathit{b})$ any more. The table below has the two-element subsets of $A_2$ in the first column, $d(\mathit{a},\mathit{b})$ in the second column, and their distance in the relabelled graph in the third column.

   $\{\mathit{a},\mathit{b}\}$	$d(\mathit{a},\mathit{b})$	new distance
   $\{00,01\}$	$1$	$2$
   $\{00,10\}$	$1$	$1$
   $\{00,11\}$	$2$	$1$
   $\{01,10\}$	$2$	$1$
   $\{01,11\}$	$1$	$1$
   $\{10,11\}$	$1$	$2$

   Among the four subsets $\{\mathit{a},\mathit{b}\}$ with $d(\mathit{a},\mathit{b})=1$, there are two that have a distance in the relabelled graph of $1$ and two that have a distance in the relabelled graph of $2$.

   Now for the question: For each $n$, find a way to permute the elements of $A_n$ so that the following happens: Among all two-element subsets $\{\mathit{a},\mathit{b}\}$ of $A_n$ with $d(\mathit{a},\mathit{b})=1$, there are the same number with each possible distance in the relabelled graph.

Problem 8: May 2023

This month’s problem is based on Problem 6 part (b) of the 2023 Euclid Contest. Here is a modified and rephrased version of that problem:

A square is drawn in the plane with vertices at $(0,0),(1,0),(1,1)$, and $(0,1)$. Two blue lines are drawn with slope 3, one passing through $(0,0)$ and the other through $(\frac{1}{3},0)$. Two red lines are drawn with slope $-\frac{1}{3}$, one passing through $(0,1)$ and the other through $(0,\frac{2}{3})$. What is the area of the square bounded by the red and blue lines?

The answer to this question is $\frac{1}{10}$. We suggest convincing yourself of this before attempting the rest of the problem. The fact that this small square has an area exactly one tenth of the larger square suggests that there is a way to answer this question by showing that exactly $10$ squares the size of the small one should fit into the large square. Let’s explore!

Here is some terminology that we will use in this problem.

Definition: A lattice point is a point $(x,y)$ for which $x$ and $y$ are both integers.

Definition: A $1\times 1$ square whose vertices are at lattice points is called a unit lattice square. We will denote by $T$ the unit lattice square with vertices $(0,0)$, $(1,0)$, $(1,1)$, and $(0,1)$.

Definition: $L_{q,p}$ denotes the line segment connecting $(0,0)$ to the point $(q,p)$. Note that this line has slope $\frac{p}{q}$.

Definition: An $m$ – lattice line is a line with slope $m$ that passes through at least one lattice point.

The next two definitions are more complicated. There are examples given after they are stated.

Definition: The tricky unit square, $\mathbb{T}$, is a modified version of $T$ (see above) with the property that if a line reaches an edge of $\mathbb{T}$, it "jumps" to the opposite side and continues with the same slope. For example, if a line reaches the top edge of $\mathbb{T}$, it continues with the same slope from the bottom edge directly below where it reached the top edge. If a line reaches a vertex of $\mathbb{T}$, then it has simultaneously reached two edges. In this situation, it continues with the same slope from the opposite vertex of $\mathbb{T}$.

Definition: Let $\frac{p}{q}$ be a rational number written in lowest terms. The $\frac{p}{q}$ – loop on $\mathbb{T}$ is the line passing through $(0,0)$ with slope $\frac{p}{q}$.

Below are diagrams, from left to right, of the $\frac{1}{2}$ – loop, the $\frac{-2}{1}$ – loop, and the $\frac{2}{5}$ – loop on $\mathbb{T}$. In each diagram, equal letters mark places where the line jumps from one side of the square to the opposite side.

Each of the loops above eventually come back to their starting point and repeat. This happens because $\frac{p}{q}$ is rational (think about this!). Notice that in the image of the $\frac{-2}{1}$ – loop (the middle image), the loop starts at $(0,1)$ instead of $(0,0)$. This is because a line of negative slope starting at $(0,0)$ (on the bottom edge) immediately jumps to the top edge and continues from $(0,1)$. It is worth thinking about how all four vertices of $\mathbb{T}$ really represent the same point.

Below is an image of $\mathbb{T}$ with the $\frac{3}{1}$ – loop in blue and the $\frac{-1}{3}$ – loop in red. These two loops divide $\mathbb{T}$ into $10$ smaller squares. The squares numbered $1$, $2$, $3$, $4$, $5$, and $6$ are split in two pieces each across edges of $\mathbb{T}$. Notice that both the loops pass thorough the point $(0,0)$ since the four vertices of the square are the same point. This means, if we count the four vertices as one intersection point, the two loops intersect exactly $10$ times (count them!). Think about how this compares to the Euclid problem mentioned earlier.

1. For each pair of loops below, draw $\mathbb{T}$ with that pair of loops, count the number of times the loops intersect, and count the number of squares into which the loops divide $\mathbb{T}$.

   1. The $\frac{4}{1}$ – loop and the $\frac{-1}{4}$ – loop.

   2. The $\frac{2}{3}$ – loop and the $\frac{-3}{2}$ – loop.

   3. The $\frac{4}{3}$ – loop and the $\frac{-3}{4}$ – loop.

   4. The $\frac{1}{1}$ – loop and the $\frac{-1}{1}$ – loop.

In the remaining problems, $p$ and $q$ are positive integers that have no positive divisors in common other than $1$.

2. How many line segments make up the $\frac{p}{q}$ – loop?

3. How many $\frac{p}{q}$ – lattice lines intersect $T$?

4. Explain why the number of points of intersection of the $\frac{p}{q}$ – loop and the $-\frac{q}{p}$ – loop on $\mathbb{T}$ is equal to the number of small squares into which the loops divide $\mathbb{T}$. Remember that the four vertices of $\mathbb{T}$ represent the same point.

5. How many $-\frac{q}{p}$ – lattice lines intersect $L_{q,p}$?

6. Compute the area of the small squares in $\mathbb{T}$ created by the $\frac{p}{q}$ – loop and the $-\frac{q}{p}$ – loop. Our solution will take for granted that these small squares all have the same area, but you might like to think about how to prove this.