2023 Galois Contest
Solutions
(Grade 10)

Wednesday, April 5, 2023
(in North America and South America)

Thursday, April 6, 2023
(outside of North American and South America)

©2023 University of Waterloo

1. 1. A grid with 12 rows and 15 columns has $12\times 15=180$ pieces.

   2. Solution 1

      We begin by recognizing that the middle pieces in each grid form a rectangle.
      In a grid with 6 rows, the 1st row and the 6th row are each composed entirely of edge pieces, and thus the grid has $6-2=4$ rows that contain some middle pieces.
      In each of these 4 rows, the 1st column and the 4th column are each composed entirely of edge pieces, and thus the grid has $4-2=2$ columns that contain some middle pieces.
      Therefore, a grid with 6 rows and 4 columns contains a rectangular grid of middle pieces having 4 rows and 2 columns, and thus has $4\times 2=8$ middle pieces.

      Solution 2

      A grid with 6 rows and 4 columns has $6\times 4=24$ pieces.
      We proceed to find the number of edge pieces, and then subtract this number from 24 to determine the number of middle pieces.
      The first column of the grid contains 6 edge pieces (since there are 6 rows), and the fourth column of the grid also contains 6 edge pieces.
      The first row of the grid contains 4 edge pieces (since there are 4 columns).
      However, the first and last of these edge pieces (the top left and right corners of the grid) were previously included in the count of edge pieces in the first and last columns, respectively, and so there are $4-2=2$ additional edge pieces in the first row.
      Similarly, there are 2 additional edge pieces in the sixth row.
      Thus, there are $6+6+2+2=16$ edge pieces, and so there are $24-16=8$ middle pieces.

   3. Since 14 has two possible factor pairs, 1 and 14 or 2 and 7, then the dimensions of the rectangular grid of middle pieces has either 1 row and 14 columns (or vice versa), or it has 2 rows and 7 columns (or vice versa).

      If the rectangular grid of middle pieces has 1 row, then the puzzle grid has $1+2=3$ rows since there is a row of edge pieces both above and below the 1 row of middle pieces.
      Similarly, if the rectangular grid of middle pieces has 14 columns, then the puzzle grid has $14+2=16$ columns since there is a column of edge pieces both to the right and to the left of the middle pieces.
      In this case, the puzzle grid has 3 rows and 16 columns (or vice versa), and thus has $3\times 16=48$ pieces.
      A puzzle grid with 48 pieces, including 14 middle pieces, has $48-14=34$ edge pieces.

      If the rectangular grid of middle pieces has 2 rows, then the puzzle grid has $2+2=4$ rows, as above.
      Similarly, if the rectangular grid of middle pieces has 7 columns, then the puzzle grid has $7+2=9$ columns.
      In this case, the puzzle grid has 4 rows and 9 columns (or vice versa), and thus has $4\times 9=36$ pieces.
      A puzzle grid with 36 pieces, including 14 middle pieces, has $36-14=22$ edge pieces.
      The values of $s$ and $t$ are 34 and 22.

   4. A grid with 5 rows and $c$ columns contains $5c$ pieces.
      A grid with 5 rows and $c$ columns contains a rectangular grid of middle pieces with $5-2=3$ rows and $c-2$ columns, and thus has $3(c-2)$ middle pieces.
      Since the number of edge pieces is equal to the number of middle pieces, then the total number of pieces is twice the number of middle pieces.
      Thus, $5c=2\times 3(c-2)$ or $5c=6(c-2)$. Solving, we get $5c=6c-12$ and so $c=12$.

