Some friends are playing a game involving ten cards numbered \(1\) through \(10\). In part (a), Adina, Budi, and Dewei are the players. In parts (b) and (c), Adina, Budi, Charlie, and Dewei are the players. To play the game, each player other than Dewei chooses a card and shows it to all other players, but no player looks at their own card. The game consists of a dialogue with the goal being for all players holding a card to deduce the integer on their own card. In each part of this question, the dialogue is given in the order the statements/questions occurred. No player is allowed to ask a question to which they already know the answer.
Given the dialogue below, determine the integers on Adina’s and Budi’s cards.
(Adina) Is the integer on my card larger than the integer on Budi’s card?
(Dewei) No.
(Budi) I know the integer on my card.
(Adina) I know the integer on my card.
After the dialogue below, Adina, Budi, and Charlie each know the integer on their own card. Determine all possibilities for the integers on their cards.
(Adina) Is the sum of the integers on the cards a perfect square?
(Dewei) Yes.
Given the dialogue below, determine all possibilities for the integers on the cards.
(Adina) Are the integers on any of the cards prime?
(Dewei) No.
(Budi) Is the sum of the integers on the cards prime?
(Dewei) Yes.
The three statements below occur simultaneously.
(Adina) I do not know what integer is on my card.
(Budi) I do not know what integer is on my card.
(Charlie) I know what integer is on my card.
The two statements below occur simultaneously
(Adina) I still do not know what integer is on my card.
(Budi) I now know what integer is on my card.
(Adina) I now know what integer is on my card.
When we ordinarily write an integer, we write it in base-\(10\), using digits from the set \[\{0,1,2,3,4,5,6,7,8,9\}.\] For example, when we write \(743\) what we mean is \[743 = 7\times 10^2 + 4 \times 10^1 + 3 \times 10^0.\] However, there is nothing special about \(10\), and we can use other numbers as a base! Integers can also be written in base-\(2\), and we call this writing an integer in binary. When writing an integer in binary, we use powers of \(2\) instead of powers of \(10\), and we use the "digits" from the set \(\{0,1\}\) ("digits" is in scare quotes because binary digits are called bits). We are going to explore some problems related to writing numbers in binary.
How do we write a number, say \(121\), in binary? Well, it’s not that different to writing it in base-\(10\). First, find the largest power of \(2\) which is less than or equal to \(121\), which is \(2^6 = 64\). Subtracting this power gives us \(121-64 = 57\). Then we repeat with \(57\), and continue this way until we are left with only a power of \(2\). With \(121\) this process looks like this: \[\begin{aligned} 121 &= 2^6 + 57 \\ 57 &= 2^5 + 25 \\ 25 &= 2^4 + 9 \\ 9 &= 2^3 + 1 \\ 1 &= 2^0\end{aligned}\] Once we are done with this process, we conclude that \(121 = 2^6 + 2^5 + 2^4 + 2^3 + 2^0\). To be completely explicit, \[121 = 1\times 2^6 + 1 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0.\] More compactly, we write this as \(121 = [1111001]_2\).
This process works great for natural numbers, but it also works great for all real numbers! Typically, we write real numbers in base-\(10\). For example, \(\pi = 3.1415\ldots\) means \[\pi = 3\times 10^0 + 1 \times 10^{-1} + 4 \times 10^{-2} + 1 \times 10^{-3} + 5 \times 10^{-4} + \cdots.\] To write \(\pi\) in binary, we follow the procedure above: find the highest power of \(2\) less than or equal to \(\pi\), subtract it, and repeat. The first few steps look like this: \[\begin{aligned} \pi &= 2^1 + (\pi - 2) \\ \pi - 2 &= 2^0 + (\pi - 3) \\ \pi - 3 &= 2^{-3} + \left(\pi - \frac{25}{8}\right)\end{aligned}\] Therefore, \(\pi =1 \times 2^1 + 1 \times 2^0 + 0 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3} + \cdots\) or more succinctly, \(\pi = [11.001 \ldots]_2\) (take a moment and prove that these calculations are correct, that is, for example, that \(2^{-3}\) is indeed the largest power of \(2\) less than or equal to \(\pi-3\)).
Before we get started on the questions, here are a couple of important facts you can take for granted without proof.
Fact 1: The binary expansions \([0.a_1a_2\cdots a_k0\overline{1}]_2\) and \([0.a_1a_2\cdots a_k 1]_2\) represent the same number. This is due to the fact that \(\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \cdots = 1\). As a result, we never write a binary number ending in an infinite string of \(1\)’s. This is analogous to the fact that the decimal expansions \(0.\overline{9}\) and \(1\) are decimal expansions of the same number (that number being the number \(1\)).
Fact 2: With Fact 1 taken care of, every real number has a unique binary expansion.
Compute the binary expansion of \(279\).
Let \(k\) be a positive integer. Compute the binary expansion of \(2^k - 1\).
Let \(\sqrt 3 = [a_0.a_1a_2a_3a_4\ldots]_2\). Compute \(a_0,a_1,a_2,a_3,\) and \(a_4\).
In base-\(10\), \(\frac{1}{7} = 0.\overline{142857}\). In this question we will find the binary expansion of \(\frac{1}{7}\), which will also be repeating.
Find a pair of positive integers \(k\) and \(n\) so that \(2^k\cdot\frac{1}{7} = \frac{1}{7} + n\).
Let \(\frac{1}{7} = [0.a_1a_2a_3\ldots]_2\) (why is the only thing to the left of the decimal point a \(0\)?). Using your values for \(k\) and \(n\) from part (a), write down binary expansions of \(2^k\cdot\frac{1}{7}\) and \(\frac{1}{7} + n\) in terms of the \(a_i\).
Compute the binary expansion of \(\frac{1}{7}\). It should look like \([0.\overline{a_1a_2 \cdots a_t}]\) for some \(t\).
Compute the binary expansion of \(\frac{3}{11}\).
Let \(p\) be a prime. Prove that when \(\sqrt p\) is written in binary, there are infinitely many \(1\)’s and infinitely many \(0\)’s.
The floor of a real number \(x\) is denoted \(\lfloor x \rfloor\), and is the largest integer \(n\) so that \(n \leq x\). Prove that the sequence \[\lfloor{\sqrt 2} \rfloor,\lfloor{2\sqrt 2}\rfloor,\lfloor{3\sqrt 2}\rfloor,\lfloor{4\sqrt 2}\rfloor,\lfloor{5\sqrt 2}\rfloor\ldots\] contains infinitely many powers of \(2\).
A course for a robot is a finite set of places (denoted by circles or squares) with arrows labelled \(a\) and \(b\) between places, satisfying the following conditions:
For every place \(s\), there is exactly one arrow labelled \(a\) and one arrow labelled \(b\) which starts at \(s\).
There is exactly one place called the starting place, denoted by a square.
Some positive number of places are called finishing places, and they are denoted by being shaded. The starting place can be a finishing place.
The course is connected. That is, there is a way to get from the starting place to any other place by following (possibly several) arrows.
While there is exactly one arrow labelled \(a\) and one arrow labelled \(b\) starting at every place, there may be multiple arrows labelled \(a\) ending at a particular place, or none at all! Take a moment to check that the following three examples are indeed courses.
For a particular course, we can give a robot instructions as to how to move from place to place in the form of a string. A string is a finite sequence of \(a\)'s and \(b\)'s (for example, \(abaa\)).
For each string, the robot begins at the starting place, and follows the arrows in the order they appear in the string (reading from left to right), moving from place to place.
If the robot ends at a finishing place, then the string is accepted. Otherwise, the string is rejected. Notice that by Condition \(1\) in the definition of a course, the string completely determines which places the robot visits.
The set of accepted strings is the manual for that course. For example, the manual for Course 3 above is the set of all strings. Convince yourself that the manual for Course 1 is the set of strings with an odd number of \(b\)'s.
Decide which of the following strings belong to the manual for Course 2 from the first page: \(abb\), \(aab\), \(baaaa\), \(abba\).
Describe the manuals for the following courses:
Construct a course whose manual is the set of three strings \(\{a,ab,bbb\}\).
Construct a course whose manual is the set of all strings where the number of \(a\)'s in the string is a multiple of \(3\).
For this problem we need to introduce some language and notation.
The length of a string is the number of characters in the string. For example, \(aaba\) has length \(4\). The string of length \(0\) is called the empty string and we denote it by \(e\).
If \(x\) and \(y\) are strings, then \(xy\) is the concatenation of the two strings. The string \(x^n\) is \(x\) concatonated with itself \(n\) times. For example, if \(x = bab\), \(y = ba\), and \(z = aab\), then \(xy^3z = babbababaaab\). Define \(x^0\) to be the empty string \(e\).
A substring of a string \(x\) is a string consisting of consecutive letters from \(x\). For example, \(ab\), \(ba\), \(e\), and \(baba\) are all substrings of \(baba\). The string \(bba\) is not a substring of \(baba\).
Suppose a course has \(k\) places, and let \(w\) be a string in its manual of length at least \(k\). Show that there is a substring \(y\) of \(w\) with length at least \(1\) and at most \(k\) so that when it is deleted from \(w\), the remaining word is also in the manual.
Suppose a course has \(k\) places, and let \(w\) be a string in its manual of length at least \(k\). Show that you can write \(w = xyz\) with the property that \(y \neq e\), the length of \(y\) is at most \(k\), and for all natural numbers \(n\), \(xy^nz\) is also in the manual.
Prove that the manual for a course cannot be the set of all strings with length equal to a perfect square.
Prove that the manual for a course cannot be the set of all strings that are palindromes. (A palindrome is a string that is the same when written backwards. The strings \(abba\) and \(aaa\) are palindromes, but \(ba\) is not.)
This month’s problem is an extension of Question B3 from the 2024 Canadian Intermediate Mathematics Contest, which was run by the CEMC in November 2024. The question that appeared on the contest can be found at the end of this problem. As a warm up, try the problem yourself and pay attention to the differences between the contest problem and this Problem of the Month.
Given an increasing list of integers \(L = \{a_1,a_2,\ldots,a_k\}\), the 3-sign sum of the list \(L\), denoted \(\mu(L)\), is the sum of the integers in the list, in order, except that every third integer is subtracted instead of added. For example, if \(L = \{3,4,5,8,10,11,13\}\), then \(\mu(L) = 3 + 4 - 5 + 8 + 10 - 11 + 13 = 22\).
Let \(n\) be a positive integer, and consider the list \(\{1,2,3,\ldots,n\}\). We define the integer \(f_n\) to be the sum of all 3-sign sums of all increasing sublists of \(\{1,2,3,\ldots,n\}\). For example, \[f_3 = \mu(\{1\}) + \mu(\{2\}) + \mu(\{3\}) + \mu(\{1,2\}) + \mu(\{1,3\}) + \mu(\{2,3\}) + \mu(\{1,2,3\}).\] The problems below use binomial coefficients and the binomial theorem. If you are unfamiliar with, or need a refresher for, these concepts, please see this Problem of the Month lesson.
Compute \(f_3\), \(f_4\), and \(f_5\).
Verify that \(f_5 = 2f_4 + 5\left(\binom{4}{0} + \binom{4}{1} - \binom{4}{2} + \binom{4}{3} + \binom{4}{4}\right)\).
For all integers \(n \geq 2\), prove that \(f_{n+1} = 2f_n + (n+1)\left(b_0 \binom{n}{0} + b_1\binom{n}{1} + b_2\binom{n}{2} + \cdots + b_n\binom{n}{n}\right)\) where \[b_t = \begin{cases} 1 &\text{if $t+1$ is not a multiple of $3$} \\ -1 &\text{if $t+1$ is a multiple of $3$}. \end{cases}\]
For the remainder of the problems, our goal is to work out how to compute the expression \[b_0 \binom{n}{0} + b_1\binom{n}{1} + b_2\binom{n}{2} + \cdots + b_n\binom{n}{n}.\] With that in mind, let \(\alpha\) be a number that satisfies \(\alpha^2 + \alpha = -1\).
It turns out that there is no real number \(\alpha\) with this property (see if you can prove this!), but we can still work with \(\alpha\) as a number. We simply treat \(\alpha\) like a variable, with the added flexibility that we can replace \(\alpha^2 + \alpha\) with \(-1\).
It’s very likely that you already have experience doing something like this. For example, when we write \(\sqrt 2\), it’s not important that \(\sqrt 2 \approx 1.41\). The important thing is that the number satisfies \((\sqrt 2)^2 = 2\). So, when working with \(\sqrt 2\), we simply treat it like a variable with the added bonus that we can replace \((\sqrt 2)^2\) with \(2\). Similarly, when we write a fraction like \(\frac{5}{3}\), while it’s true that this number is equal to \(1.\overline{6}\), the important thing is that when you multiply \(\frac{5}{3}\) by \(3\), you get \(5\).
Evaluate the following expressions (they should all be integers!).
\(\alpha^3\)
\(\alpha^8 + \alpha^4 + \alpha^9\)
\((1+\alpha) - (1+\alpha)^2\)
Let \(n \geq 1\) be an integer. Let \(g_n(x) = (1 + x)^n\).
Find numbers \(A\), \(B\), and \(C\) in terms of \(\alpha\) such that \[b_0 \binom{n}{0} + b_1\binom{n}{1} + b_2\binom{n}{2} + \cdots + b_n\binom{n}{n} = Ag_n(1) + Bg_n(\alpha) + Cg_n(\alpha^2).\] [Note: The binomial theorem will be essential here.]
Using the values you found in part (a), Let \(d_n = Ag_n(1) + Bg_n(\alpha) + Cg_n(\alpha^2)\). Evaluate \(d_n\) (it is always an integer!). Keep in mind that the value of \(d_n\) may depend on \(n\).
Evaluate \(f_6, f_7, f_8, f_9,f_{10},f_{11},\) and \(f_{12}\).
Here is Question B3 from the 2024 Canadian Intermediate Mathematics Contest.
Given an increasing list of consecutive integers, the 3-sign sum of the list is the sum of the integers in the list, in order, except that every third integer is subtracted instead of added. For example, the 3-sign sum of the list \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\) is \(3+4-5+6+7-8+9=16\).
Determine the 3-sign sum of \(8\), \(9\), \(10\), \(11\), \(12\), \(13\), \(14\), \(15\).
For a positive integer \(n\), a slice of the list \(1\), \(2\), \(3\), \(\ldots\), \(n-1\), \(n\) is an increasing list of at least \(1\) and at most \(n\) consecutive integers, each of which is between \(1\) and \(n\) inclusive. For example, \(1\), \(2\) and \(2\), \(3\), \(4\) are both slices of the list \(1\), \(2\), \(3\), \(4\), \(5\). As another example, the list \(1\), \(2\), \(3\) has a total of six slices. They are given in the left column of the table below with their 3-sign sums in the right column.
| Slice | 3-sign sum |
|---|---|
| \(1\), \(2\), \(3\) | \(1+2-3 = 0\) |
| \(1\), \(2\) | \(1+2=3\) |
| \(2\), \(3\) | \(2+3=5\) |
| \(1\) | \(1\) |
| \(2\) | \(2\) |
| \(3\) | \(3\) |
For a positive integer \(n\), the Ghimire number of \(n\), denoted \(G_n\), is the sum of the 3-sign sums of all slices of \(1\), \(2\), \(3\), \(\ldots\), \(n-1\), \(n\). For example, using the information from the table above, \(G_3 = 0+3+5+1+2+3=14\).
For each integer \(n\geq 1\), show that \(\dfrac{G_{3n} - 2G_{3n-1} + G_{3n-2}}{3}\) is a perfect square.
Determine the remainder when \(G_{2025} - G_{2024}\) is divided by \(27\).
Let \(a\), \(b\), \(c\), and \(d\) be rational numbers and \(f(x)=ax^3+bx^2+cx+d\). Suppose \(f(n)\) is an integer whenever \(n\) is an integer and that \[\dfrac{1}{3}n^3-n-\dfrac{2}{3}\leq f(n)\leq \dfrac{1}{3}n^3+n^2+2n+\dfrac{4}{3}\] for every integer \(n\) with the possible exception of \(n=-2\).
This month’s problem is about the card game SET!. Each card in the game SET! has four properties, and each property has three options as follows:
Number: \(1\), \(2\), or \(3\).
Colour: Red, green, or purple.
Shading: Solid, striped, or open.
Shape: Squiggle, diamond, or oval.
For example, below are some cards from a SET! deck. From left to right we have a card with \(1\) red open diamond, a card with \(2\) green solid squiggles, a card with \(3\) purple striped ovals, and a card with \(1\) red solid oval.
A set is a group of three cards such that for each of the four properties, all three cards have the same option, or all three cards have different options. For example, the following four collections of three cards are sets:
However, the following two collections of three cards are not sets:
The order of the cards doesn’t matter, so the two collections of three cards
are considered to be the same set. Note that the same card could appear in two distinct sets.
Find six distinct sets in the following collection of twelve cards:
A SET! deck consists of exactly one of every possible card. How many cards are in a SET! deck?
How many distinct sets contain the following card?
How many different sets exist in a SET! deck?
In a game of SET!, first, a full deck is shuffled. Then twelve cards are dealt on the table, and the players try to find sets. If a player finds a set, they shout "set", and pick up the three cards that form the set. Those three cards are removed from the game (to be counted at the end), and three more cards from the deck are dealt to replace them. The game continues until all the cards from the deck are dealt and there are no more sets among the cards remaining on the table.
Suppose that during a game of SET!, there are three cards remaining on the table. That is, every card in the deck besides the three on the table has been collected as part of a set. Show that the remaining three cards must form a set.
A lattice point in the Cartesian plane is a point \((a,b)\) with the property that both \(a\) and \(b\) are integers. In this Problem of the Month, we will investigate regular polygons that have every vertex lying on a lattice point.
Let \(A\) and \(B\) be distinct lattice points on the Cartesian plane, neither of which have coordinates \((0,0)\). Show that the measure of \(\angle AOB\) cannot equal \(60\degree\), where \(O\) has coordinates \((0,0)\).
Consider a regular pentagon \(ABCDE\). Let \(F\) be the point of intersection of lines \(AD\) and \(BE\).
Show that the quadrilateral \(FBCD\) is a parallelogram.
Show that if \(B\), \(C\), and \(D\) are lattice points then so is \(F\).
View a regular \(n\)-gon as a collection of \(n\) line segments. Give each line segment a direction (indicated by an arrow), moving in a clockwise direction (see the image below). Label the line segments \(L_1,L_2,\ldots,L_n\). For each \(i\), label the starting point of \(L_i\) by \(A_i\). Note that the points \(A_1,A_2,\ldots,A_n\) are the vertices of the \(n\)-gon.
Now, translate the line segments (without any rotation) so that the points \(A_i\) all coincide. For each \(L_i\), label its new endpoint by \(B_i\). Below are images of this process when \(n = 7\).
Show that the polygon \(B_1B_2\cdots B_n\) is a regular \(n\)-gon.
Let \(y\) be the length of \(L_1\) and \(x\) be the length of the line segment \(B_1B_2\). Compute \(\frac{x}{y}\) in terms of \(n\).
We call a polygon that has every vertex lying on a lattice point a lattice polygon. Show that if a regular \(n\)-gon is a lattice polygon, then \(n = 4\).
Define a function \(f\) whose input and output are both lists of \(n\) nonnegative integers by \[f(a_1,a_2,\dots,a_n)=(|a_1-a_2|,|a_2-a_3|,\dots,|a_{n-1}-a_n|,|a_n-a_1|)\] where, as usual, \(|x|\) represents the absolute value of \(x\).
For example, \[f(1,2,3,4)=(|1-2|,|2-3|,|3-4|,|4-1|)=(1,1,1,3)\] and \[f(2,3,5)=(|2-3|,|3-5|,|5-2|)=(1,2,3).\] We will denote by \(f^k\) the function that iterates the application of \(f\) a total of \(k\) times. For example, \[f^4(1,1,1,3)=f^3(0,0,2,2)=f^2(0,2,0,2)=f(2,2,2,2)=(0,0,0,0).\] We will call a list \((a_1,a_2,\dots,a_n)\) smooth if there is some \(m\) for which \(f^m(a_1,\dots,a_n) = (0,0,\ldots,0)\). That is, a list is smooth if some number of applications of \(f\) will result in the list of all zeros. For example, \((1,1,1,3)\) is smooth since \(f^4(1,1,1,3)=(0,0,0,0)\), as demonstrated above.
Find a list of length \(5\) that is not smooth. Find a list of length \(7\) that is not smooth.
Show that for all odd integers \(n\geq 1\) there exists a list \(L\) of length \(n\) that is not smooth.
How many smooth lists \((a,b,c)\) are there with \(a\), \(b\), and \(c\) each no larger than \(100\)?
Suppose \(L\) is a list of length 4 consisting of only zeros and ones. Show that \(L\) is smooth.
Show that all lists of length 4 are smooth.
This month’s problem is inspired by Question 9 on the 2025 Euclid contest. The question in its original form is on the next page. As a warm up, try the problem yourself before attempting the Problem of the Month.
While solving Q9(c), you need to find pairs of integers \((m,e)\) satisfying that \(m^2 - 8e^2\) is a perfect square. Let’s investigate this problem further.
For each of the following equations, find one pair \((m,e)\) of non-zero integers that solve it: \(m^2 - 8e^2 = 1\), \(m^2 - 8e^2 = 4\) and \(m^2 - 8e^2 = 9\).
Integers \(a\) and \(b\) are called coprime if they share no positive common divisors other than \(1\). For example, \(3\) and \(5\) are coprime but \(4\) and \(6\) are not.
Find a pair \((m,e)\) of coprime integers satisfying \(m^2 - 8e^2 = 49\).
Let’s focus on expressions of the form \(a + b\sqrt 8\), where \(a\) and \(b\) are integers. Define the norm of \(a + b\sqrt 8\) to be \(N(a + b\sqrt 8) = (a+b\sqrt 8)(a - b\sqrt 8)\).
Let \(a,b,c,d\) be integers. Prove that \(N\big((a + b\sqrt8)(c + d\sqrt 8)\big) = N(a + b\sqrt8)N(c + d \sqrt 8)\).
It turns out that \(19^2 - 8(3^2) = 17^2\) and \(27^2 - 8(5^2) = 23^2\). Find coprime integers \(a,b\) so that \(a^2 - 8b^2 = 391^2\).
Find infinite sequences of integers \(a_1,a_2,\ldots\) and \(b_1,b_2,\ldots\) satisfying that for all positive integers \(n\),
\(a_n\) and \(b_n\) are coprime, and
\(a_n^2 - 8b_n^2 = 7^{2^n}\).
When we write \(7^{2^n}\) we mean \(7^{(2^n)}\). So, for example, when \(n = 5\), \(7^{2^n}\) is equal to \(7^{32}\) and not \(49^5\).
Here is Question 9 from the 2025 Euclid contest.
Suppose that \(p(x) = qx^3 - rx^2 - sx + t\) for some positive integers \(q<r<s<t\) which form an arithmetic sequence.
Show that \(x = 1\) is a root of \(p(x)\).
Suppose that the average of \(q\), \(r\), \(s\), \(t\) is 19 and that \(p(x)\) has three rational roots. Determine the roots of \(p(x)\).
Prove that, for every positive integer \(n > 3\), there are at least two arithmetic sequences of positive integers \(q<r<s<t\) with common difference \(2n\) for which \(p(x)\) has three rational roots.
(An arithmetic sequence is a sequence in which each term after the first is obtained from the previous term by adding a constant, called the common difference. For example, \(3, 5, 7, 9\) are the first four terms of an arithmetic sequence.)