2024 Galois Contest
Solutions
(Grade 10)

Thursday, April 4, 2024
(in North America and South America)

Friday, April 5, 2024
(outside of North American and South America)

©2024 University of Waterloo

1. 1. Solution 1:

      The length of the expanded garden is $(5+2\times 2)\text{ m}=9\text{ m}$, and the width is $4\text{ m}$.
      Thus, the total area of the expanded garden is $9\text{ m}\times 4\text{ m}=36{\text{ m}}^2$.

      Solution 2:

      The area of the original $5\text{ m}$ by $4\text{ m}$ garden is $5\text{ m}\times 4\text{ m}=20{\text{ m}}^2$.
      Each additional $2\text{ m}$ by $4\text{ m}$ plot has area $2\text{ m}\times 4\text{ m}=8{\text{ m}}^2$, and so the total area of the expanded garden is $(20+2\times 8){\text{ m}}^2=36{\text{ m}}^2$.

   2. Solution 1:

      The combined garden and path has length $9\text{ m}+1\text{ m}=10\text{ m}$, and width $(4+2\times 1)\text{ m}=6\text{ m}$.
      Thus, the area of the garden and the path is $10\text{ m}\times 6\text{ m}=60{\text{ m}}^2$.

      Solution 2:

      Consider splitting the path into three rectangles, as shown.

      

      Each of the rectangles above and below the garden has dimensions $9\text{ m}$ by $1\text{ m}$, and thus each has area $9\text{ m}\times 1\text{ m}=9{\text{ m}}^2$.
      The remaining section of the path has height$(4+2\times 1)\text{ m}=6\text{ m}$ and width $1\text{ m}$, and thus has area $6\text{ m}\times 1\text{ m}=6{\text{ m}}^2$. The area of the expanded garden is 36 m${}^2$, and so the total combined area of the garden and the path is $(36+2\times 9+6){\text{ m}}^2=60{\text{ m}}^2$.

   3. Solution 1:

      Each of the new plots has length $2\text{ m}$, and so $n$ plots increase the $9\text{ m}$ length of the garden by $2n\text{ m}$.
      Thus, the combined length of the garden and the path is $(9+2n+2\times 1)\text{ m}=(2n+11)\text{ m}$. The combined width of the garden and the path is $(4+2\times 1)\text{ m}=6\text{ m}$.
      Thus in ${\text{m}}^2$, the total combined area of the garden and the path is $6\times (2n+11)$.
      Solving $6\times (2n+11)=150$, we get $2n+11=\frac{150}{6}=25$ or $2n=14$, and so $n=7$.

      Solution 2:

      Consider splitting the combined area of the garden and path into three rectangles, as shown.

      

      Each of the rectangles to the left and right of the garden has height $(4+2\times 1)\text{ m}=6\text{ m}$, width $1\text{ m}$, and thus each has area $6\text{ m}\times 1\text{ m}=6{\text{ m}}^2$.
      The remaining rectangle, which combines the garden and the remaining sections of the path, also has height $6\text{ m}$.
      Each of the new plots has length $2\text{ m}$, and so $n$ plots increase the $9\text{ m}$ length of the garden by $2n\text{ m}$.
      Thus, the length of this remaining rectangle is $(2n+9)\text{ m}$.
      Measured in ${\text{m}}^2$, the total combined area of the garden and the path is $2\times 6+6\times (2n+9)$ or $12+6\times (2n+9)$.
      Solving $12+6\times (2n+9)=150$, we get $6\times (2n+9)=138$ or $2n+9=\frac{138}{6}=23$ or $2n=14$, and so $n=7$.