2. 1. If the first term is 7, then the second term is $7+3=10$ (since 7 is odd, we add 3).
      If the second term is 10, then the third term is $10+4=14$ (since 10 is even, we add 4).
      Similarly, the fourth term is $14+4=18$, and the fifth term is $18+4=22$.
      If the first term in an Ing sequence is 7, then the fifth term in the sequence is 22.

   2. Suppose that a term, $x$, is odd. The next term, $x+3$, is even since an odd integer plus an odd integer is even.
      Suppose that a term, $x$, is even. The next term, $x+4$, is even since an even integer plus an even integer is even.
      This means that in an Ing sequence, each term after the first is an even integer.
      Thus, if the fifth term is 62, then the fourth term cannot equal $62-3=59$ (since 59 is odd), and so it must equal $62-4=58$.
      Similarly, the third term is $58-4=54$, and the second term is $54-4=50$.
      If the first term is an even integer, then the first term is $50-4=46$, and if it is an odd integer, then the first term is $50-3=47$.
      If the fifth term in an Ing sequence is 62, then the first term is 46 (the terms are 46, 50, 54, 58, 62) or the first term is 47 (the terms are 47, 50, 54, 58, 62).

   3. If the first term is 49, then the second term is $49+3=52$, and so each term after the second is 4 more than the previous term.
      This means that for every positive integer $k$, there is a term of the form $52+4k$ in the sequence.
      Since $52+4k=4(13+k)$, then each of the remaining terms in the sequence is a multiple of 4.
      The integers that are greater than 318 and less than 330, and that are equal to a multiple of 4 are $320=4\times 80$, $324=4\times 81$, and $328=4\times 82$.

   4. If 18 appears somewhere in an Ing sequence after the first term, then the term preceding 18 is either $18-3=15$, or it is $18-4=14$.
      Each of these is a possible value of $n$, the first term of the sequence.
      As was shown in part (b), each term after the first in an Ing sequence is even, and so if 15 appears in the sequence, then 15 can only be the first term of the sequence.
      Since 14 is even, then it could be the first term, but it could also be a term after the first.
      If 14 appears in the sequence after the first term, then the preceding term is either $14-3=11$, or it is $14-4=10$.
      Each of these is a possible value of $n$.
      If 11 appears in the sequence, then 11 is the first term (since 11 is odd).
      Since 10 is even, then it could be the first term, but it could also be a term after the first.
      If 10 appears in the sequence after the first term, then the preceding term is either $10-3=7$, or it is $10-4=6$.
      Each of these is a possible value of $n$.
      If 7 appears in the sequence, then 7 is the first term.
      Since 6 is even, then it could be the first term, but it could also be a term after the first.
      If 6 appears in the sequence after the first term, then the preceding term is either $6-3=3$, or it is $6-4=2$.
      Each of these is a possible value of $n$.
      If 3 appears in the sequence, then 3 is the first term.
      If 2 appears in the sequence, then 2 must also be the first term of the sequence since both $2-3=-1$ and $2-4=-2$ are not positive integers.
      Thus, if 18 appears somewhere in an Ing sequence after the first term, then the possible values of the first term $n$ are 2, 3, 6, 7, 10, 11, 14, and 15.

