Problem of the Month 2023-2024

Problem 0: September 2023

In this problem, $f$ will always be a function defined by $f(r)={\displaystyle \frac{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\ge 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)={\displaystyle \frac{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)={\displaystyle \frac{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\ge 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)={\displaystyle \frac{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|{\displaystyle \frac{1-\sqrt{2}}{r+1}}\right|$$

   3. Suppose $r_1$ is a positive rational number. Prove that $|r_n-\sqrt{2}|<{\displaystyle \frac{1}{2^{n-1}}}|r_1-\sqrt{2}|$ for each $n\ge 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)={\displaystyle \frac{r-3}{r-2}},f(r)={\displaystyle \frac{r-1}{5r+3}},f(r)={\displaystyle \frac{r-1}{r+2}},f(r)={\displaystyle \frac{2r+2}{3r+3}},f(r)=\frac{r+1}{r-2}$$

Problem 1: October 2023

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.

Problem 2: November 2023

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 ${\displaystyle \frac{x^2}{a^2}}+{\displaystyle \frac{y^2}{b^2}}=1$ where $a$ and $b$ are fixed positive real numbers

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

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

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

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

Problem 3: December 2023

This month’s problem is an extension of Problem 3 from Part B of the 2023 Canadian Intermediate Mathematics Contest. The original problem was stated as follows:

The positive integers are written into rows so that Row $n$ includes every integer $m$ with the following properties:

1. $m$ is a multiple of $n$,

2. $m\le n^2$, and

3. $m$ is not in an earlier row.

The table below shows the first six rows.

Row 1	1
Row 2	2, 4
Row 3	3, 6, 9
Row 4	8, 12, 16
Row 5	5, 10, 15, 20, 25
Row 6	18, 24, 30, 36

1. Determine the smallest integer in Row $10.$

2. Show that, for all positive integers $n\ge 3$, Row $n$ includes each of $n^2-n$ and $n^2-2n.$

3. Determine the largest positive integer $n$ with the property that Row $n$ does not include $n^2-10n.$

If you have not already done so, we suggest thinking about the parts above before proceeding.

1. For each positive integer $k$, determine the largest positive integer $n$ with the property that Row $n$ does not include $n^2-kn$. (This generalizes part (c) from the original problem.)

In the remaining questions, $f(n)$ is defined for each $n\ge 1$ to be the largest non-negative integer $m$ such that $m\le n$ and $mn$ is not in Row $n$. For example, Row $6$ is $18,24,30,36$, so $f(6)=2$ since $2\times 6=12$ is not in Row $6$ but $3\times 6$, $4\times 6$, $5\times 6$, and $6\times 6$ are all in Row $6$.

2. Show that $f(p)=0$ for all prime numbers $p$. (Looking closely at the definition of $f(n)$, $f(p)=0$ means that every positive multiple of $p$ from $p$ through $p^2$ appears in Row $p$.)

3. Find an expression for $f(pq)$ where $p$ and $q$ are prime numbers. Justify that the expression is correct.

4. Find an expression for $f(p^d)$ where $p$ is a prime number and $d$ is a positive integer.

5. Take some time to explore the function $f$ further on your own. Are there other results you can prove about the function beyond what is done in (b), (c) and (d)? Is there a nice way to compute $f(n)$ in general without computing each of the first $n-1$ rows?

Problem 4: January 2024

In this problem, we will enclose a list of positive integers in square brackets. For example, $[1,2,4,7,9]$ is a list of positive integers of length five. All lists in this problem will be expressed in non-decreasing order. To denote the list of consecutive integers from $a$ to $b$ inclusive, we will use the notation $[a:b]$. For example, $[4:7]$ denotes the list $[4,5,6,7]$.

Given a list, $A$, of positive integers, we will define $f(A)$ to be the increasing list of distinct positive integers that are expressible as the sum of some, but not all, of the items in $A$. A sum is allowed to consist of just one item in $A$, and each item in $A$ can be used at most once in a particular sum.

For example, if $A=[1,1,3,7]$, then the sums of at least one but not all of the items in $A$ are shown below. $$\begin{array}{rl}1& =1\\ 1& =1\\ 3& =3\\ 7& =7\end{array}$$ $$\begin{array}{rl}1+1& =2\\ 1+3& =4\\ 1+7& =8\\ 1+3& =4\\ 1+7& =8\\ 3+7& =10\end{array}$$ $$\begin{array}{rl}1+1+3& =5\\ 1+1+7& =9\\ 1+3+7& =11\\ 1+3+7& =11\end{array}$$ Therefore, $f(A)=[1,2,3,4,5,7,8,9,10,11]$.

A list, $D$, of positive integers is called compressible if there exists some list $A$ with $f(A)=D$. In this situation, we say that $D$ is compressed by $A$ or that $A$ compresses $D$. From the example above, we have that $[1,2,3,4,5,7,8,9,10,11]$ is compressible and is compressed by $[1,1,3,7]$.

1. Find all lists of length four that compress $[1:9]$ and explain why no list of length three or less can compress $[1:9]$.

2. Find a list, $A$, that compresses $[1:100]$ and is as short as possible.

3. Show that for all positive integers $n$, the list $[1:n]$ is compressible. For each $n$, determine the smallest possible length of a list that compresses $[1:n]$.

4. Show that for all positive integers $k\ge 3$ there are only finitely many compressible lists of $k$ consecutive positive integers. That is, for each positive integer $k\ge 3$, show that there are only finitely many positive integers $m$ for which $[m:m+k-1]$ is compressible.

5. Find the largest positive integer $k$ such that $[5:k]$ is not compressible. (A full solution will not be provided for this part.)

Problem 5: February 2024

Introduction

This problem explores a counting technique that uses binomial coefficients. The main problems for this month are in the next section. For anyone who is not already familiar with the notation of binomial coefficients, this section includes an introduction with a few standard exercises.

For non-negative integers $n$ and $k$, the expression ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ denotes the number of ways to choose $k$ objects from $n$ distinct objects. For this reason, the quantity ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ is pronounced "$n$ choose $k$".

For example, consider the four letters $A$, $B$, $C$, and $D$. There are $4$ ways to select three of them. They are as follows:

• $A$, $B$, $C$
• $A$, $B$, $D$
• $A$, $C$, $D$
• $B$, $C$, $D$

Since there are $4$ ways to choose $3$ of the objects (order does not matter – it only matters which objects are chosen), we have that ${\displaystyle (\genfrac{}{}{0ex}{}{4}{3})}=4$.

Try the following exercises. Hints will be provided, but solutions will not. These exercises are intended as a way to get familiar with the notation, so they may not be explicitly useful in the main problems.

1. Show that ${\displaystyle (\genfrac{}{}{0ex}{}{5}{2})}=10$.

2. What are ${\displaystyle (\genfrac{}{}{0ex}{}{n}{0})}$ and ${\displaystyle (\genfrac{}{}{0ex}{}{n}{1})}$?

3. Convince yourself that ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}={\displaystyle (\genfrac{}{}{0ex}{}{n}{n-k})}$ for $0\le k\le n$.

4. Convince yourself that ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}+{\displaystyle (\genfrac{}{}{0ex}{}{n}{k+1})}={\displaystyle (\genfrac{}{}{0ex}{}{n+1}{k+1})}$ when $0\le k<n$.

5. Convince yourself that ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ is equal to the coefficient of $x^k$ in the expanded form of $(1+x{)}^n$. This is why ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ is called a "binomial coefficient".

It turns out that there is a convenient way to compute binomial coefficients using factorial notation. If $n\ge k\ge 0$ are integers, then ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}={\displaystyle \frac{n!}{k!(n-k)!}}$. Here, $m!$, pronounced "$m$ factorial", is defined so that $m!=1$ when $m=0$ and $m=1$, and $m!=1\times 2\times 3\times \cdots \times (m-1)\times m$ for integers $m\ge 2$. It is also a useful exercise to think about why this formula for ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ works.

Main Problems

1. For a positive integer $n$, show that ${\displaystyle (\genfrac{}{}{0ex}{}{n+1}{2})}$ is the answer to each of these three questions. Think about why the answers to all three questions are the same.

   1. What is $1+2+3+\cdots +n$?

   2. How many pairs $(x,y)$ of non-negative integers satisfy $x+y\le n-1$?

   3. How many triples $(x,y,z)$ of non-negative integers satisfy $x+y+z=n-1$?

2. Let $n\ge 0$ and $r\ge 1$ be integers. Show that the following two questions have the same answer and express the common answer as a single binomial coefficient.

   1. How many ways are there to place $n$ indistinguishable balls in $r$ distinguishable cups?

   2. How many non-negative integer solutions are there to the equation $x_1+x_2+\cdots +x_r=n$?

3. Let $n\ge 0$ and $r\ge 1$ be integers. By counting $r$-tuples of non-negative integers $(x_1,x_2,\dots ,x_r)$ that satisfy $x_1+x_2+x_3+\cdots +x_r\le n$, prove the identity $${\displaystyle (\genfrac{}{}{0ex}{}{r-1}{r-1})}+{\displaystyle (\genfrac{}{}{0ex}{}{r}{r-1})}+{\displaystyle (\genfrac{}{}{0ex}{}{r+1}{r-1})}+{\displaystyle (\genfrac{}{}{0ex}{}{r+2}{r-1})}+\cdots +{\displaystyle (\genfrac{}{}{0ex}{}{r-1+n}{r-1})}={\displaystyle (\genfrac{}{}{0ex}{}{n+r}{r})}$$ Clarification: The quantity on the left in the equation above is the sum of the binomial coefficients ${\displaystyle (\genfrac{}{}{0ex}{}{r-1+m}{r-1})}$ where $m$ ranges from $0$ to $n$.

4. Determine the number of non-negative integers $x$ with $x<{10}^{10}$ that have a digit sum of $21$.

5. For a positive integer $x=a_n{a}_{n-1}{a}_{n-2}\cdots a_1{a}_0$ where the $a_i$ are the digits of $x$, the alternating sum of $x$ is the expression $a_0-a_1+a_2-a_3+\cdots +(-1{)}^n{a}_n$. For example, the alternating sum of $744923$ is $3-2+9-4+4-7=3$. Determine the number of non-negative integers with at most $8$ digits that have an alternating sum equal to $0$.

6. How many ways are there to choose integers $a$, $b$, and $c$ such that $1\le a<b<c\le 2024$ and $a+b+c=2027$?

Problem 6: March 2024

This month’s problem is an introduction to some of the basic ideas that come up when studying polynomials. It is presented with many exercises interspersed among some definitions. Some of the exercises are computational and some are theoretical.

Complex Numbers: The polynomial $x^2+1$ does not have any real roots. Because of this, we "invent" a root, and it is traditionally called $i$ for "imaginary". That is, we declare that $i$ is a number such that $i^2+1=0$ or $i^2=-1$. From a desire to do arithmetic with numbers "like" $i$, we declare that a complex number is a number of the form $a+bi$ where $a$ and $b$ are real numbers. For example, $1+i$ and $-3+2i$ are complex numbers. Remembering that $i^2=-1$ and using expected arithmetic rules, we can add and multiply complex numbers. For example, $$\begin{array}{rl}(1+i)+(-3+2i)& =1+i-3+2i=-2+3i\\ (1+i)(-3+2i)& =(1)(-3)+(1)(2i)+(i)(-3)+(i)(2i)\\ & =-3+2i-3i+2i^2\\ & =-3+2i-3i+2(-1)\\ & =-5-i\end{array}$$ Using the quadratic formula, complex numbers give roots to all real quadratics. For example, the quadratic $f(x)=x^2-4x+13$ has a discriminant of $(-4{)}^2-4(13)=-36$, and so it has no real roots. However, if we accept that $\sqrt{-36}$ means "a number that squares to $-36$", we can infer that $6i$ or $-6i$ could reasonably be considered as $\sqrt{-36}$. Indeed, using the quadratic formula, we get $${\displaystyle \frac{4\pm \sqrt{-36}}{2}}={\displaystyle \frac{4\pm 6i}{2}}=2\pm 3i$$ If you are new to complex numbers, or you just want to have some fun, you might want to check that $f(2+3i)=0$ and $f(2-3i)=0$ using the methods for adding and multiplying complex numbers demonstrated above.

For the next three exercises, it will be useful to remember that if $r$ is a root of a polynomial $p(x)$, then $x-r$ is a factor of $p(x)$.

1. Find all roots of the polynomial $f(x)=x^4-2x^3-2x^2+8$.

2. Find all roots of the polynomial $g(x)=x^4+2x^2+1$.

3. Find all roots of the polynomial $h(x)=x^4-4$.

Definition: A polynomial $p(x)$ is called a rational polynomial if all of its coefficients are rational numbers. The set of rational polynomials is denoted by $\mathbb{Q}[x]$.

Definition: Suppose $p(x)\in \mathbb{Q}[x]$ has degree at least $1$. We say that $p(x)$ is reducible in $\mathbb{Q}[x]$ (or reducible over $\mathbb{Q}$) if there are rational polynomials $u(x)$ and $v(x)$, both of degree at least $1$, such that $p(x)=u(x)v(x)$. We say that $p(x)$ is irreducible over $\mathbb{Q}$ if it is not reducible over $\mathbb{Q}$. In other words, $p(x)$ is irreducible over $\mathbb{Q}$ if it cannot be factored as a product of rational polynomials of degree lower than that of $p(x)$.

4. Determine whether each given polynomial is reducible or irreducible over $\mathbb{Q}$.

   1. $x^2-2$

   2. $x^3-6x^2+11x-6$

   3. $x^3+x+1$

   4. $2x-5$

   5. $x^4+3x^2+2$

   6. $x^4+1$

Definition: A complex number $\alpha$ is called algebraic if it is a root of some non-constant rational polynomial. That is, $\alpha$ is algebraic if there is a polynomial $p(x)\in \mathbb{Q}[x]$ of degree at least $1$ such that $p(\alpha )=0$. The degree of the algebraic number $\alpha$ is the smallest positive integer $d$ such that there is a rational polynomial $p(x)$ of degree $d$ with $p(\alpha )=0$. [The word "positive" is important because every number $\alpha$ is a root of the constant $0$ polynomial.]

5. Show that $\sqrt{2}$, $1+\sqrt[3]{2}$, $1+2i$, and $\sqrt{2}+\sqrt{3}$ are all algebraic numbers and find their degrees. It might be easier to find the degrees after thinking about some of the later questions.

6. Suppose $\alpha$ is an algebraic number of degree $d$. Prove that there is a unique irreducible polynomial $m(x)$ of degree $d$ with leading coefficient equal to $1$ such that $m(\alpha )=0$.

Note: Numbers that are not algebraic are called transcendental numbers. Two famous examples of transcendental numbers are $\pi$ and $e$.

Definition: If $f(x)$ is a polynomial and $\alpha$ is a root of $f(x)$, then $\alpha$ is a repeated root of $f(x)$ if there is a polynomial $g(x)$ such that $f(x)=g(x)(x-\alpha {)}^2$. Note that $\alpha$ might be a complex number, which means $g(x)$ could have complex coefficients.

7. Let $f(x)=x^7-3x^6+2x^5-2x^4+x^3+5x^2+4$. Find complex numbers $r_1,r_2,\dots ,r_7$ such that $f(x)=(x-r_1)(x-r_2)\cdots (x-r_7)$. In other words, find all roots of $f(x)$.
   Hint: Some of the roots are small integers and every root corresponds a linear factor.

8. Given a polynomial $f(x)$ of degree $n$, if we expand the expression $f(x+y)$ (here, $y$ is another variable), we can write $f(x+y)$ as $$f(x+y)=f_0(x)+y{f}_1(x)+y^2{f}_2(x)+\cdots +y^n{f}_n(x)$$ for unique polynomials $f_0(x),f_1(x),\dots ,f_n(x)$.

   1. For the polynomial $f(x)$ from part (g), determine the polynomials $f_0(x)$ and $f_1(x)$ described above and find all roots of $f_0(x)$ and $f_1(x)$.

   2. Suppose that $f(x)$ is a polynomial and that $r$ is a root of $f(x)$. Prove that $r$ is a repeated root of $f(x)$ if and only if $r$ is a root of $f_1(x)$.

10. Prove that if $p(x)$ and $q(x)$ are irreducible rational polynomials with a root in common, then there is a rational number $c$ such that $p(x)=cq(x)$.

11. Prove that an irreducible rational polynomial cannot have a repeated root.

Note: The division algorithm for polynomials might be useful in some of the later problems. It will be explained briefly in the hint.

Problem 7: April 2024

Curves in the plane are often given as the set of points $(x,y)$ that satisfy some equation in $x$ and $y$. For example, the set of points $(x,y)$ that satisfy $y=x^2$ is a parabola, the set of points $(x,y)$ that satisfy $y=3x+4$ is a line, and the set of points $(x,y)$ that satisfy $x^2+y^2=1$ is the circle of radius $1$ centred at the origin.

Another way to express a curve in the plane is using parametric equations. With this type of description, we introduce a third variable, $t$, called the parameter, and each of $x$ and $y$ is given as a function of $t$. This is useful for describing the position of a point that is moving around the plane. For example, imagine that an ant is crawling around the plane. If its $x$-coordinate at time $t$ is $x=x(t)$ and its $y$-coordinate at time $t$ is $y(t)$, then its position at time $t$ is $(x(t),y(t))$.

1. A particle’s position at time $t$ is $(x,y)=(1+t,-2+2t)$. That is, its $x$-coordinate at time $t$ is $1+t$ and its $y$-coordinate at time $t$ is $-2+2t$.

   1. Plot the position of the particle at $t=0$, $1$, $2$, $3$, and $4$.

   2. Show that every position the particle occupies is on the line with equation $y=2x-4$.

   3. Sketch the path of the particle from $t=0$ through $t=4$.

2. A particle’s position at time $t$ is $(\cos (t),\sin (t))$. Sketch the path of the particle from $t=0$ through $t=2\pi$.

3. A particle’s position at time $t$ is $(\cos (t),\sin (2t))$.

   1. Plot the position of the particle at $t={\displaystyle \frac{k\pi }{12}}$ for the integers $k=0$ through $k=24$. Sketch the path of the particle from $t=0$ through $t=2\pi$.

   2. Show that every position the particle occupies is on the curve with equation $y^2=4x^2-4x^4$.

4. Circle 1 is centred at the origin, Circle 2 is centred at $(2,0)$, and both circles have radius $1$. The circles are tangent at $(1,0)$. Circle 2 is "rolled" in the counterclockwise direction along the outside of the circumference of Circle 1 without slipping. The point on Circle 2 that was originally at $(1,0)$ (the point of tangency) follows a curve in the plane. Find functions $x(t)$ and $y(t)$ so that the points on this curve are $(x(t),y(t))$ for $0\le t\le 2\pi$.

   

5. The setup in this problem is similar to (d). Circle 1 is centred at the origin and has radius $2$ and Circle 2 is centred at $(1,0)$ and has radius $1$ so that the two circles are tangent at $(2,0)$. Circle 2 is rolled around the inside of the circumference of Circle 1 in the counterclockwise direction. Describe the curve in the plane followed by the point on Circle 2 that is initially at $(2,0)$.

   

6. Circle 1 is centred at the origin and has radius $1$. Circle 2 has radius $r<1$, is inside Circle 1, and the two circles are initially tangent at $(1,0)$. When Circle 2 is rolled around the inside of Circle 1 in the counterclockwise direction, the point on Circle 2 that was initially at $(1,0)$ will follow some curve in the plane.

   1. Show that when $r={\displaystyle \frac{1}{4}}$, the points on the curve satisfy the equation $(\sqrt[3]{x}{)}^2+(\sqrt[3]{y}{)}^2=1$.

   2. Show that the curves for $r={\displaystyle \frac{1}{3}}$ and $r={\displaystyle \frac{2}{3}}$ are exactly the same and that the point initially at $(1,0)$ travels this curve in opposite directions for the two radii.

   

Problem 8: May 2024

This month’s problem is an extension of Question 4 from the 2024 Galois Contest. It is not necessary to try the problem before attempting the questions below.

In an $m\times n$ rectangular grid, we say that two cells are neighbours if they share an edge. The neighbourhood of a cell is the cell itself along with its neighbours.

An $m\times n$ grid is called a Griffin Grid if each of its $mn$ cells contains either a $1$ or a $-1$ and the integer in every cell is equal to the product of the other integers in its neighbourhood.

For example, the $4\times 9$ grid below is a Griffin Grid. The three shaded regions are the neighbourhoods of the cells in Row 1 and Column 1, Row 1 and Column 8, and Row 4 and Column 4.

The Galois problem restricted this definition to $m=3$. Here we want to explore what happens more generally. If a question is marked with an asterisk $(\ast )$, it means I was unable to solve it. Solutions will not be provided for these problems, but I would love to hear if you solve one!

1. Show that an $m\times n$ grid with $-1$ or $1$ in every cell is a Griffin Grid if and only if the cells in every neighbourhood have a product of $1$.

2. For every $n$, determine the number of $2\times n$, $3\times n$, and $4\times n$ Griffin Grids. Determining the number of $3\times n$ Griffin Grids in general is essentially what is required to answer part (c) of the Galois question.

3. Show that the number of $m\times n$ Griffin Grids is of the form $2^k$ for some integer $k$ with $0\le k\le m$.

4. $\ast$ For general $m$, determine for which $k$ there exists $n$ with the property that the number of $m\times n$ Griffin Grids is exactly $2^k$.

5. Show that for all $m$ there exist infinitely many $n$ for which there is exactly one $m\times n$ Griffin Grid.

6. Show that for all $m$ there exist infinitely many $n$ for which there are $2^m$ distinct $m\times n$ Griffin Grids.

7. * Find a simple general way to calculate the number of $m\times n$ Griffin Grids.