2. 1. Beginning with the point $(5,11)$, and applying $R$ then $T$, the resulting coordinates are $(11,-3)$, as shown: $$(5,11)\stackrel{R}{⟶}(11,-5)\stackrel{T}{⟶}(11,-3)$$

   2. Solution 1:

      When a point is rotated $90\mathrm{°}$ about the origin $4$ times, the result is a rotation of $4\times 90\mathrm{°}=360\mathrm{°}$ or one full rotation about the origin.
      Thus beginning with the point $(-3,7)$, when $R$ is applied $4$ times, the point returns to its original location, and so the resulting coordinates are $(-3,7)$.
      When $R$ is applied a 5th time, the resulting coordinates are $(7,3)$.

      Solution 2:

      Beginning with the point $(-3,7)$, and applying $R$ $5$ times, the resulting coordinates are $(7,3)$, as shown: $$(-3,7)\stackrel{R}{⟶}(7,3)\stackrel{R}{⟶}(3,-7)\stackrel{R}{⟶}(-7,-3)\stackrel{R}{⟶}(-3,7)\stackrel{R}{⟶}(7,3)$$

   3. Beginning with the point $(9,1)$, and applying the sequence $R$, $R$, $T$, the resulting coordinates are $(-9,1)$, as shown: $$(9,1)\stackrel{R}{⟶}(1,-9)\stackrel{R}{⟶}(-9,-1)\stackrel{T}{⟶}(-9,1)$$ Continuing with the point $(-9,1)$, and applying the sequence $R$, $R$, $T$ again, the resulting coordinates are $(9,1)$, as shown: $$(-9,1)\stackrel{R}{⟶}(1,9)\stackrel{R}{⟶}(9,-1)\stackrel{T}{⟶}(9,1)$$ Beginning with the point $(9,1)$, and applying the sequence $R$, $R$, $T$ twice, the resulting coordinates are $(9,1)$ (that is, the point returns to its original location).
      This will continue to occur each time the sequence $R$, $R$, $T$ is applied an even number of times, and so after applying $R$, $R$, $T$ $10$ times, the resulting coordinates are $(9,1)$.
      Beginning with the point $(9,1)$, and applying the sequence $R$, $R$, $T$ an 11th time, the resulting coordinates are $(-9,1)$, the steps to which were previously shown.

3. 1. Of the $7$ balls in the hat, there are $3$ balls that are even-numbered (numbered $2$, $4$ and $6$) and so the probability that the first ball drawn is even-numbered is $\frac{3}{7}$.

   2. There are $7$ possible choices for the first ball, and since a drawn ball is neither replaced nor returned to the hat, there are $6$ choices for the second ball, and thus $7\times 6=42$ ways that the first two balls may be drawn.
      The sum of the numbers on the first two balls drawn is $5$ exactly when the numbers are $1$ and $4$, in some order, or $2$ and $3$, in some order.
      Thus there are $4$ possible ways that the first two balls drawn have a sum of $5$: $1$ and $4$, $4$ and $1$, $2$ and $3$, or $3$ and $2$.
      The probability that the sum of the numbers on the first two balls drawn is $5$ is $\frac{4}{42}=\frac{2}{21}$.

   3. Suppose the probability that the sum of the numbers on the first two balls drawn is greater than or equal to $6$ is $p$.
      Then we let $\bar{p}$ equal the probability that the sum of the numbers on the first two balls drawn is not greater than or equal to $6$.
      That is, $\bar{p}$ is equal to the probability that the sum of the numbers on the first two balls drawn is less than $6$, and so $p=1-\bar{p}$.

      If sum of the numbers on the first two balls drawn is less than $6$, then this sum is either $5$, $4$ or $3$ (since two different balls are drawn, the smallest possible sum is $1+2=3$).
      From part (b), there are exactly $4$ ways that the first two balls drawn have a sum of $5$.
      There are exactly $2$ ways in which the sum is $4$: $1$ and $3$ or $3$ and $1$ ($2$ and $2$ is not possible since there is only one $2$).
      There are exactly $2$ ways in which the sum is $3$: $1$ and $2$ or $2$ and $1$.
      Therefore, of the $7\times 6=42$ ways that the first two balls may be drawn, there are$4+2+2=8$ ways that the sum is less than $6$, and so $\bar{p}=\frac{8}{42}=\frac{4}{21}$.
      Finally, the probability that the sum of the numbers on the first two balls drawn is greater than or equal to $6$ is $p=1-\bar{p}=1-\frac{4}{21}=\frac{17}{21}$.

      Note: We may have instead chosen to determine $p$ directly. That is, we may have determined the probability that the sum of the numbers on the first two balls drawn was $6$, $7$, $8$, $9$, $10$, $11$, $12$, or $13$ and then added each of these probabilities together to determine $p$.
      We chose to determine $\bar{p}$ since it required considering that the sum of the numbers on the first two balls drawn was $3$, $4$ or $5$, and thus was less work than it would be to determine $p$ directly.

   4. The probability that the sum of the numbers on the first two balls drawn is greater than or equal to $7$ is $q=\frac{3}{4}$.
      As in part (c), we similarly define $\bar{q}$ to be the probability that the sum of the numbers on the first two balls is less than $7$, and thus $q=1-\bar{q}$, or $\frac{3}{4}=1-\bar{q}$, and so $\bar{q}=\frac{1}{4}$.
      There are $8$ possible choices for the first ball (since an eighth ball was added to the hat) and $7$ choices for the second ball, and thus $8\times 7=56$ ways that the first two balls may be drawn.
      Since $\bar{q}=\frac{1}{4}=\frac{14}{56}$, then there are $14$ ways that the sum of the numbers on the first two balls drawn is less than $7$.
      Without using the new gold ball, there are $12$ ways that the sum of the numbers on the first two balls drawn can be less than $7$.
      These are: $1+5$, $1+4$, $1+3$, $1+2$, $2+4$, $2+3$, and their reversals.
      Thus, the new gold ball, numbered with the integer $k$, where $1\le k\le 7$, must give $2$ additional ways to produce a sum that is less than $7$.
      If $k=5$, then the gold ball may be paired with the ball numbered $1$ (drawn in either order) to give $2$ additional ways to produce a sum that is less than $7$.
      Further, if $k=5$, the gold ball cannot be paired with any other ball to give a sum that is less than $7$, and so the correct value of $k$ is $5$.
      (You should confirm for yourself that if $k=6\text{ or }7$, there are no additional ways for the sum to be less than $7$, and if $k=1,2,3,\text{ or }4$, then there are more than $2$ additional ways for the sum to be less than $7$.)