3. 1. The line $x=a$ intersects the line $y=x$ at the point $(a,a)$.
      Thus, the length of the base and the height of the triangle are each equal to $a$, and so the area of the triangle is ${\displaystyle \frac{1}{2}}\times a\times a$.
      Solving ${\displaystyle \frac{1}{2}}{a}^2=32$, we get $a^2=64$, and so $a=8$ (since $a>0$).

   2. Solution 1

      The line $x=10$ intersects the line $y=2x$ at the point $(10,20)$.
      The line $x=4$ intersects the line $y=2x$ at the point $(4,8)$.
      Thus, the trapezoid has parallel sides of length 20 and 8, and the distance between the parallel sides is $10-4=6$.
      The area of the trapezoid is ${\displaystyle \frac{6}{2}}(20+8)=3(28)$ which is equal to 84.

      Solution 2

      If the area of the trapezoid is $T$, the area of the new unshaded triangle is $B$, and the area of the original triangle is $A$, then $T=A-B$.
      The line $x=4$ intersects the line $y=2x$ at the point $(4,8)$.
      Thus, the unshaded triangle has base length 4 and height 8, and so $B={\displaystyle \frac{1}{2}}\times 4\times 8=16$.
      The line $x=10$ intersects the line $y=2x$ at the point $(10,20)$.
      Thus, the original triangle has base length 10 and height 20, and so $A={\displaystyle \frac{1}{2}}\times 10\times 20=100$.

      The area of the trapezoid is $T=A-B$ or $T=100-16$ which is 84.

   3. Solution 1

      We begin by determining the area of the trapezoid.
      The line $x=21$ intersects the line $y=3x$ at the point $(21,63)$.
      The line $x=c$ intersects the line $y=3x$ at the point $(c,3c)$.
      Thus, the trapezoid has parallel sides of length 63 and $3c$, and the distance between the parallel sides is $21-c$ (since $0<c<21$).
      The area of the trapezoid is ${\displaystyle \frac{21-c}{2}}(63+3c)$.

      Next, we determine the area of the new triangle.
      If the length of its base is $c$, then its height is $3c$, and so the area of the new triangle is ${\displaystyle \frac{1}{2}}\times c\times 3c={\displaystyle \frac{1}{2}}\times 3c^2$.

      The area of the trapezoid is 8 times the area of the new triangle.
      Solving, we get $$\begin{array}{rl}{\displaystyle \frac{21-c}{2}}(63+3c)& =8\times {\displaystyle \frac{1}{2}}\times 3c^2\\ (21-c)(63+3c)& =8\times 3c^2\\ (21-c)(21+c)& =8\times c^2\\ 441-c^2& =8c^2\\ 441& =9c^2\\ c^2& =49\end{array}$$ and so $c=7$ (since $c>0$).

      Solution 2

      If the area of the trapezoid is $T$, the area of the new triangle is $B$, and the area of the original triangle is $A$, then $T=A-B$.
      The area of the trapezoid is 8 times the area of the new triangle, or $T=8B$.
      Substituting, we get $8B=A-B$ or $9B=A$.

      The line $x=21$ intersects the line $y=3x$ at the point $(21,63)$.

      Thus, $A={\displaystyle \frac{1}{2}}\times 21\times 63={\displaystyle \frac{1323}{2}}$.

      The line $x=c$ intersects the line $y=3x$ at the point $(c,3c)$.
      Thus, $B={\displaystyle \frac{1}{2}}\times c\times 3c={\displaystyle \frac{3c^2}{2}}$.
      Substituting into $9B=A$ and solving, we get $$\begin{array}{rl}9\times {\displaystyle \frac{3c^2}{2}}& ={\displaystyle \frac{1323}{2}}\\ 27c^2& =1323\\ c^2& =49\end{array}$$ and so $c=7$ (since $c>0$).

   4. Solution 1

      As was shown in parts (b) and (c), the vertical line drawn at $x=p$ divides the original triangle into a trapezoid and a new triangle.
      We begin by determining the area of the trapezoid.
      The line $x=1$ intersects the line $y=4x$ at the point $(1,4)$.
      The line $x=p$ intersects the line $y=4x$ at the point $(p,4p)$.
      Thus, the trapezoid has parallel sides of length 4 and $4p$, and the distance between the parallel sides is $1-p$ (since $0<p<1$).
      The area of the trapezoid is ${\displaystyle \frac{1-p}{2}}(4+4p)$.

      Next, we determine the area of the new triangle.
      If the length of its base is $p$, then its height is $4p$, and so the area of the new triangle is ${\displaystyle \frac{1}{2}}\times p\times 4p={\displaystyle \frac{1}{2}}\times 4p^2$.

      The line $x=p$ divides the area of the original triangle in half, and so the area of the trapezoid is equal to the area of the new triangle.
      Solving, we get $$\begin{array}{rl}{\displaystyle \frac{1-p}{2}}(4+4p)& ={\displaystyle \frac{1}{2}}\times 4p^2\\ (1-p)(4+4p)& =4p^2\\ (1-p)(1+p)& =p^2\\ 1-p^2& =p^2\\ 1& =2p^2\\ p^2& ={\displaystyle \frac{1}{2}}\end{array}$$ and so $p={\displaystyle \frac{1}{\sqrt{2}}}$ (since $p>0$).

      Ahmed repeats the process by drawing a second vertical line at $x=q$, where $0<q<p$.
      We wish to determine the value of $q$ in terms of $p$, so that we may use this relationship to determine the position of the 12th vertical line (without needing to repeat these calculations 12 times).
      That is, we will repeat the above process without substituting $p={\displaystyle \frac{1}{\sqrt{2}}}$ so that we may determine the value of $q$ in terms of $p$.

      The vertical line drawn at $x=q$ divides the triangle bounded by the $x$-axis, the line $y=4x$, and the line $x=p$ into a new trapezoid and a new triangle.
      We begin by determining the area of the trapezoid.
      The line $x=p$ intersects the line $y=4x$ at the point $(p,4p)$.
      The line $x=q$ intersects the line $y=4x$ at the point $(q,4q)$.
      Thus, the trapezoid has parallel sides of length $4p$ and $4q$, and the distance between the parallel sides is $p-q$ (since $0<q<p$).
      The area of the trapezoid is ${\displaystyle \frac{p-q}{2}}(4p+4q)$.

      Next, we determine the area of the triangle.
      If the length of its base is $q$, then its height is $4q$, and so the area of the triangle is ${\displaystyle \frac{1}{2}}\times q\times 4q={\displaystyle \frac{1}{2}}\times 4q^2$.

      The line $x=q$ divides the area of the previous triangle in half, and so the area of the trapezoid is equal to the area of the new triangle.
      Solving, we get $$\begin{array}{rl}{\displaystyle \frac{p-q}{2}}(4p+4q)& ={\displaystyle \frac{1}{2}}\times 4q^2\\ (p-q)(4p+4q)& =4q^2\\ (p-q)(p+q)& =q^2\\ p^2-q^2& =q^2\\ p^2& =2q^2\\ q^2& ={\displaystyle \frac{1}{2}}\times p^2\end{array}$$ and so $q={\displaystyle \frac{1}{\sqrt{2}}}\times p$ (since $q>0$).

      This tells us that if Ahmed draws a vertical line at $x=n$ (where $n>0$ and $n$ is less than the $x$-intercept of the vertical line previously drawn), then the next vertical line is drawn at $x={\displaystyle \frac{1}{\sqrt{2}}}\times n$ (since the process repeats).
      Since the original vertical line is at $x=1$, then the 12th vertical line drawn by Ahmed is at $x=1\times {\left({\displaystyle \frac{1}{\sqrt{2}}}\right)}^{12}$ or $x={\left({\left({\displaystyle \frac{1}{\sqrt{2}}}\right)}^2\right)}^6$ or $x={\left({\displaystyle \frac{1}{2}}\right)}^6$, and so $k={\displaystyle \frac{1}{64}}$.

      Solution 2

      As was shown in parts (b) and (c), the vertical line drawn at $x=p$ divides the original triangle into a trapezoid and a new triangle.
      The line $x=1$ intersects the line $y=4x$ at the point $(1,4)$, and so the area of the original triangle is ${\displaystyle \frac{1}{2}}\times 1\times 4=2$.

      The line $x=p$ intersects the line $y=4x$ at the point $(p,4p)$, and so the area of the new triangle is ${\displaystyle \frac{1}{2}}\times p\times 4p=2p^2$.
      The area of the new triangle is half of the area of the original triangle, and so $2p^2=1$ or $p^2={\displaystyle \frac{1}{2}}$, and so $p={\displaystyle \frac{1}{\sqrt{2}}}$ (since $p>0$).
      Ahmed repeats the process by drawing a second vertical line at $x=q$, where $0<q<p$.
      We wish to determine the value of $q$ in terms of $p$, so that we may use this relationship to determine the position of the 12th vertical line (without needing to repeat these calculations 12 times).
      That is, we will repeat the above process without substituting $p={\displaystyle \frac{1}{\sqrt{2}}}$ so that we may determine the value of $q$ in terms of $p$.

      The vertical line drawn at $x=q$ divides the triangle bounded by the $x$-axis, the line $y=4x$, and the line $x=p$ into a new trapezoid and a new triangle.
      As was determined above, the triangle bounded by the $x$-axis, the line $y=4x$, and the line $x=p$ has area $2p^2$.
      The line $x=q$ intersects the line $y=4x$ at the point $(q,4q)$, and so the area of the new triangle is ${\displaystyle \frac{1}{2}}\times q\times 4q=2q^2$.
      The area of the new triangle is half of the area of the previous triangle, and so $2q^2={\displaystyle \frac{2p^2}{2}}$ or $q^2={\displaystyle \frac{1}{2}}\times p^2$, and so $q={\displaystyle \frac{1}{\sqrt{2}}}\times p$ (since $q>0$).
      This tells us that if Ahmed draws a vertical line at $x=n$ (where $n>0$ and $n$ is less than the $x$-intercept of the vertical line previously drawn), then the next vertical line is drawn at $x={\displaystyle \frac{1}{\sqrt{2}}}\times n$ (since the process repeats).
      Since the original vertical line is at $x=1$, then the 12th vertical line drawn by Ahmed is at $x=1\times {\left({\displaystyle \frac{1}{\sqrt{2}}}\right)}^{12}$ or $x={\left({\left({\displaystyle \frac{1}{\sqrt{2}}}\right)}^2\right)}^6$ or $x={\left({\displaystyle \frac{1}{2}}\right)}^6$, and so $k={\displaystyle \frac{1}{64}}$.

      Solution 3

      Ahmed draws the 12th vertical line at $x=k$.
      The line $x=k$ intersects the line $y=4x$ at the point $(k,4k)$, and so the area of the new

      triangle to the left of this line is ${\displaystyle \frac{1}{2}}\times k\times 4k=2k^2$.

      Since the area of each new triangle is half of the area of the previous triangle, then the

      triangle with area $2k^2$ has ${\left({\displaystyle \frac{1}{2}}\right)}^{12}$ of the area of the original triangle.

      The line $x=1$ intersects the line $y=4x$ at the point $(1,4)$, and so the area of the original triangle is ${\displaystyle \frac{1}{2}}\times 1\times 4=2$.

      Equating the areas and solving for $k$, we get $$\begin{array}{rl}2k^2& ={\left({\displaystyle \frac{1}{2}}\right)}^{12}\times 2\\ k^2& ={\left({\displaystyle \frac{1}{2}}\right)}^{12}\\ k& ={\left({\displaystyle \frac{1}{2}}\right)}^6\end{array}$$ and so $k={\displaystyle \frac{1}{64}}$.