4. 1. We denote the number in row $r$, column $c$ as $[r,c]$, and so $[2,1]=1$, for example.
      We begin by determining the numbers in column 2.
      The neighbours of $[1,1]$ are $[2,1]$ and $[1,2]$, and so $[1,1]=[2,1]\times [1,2]$ or $-1=1\times [1,2]$, which gives $[1,2]=-1$.
      The neighbours of $[2,1]$ are $[1,1]$, $[3,1]$ and $[2,2]$, and so $[2,1]=[1,1]\times [3,1]\times [2,2]$ or $1=(-1)\times (-1)\times [2,2]$, which gives $[2,2]=1$.
      The neighbours of $[3,1]$ are $[2,1]$ and $[3,2]$, and so $[3,1]=[2,1]\times [3,2]$ or $-1=1\times [3,2]$, which gives $[3,2]=-1$.
      It is important to note that there was no choice in determining the numbers in column 2.
      That is, the properties of the numbers in column 1 are satisfied only when $[1,2]=-1$, $[2,2]=1$ and $[3,2]=-1$.

      Continuing in this way, the numbers in column 3 are$[1,3]=1$, $[2,3]=1$ and $[3,3]=1$.
      The numbers in column 3 are once again necessary to satisfy the properties of the numbers in column 2.
      If we were to stop here, is the following $3\times 3$ grid a Griffin Grid?

      $-1$	$-1$	$1$
      $1$	$1$	$1$
      $-1$	$-1$	$1$

      The neighbours of $[1,3]=1$ are $[1,2]=-1$ and $[2,3]=1$, however $1\ne (-1)\times 1$, and so it is not possible to construct a $3\times 3$ Griffin Grid with the given first column.

      Continuing, we complete columns 4 and 5, as shown below.

      $-1$	$-1$	$1$	$-1$	$-1$
      $1$	$1$	$1$	$1$	$1$
      $-1$	$-1$	$1$	$-1$	$-1$

      The numbers in column 5 are chosen so that the numbers in column 4 satisfy the properties of a Griffin Grid.
      We must check that the numbers in column 5 also satisfy the properties of a Griffin Grid. Since each cell in column 5 contains a $-1$ or a $1$, and the number in each cell is equal to the product of the numbers in all cells that are neighbours, then the completed $3\times 5$ grid is indeed a Griffin Grid.

   2. In the first column of a $3\times 5$ grid, there are two possibilities for the number in each cell, and so there are $2\times 2\times 2=8$ possible first columns.
      As was demonstrated in part (a), the remainder of the grid is completely determined by the three entries in the first column, and so there are at most $8$ different $3\times 5$ Griffin Grids.
      Expressed as an ordered triple, consider the two grids with first columns $(1,-1,-1)$ and $(-1,-1,1)$.
      Since each of these columns is a vertical reflection of the other, then their completed $3\times 5$ grids will be vertical reflections of one another.
      That is, the $3\times 5$ grid with first column $(-1,-1,1)$ is a Griffin Grid exactly when the $3\times 5$ grid with first column $(1,-1,-1)$ is a Griffin Grid, and so we may consider these two grid types as one case.
      Similarly, the grids with first columns $(1,1,-1)$ and $(-1,1,1)$ are also vertical reflections of one another and so we may consider these two grid types as one case.Each cell of a grid with first column $(1,1,1)$ is a $1$, and thus gives a $3\times 5$ Griffin Grid.
      At this point, we are left to consider the 5 grids whose first columns are: $$A(-1,-1,-1),B(1,-1,1),C(-1,1,-1),D(1,-1,-1),\text{ and }E(1,1,-1)$$ We complete each of the $5$ grids below, replacing 1 with $+$ and $-1$ with $-$.

      First column A

      $-$	$+$	$+$	$+$	$-$
      $-$	$-$	$+$	$-$	$-$
      $-$	$+$	$+$	$+$	$-$

      First column B

      $+$	$-$	$+$	$-$	$+$
      $-$	$-$	$+$	$-$	$-$
      $+$	$-$	$+$	$-$	$+$

      First column C

      $-$	$-$	$+$	$-$	$-$
      $+$	$+$	$+$	$+$	$+$
      $-$	$-$	$+$	$-$	$-$

      First column D

      $+$	$-$	$-$	$+$	$-$
      $-$	$+$	$+$	$+$	$-$
      $-$	$+$	$-$	$-$	$+$

      First column E

      $+$	$+$	$-$	$-$	$-$
      $+$	$-$	$+$	$-$	$+$
      $-$	$-$	$-$	$+$	$+$

      As was demonstrated in part (a), the numbers in column 5 are chosen so that the numbers in column 4 satisfy the properties of a Griffin Grid.
      We must check if the numbers in column 5 also satisfy the properties of a Griffin Grid.
      Since each cell in each column 5 contains a $-1$ or a $1$, and the number in each cell is equal to the product of the numbers in all cells that are neighbours, then each of the completed $3\times 5$ grids is indeed a Griffin Grid.
      Thus, each of the $8$ possible first columns produces a $3\times 5$ Griffin Grid, and so there are a total of $8$ Griffin Grids of this size.

      Additional note: The grid with first column $F(-1,-1,1)$ produces a $3\times 5$ Griffin Grid that is a vertical reflection of the grid with first column $D$.
      Similarly, the grid with first column $G(-1,1,1)$ produces a $3\times 5$ Griffin Grid that is a vertical reflection of the grid with first column $E$.
      These two Griffin Grids, along with the grid with first column $H(1,1,1)$, are shown below.

      First column F

      $-$	$+$	$-$	$-$	$+$
      $-$	$+$	$+$	$+$	$-$
      $+$	$-$	$-$	$+$	$-$

      First column G

      $-$	$-$	$-$	$+$	$+$
      $+$	$-$	$+$	$-$	$+$
      $+$	$+$	$-$	$-$	$-$

      First column H

      $+$	$+$	$+$	$+$	$+$
      $+$	$+$	$+$	$+$	$+$
      $+$	$+$	$+$	$+$	$+$

   3. Continuing our work from part (b), if we extend each $3\times 5$ grid one additional column, we see that each has the same 6th column, $(1,1,1)$.
      This means that for each $3\times 7$ grid, the 7th column will match the 5th.
      Can you see why this is? (For example, see the 2nd, 3rd and 4th columns of the grid with first column $C$ in part (b).)
      As was demonstrated in part (b), the grid with first column $F$ is a vertical reflection of the grid with first column $D$, and so their completed $3\times n$ grids will be vertical reflections of one another.
      That is, the $3\times n$ grid with first column $D$ is a Griffin Grid exactly when the $3\times n$ grid with first column $F$ is a Griffin Grid, and so we may consider these two grid types as one case. The same is true for the grids with first columns $E$ and $G$.Each cell of a grid with first column $(1,1,1)$ is a $1$, and thus gives a $3\times n$ Griffin Grid for all values of $n\ge 2$.
      The first $7$ columns of the grids with first columns $A$, $B$, $C$, $D$, $E$ are shown below.

      First column A

      $-$	$+$	$+$	$+$	$-$	$+$	$-$
      $-$	$-$	$+$	$-$	$-$	$+$	$-$
      $-$	$+$	$+$	$+$	$-$	$+$	$-$

      First column B

      $+$	$-$	$+$	$-$	$+$	$+$	$+$
      $-$	$-$	$+$	$-$	$-$	$+$	$-$
      $+$	$-$	$+$	$-$	$+$	$+$	$+$

      First column C

      $-$	$-$	$+$	$-$	$-$	$+$	$-$
      $+$	$+$	$+$	$+$	$+$	$+$	$+$
      $-$	$-$	$+$	$-$	$-$	$+$	$-$

      First column D

      $+$	$-$	$-$	$+$	$-$	$+$	$-$
      $-$	$+$	$+$	$+$	$-$	$+$	$-$
      $-$	$+$	$-$	$-$	$+$	$+$	$+$

      First column E

      $+$	$+$	$-$	$-$	$-$	$+$	$-$
      $+$	$-$	$+$	$-$	$+$	$+$	$+$
      $-$	$-$	$-$	$+$	$+$	$+$	$+$

      We will refer to each of the above grids by their first column, $A$, $B$, $C$, $D$, and $E$.
      Given a first column and an integer $n\ge 2$, there either is no $3\times n$ Griffin Grid with that first column, or there is exactly one.
      For each possible first column, we are going to count the number of $n$, where $2\le n\le 2024$, for which there is a $3\times n$ Griffin Grid.
      Notice that the 7th column of each of the above grids $A$, $B$ and $C$ matches the 1st column of the grid.
      Further, since the 6th column in each grid is $(1,1,1)$, then the 8th column will match the 2nd, the 9th will match the 3rd, and in general, column $n+6$ will match column $n$.
      Each of the grids $A$, $B$ and $C$ repeats every $6$ columns, and so if a $3\times n$ grid ($n\ge 2)$ is a Griffin Grid, then a $3\times (n+6)$ grid is also a Griffin Grid.
      This means that to determine for which values of $n$ a $3\times n$ grid is a Griffin Grid, we need only consider $2\le n\le 7$ (we don’t consider $n=1$ and since the pattern repeats every $6$ columns, we check $n=7$). We then use the fact that the pattern repeats to determine the number of Griffin Grids for all values of $n$ where $2\le n\le 2024$.

      In grids $D$ and $E$, the 7th column is a vertical reflection of the 1st column.
      Further, since the 6th column in each grid is $(1,1,1)$, then the 8th column will be a vertical reflection of the 2nd, and in general, column $n+6$ is a vertical reflection of column $n$.
      That is, in each of the grids $D$ and $E$, each group of 6 columns beginning with the 7th column is a vertical reflection of the previous group of 6 columns.
      This tells us that if grid $D$ or $E$ (and thus $F$ or $G$) is a $3\times n$ Griffin Grid, then the $3\times (n+6)$ grid is also a Griffin Grid.
      Why is this? To determine if a $3\times k$ grid is a Griffin Grid, we check that each number in column $k$ is the product of its neighbours, which are numbers in column $k$ and in the previous column, $k-1$.
      Reflecting both of these columns vertically does not change the product of the neighbouring cells, and so both the $3\times n$ and $3\times (n+6)$ grids are Griffin Grids, or they both are not.

      Next, we must determine for which values of $n$ with $2\le n\le 7$ the grids $A$, $B$, $C$, $D$, and $E$ are Griffin Grids.
      In the diagrams below, we place a "Y" below column $n$ if the $3\times n$ grid is a Griffin Grid, otherwise we leave it blank.

      

      Thus, grids $A$, $B$ and $C$ are $3\times n$ Griffin grids for $n=2,5,8,11,14,17,\dots$ and so on, while grids $D$ and $E$ are $3\times n$ Griffin grids for $n=5,11,17,23,\dots$ and so on.
      Since $2024=6\times 337+2$, the complete pattern of 6 columns repeats 337 times for each of the grids. In each group of $6$, there are $2$ values of $n$ for which grids $A$, $B$ and $C$ are Griffin Grids, and so there are $2\times 337=674$ Griffin Grids for $2\le n\le 2022$ for each of these $3$ grid types.
      However, the $3\times 2024$ grid is also a Griffin Grid in each case, and so there are $675$ Griffin Grids for each of the grids $A$, $B$ and $C$.
      In each group of $6$, there is $1$ value of $n$ for which grids $D$, $E$, $F$, and $G$ are Griffin Grids, and so there are $337$ Griffin Grids for each of these $4$ grid types.
      Finally, grid $H$ (the grid of all $1$s) is a Griffin Grid for all values of $n$, and so there are $2023$ Griffin Grids in this case.

      Thus, the sum of the numbers of $3\times n$ Griffin Grids for $2\le n\le 2024$ is $$S=(3\times 675)+(4\times 337)+2023=5396$$