4. 1. Solution 1

      Amrita shook hands with exactly 1 person, Bin and Carlos each shook hands with exactly 2 people, and Dennis shook hands with exactly 3 people, and so this gives $1+2+2+3=8$ handshakes, except each of these handshakes is counted twice.
      That is, when Person X shakes Person Y’s hand, Person Y shakes Person X’s hand, and so this one handshake is counted twice.
      In general, if $S$ is the sum of the number of hands shaken by each person, and $N$ is the number of handshakes that occurred, then $N=S÷2$.
      Thus, the total number of handshakes that took place was $8÷2=4$.

      Solution 2

      Dennis shook hands with exactly 3 people and Eloise did not shake hands with anyone.
      Therefore, Dennis must have shaken hands with Amrita, Bin and Carlos (and Amrita, Bin and Carlos each shook hands with Dennis).

      If a line segment drawn between 2 people represents a handshake, then the diagram to the right shows the handshakes accounted for to this point.

      

      The diagram shows that Amrita has 1 handshake, Dennis has 3 and Eloise has 0, and so all handshakes for Amrita, Dennis and Eloise have been accounted for.

      Bin and Carlos each shook hands with exactly 2 people, and so their second handshakes must be with one another (since they can’t be with Amrita, Dennis or Eloise).
      The diagram shows all handshakes that occurred, and so there were a total of 4 handshakes.

      

   2. As in part (a) Solution 1, if 9 people each shook hands with exactly 3 people, then $S=9\times 3=27$, and the total number of handshakes was $N=27÷2=13.5$.
      Since the number of handshakes that took place must be an integer, then it is not possible that each of 9 people shook hands with exactly 3 others.

   3. We represent the 7 people with the letters, A, B, C, D, E, F, and G.
      If each of A, B, C, and D shook hands with one another, and each of E, F, and G shook hands with one another, and no other handshakes occurred, then a total of 9 handshakes took place, as shown in the diagram.

      

      We will show that this set of 9 handshakes satisfies the given conditions and that fewer than 9 handshakes does not, and thus $m=9$.

      We begin with an explanation of why the set of 9 handshakes shown in the diagram satisfies the condition that at least one handshake occurred within each group of 3 people.
      Let Group 1 be the group A, B, C, D, and Group 2 be the group E, F, G.
      In any group of 3 people chosen from the 7 people, either all 3 people are from Group 1, or all 3 people are from Group 2, or 1 person is from one of the two groups, and 2 people are from the other group.
      That is, at least 2 of the 3 people chosen must belong to either Group 1 or to Group 2.
      Since a handshake occurs between each pair of people in Group 1 and between each pair of people in Group 2, and every group of 3 people chosen must contain at least 2 people from the same group, then at least one handshake occurs within each group of 3 people chosen.

      Next, we give an explanation of why fewer than 9 handshakes does not satisfy the given conditions.
      Define $S$ and $N$ as in part (a) Solution 1.
      Assume that $N\le 8$.
      Since each handshake occurs between 2 people and $N\le 8$, then $S$ is at most $8\times 2=16$.
      If each of the 7 people shook 3 or more hands, then $S$ would be at least $7\times 3=21$.
      Since $S$ is at most 16, then at least one of the 7 people shook hands with 2 or fewer people.
      Suppose that it was E who shook hands with 2 or fewer people. (It might not be E but whoever it is, the reasoning is identical.)
      Then at least 4 people did not shake E’s hand.
      Suppose that A, B, C, D did not shake E’s hand. (Again, the reasoning is the same if it is any other four people.)
      In this case, each pair of people from the group A, B, C, D must have shaken hands with one another, otherwise the pair that did not shake hands, along with E, form a group of 3 people in which no handshakes occurred.
      Since each pair of people in the group A, B, C, D shook hands, there are 6 handshakes within this group (A and B, A and C, A and D, B and C, B and D, C and D).
      Since $N$ is at most 8, then E, F and G participate in at most $8-6=2$ handshakes in total.
      That is, E, F, G could participate in 0, 1 or 2 handshakes, giving 3 cases to consider.

      Case 1: No pair of people in the group E, F, G shook hands

      If no pair of people in the group E, F, G shook hands, then they are a group of 3 people in which no handshakes occurred.

      Case 2: Exactly one pair of people in the group E, F, G shook hands

      In this case, there is at most one handshake between one of E, F, G, and one of A, B, C, D.
      Suppose E and F shook hands (recognizing that the argument holds when choosing any pair from E, F, G).
      There is at least one person in the group A, B, C, D who did not shake hands with F and did not shake hands with G, and so this is a group of 3 people in which no handshakes occurred.

      Case 3: Exactly two pairs of people in the group E, F, G shook hands

      Suppose E and F shook and E and G shook (recognizing that the argument holds when choosing any two pairs from E, F, G).
      In this case, F and G and one of A, B, C, D is a group of 3 people in which no handshakes occurred.
      Therefore, 8 or fewer handshakes is not possible, and so $m=9$.