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)
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
A grid with 12 rows and 15 columns has \(12\times15=180\) pieces.
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\times2=8\) middle pieces.
Solution 2
A grid with 6 rows and 4 columns has \(6\times4=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.
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\times16=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\times9=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.
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\times3(c-2)\) or \(5c=6(c-2)\). Solving, we get \(5c=6c-12\) and so \(c=12\).
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.
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).
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\times80\), \(324=4\times81\), and \(328=4\times82\).
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.
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 \(\dfrac12\times a\times
a\).
Solving \(\dfrac12 a^2=32\), we get
\(a^2=64\), and so \(a=8\) (since \(a>0\)).
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 \(\dfrac{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=\dfrac12\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=\dfrac12\times 10\times
20=100\).
The area of the trapezoid is \(T=A-B\) or \(T=100-16\) which is 84.
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 \(\dfrac{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 \(\dfrac12\times
c\times 3c=\dfrac12\times 3c^2\).
The area of the trapezoid is 8 times the area of the new
triangle.
Solving, we get \[\begin{align*}
\dfrac{21-c}{2}(63+3c)&=8\times\dfrac12\times 3c^2 \\
(21-c)(63+3c)&=8\times3c^2 \\
(21-c)(21+c)&=8\times c^2 \\
441-c^2&=8c^2 \\
441&=9c^2 \\
c^2&=49\end{align*}\] 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=\dfrac12\times 21\times 63=\dfrac{1323}{2}\).
The line \(x=c\) intersects the line
\(y=3x\) at the point \((c,3c)\).
Thus, \(B=\dfrac12\times c\times
3c=\dfrac{3c^2}{2}\).
Substituting into \(9B=A\) and solving,
we get \[\begin{align*}
9\times\dfrac{3c^2}{2}&=\dfrac{1323}{2} \\
27c^2&=1323 \\
c^2&=49\end{align*}\] and so \(c=7\) (since \(c>0\)).
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 \(\dfrac{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 \(\dfrac12\times
p\times 4p=\dfrac12\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{align*}
\dfrac{1-p}{2}(4+4p)&=\dfrac12\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&=\dfrac12\end{align*}\] and so \(p=\dfrac{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=\dfrac{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 \(\dfrac{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 \(\dfrac12\times
q\times 4q=\dfrac12\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{align*}
\dfrac{p-q}{2}(4p+4q)&=\dfrac12\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&=\dfrac12\times p^2\end{align*}\] and so \(q=\dfrac{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=\dfrac{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(\dfrac{1}{\sqrt{2}}\right)^{12}\)
or \(x=\left(\left(\dfrac{1}{\sqrt{2}}\right)^{2}\right)^{\!\!6}\)
or \(x=\left(\dfrac{1}{2}\right)^{6}\),
and so \(k=\dfrac{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 \(\dfrac12\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 \(\dfrac12\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=\dfrac{1}{2}\), and so \(p=\dfrac{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=\dfrac{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 \(\dfrac12\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=\dfrac{2p^2}{2}\) or \(q^2=\dfrac12\times p^2\), and so \(q=\dfrac{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=\dfrac{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(\dfrac{1}{\sqrt{2}}\right)^{\!\!12}\)
or \(x=\left(\left(\dfrac{1}{\sqrt{2}}\right)^{\!\!2}\right)^{\!\!6}\)
or \(x=\left(\dfrac{1}{2}\right)^{\!\!6}\), and
so \(k=\dfrac{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 \(\dfrac12\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(\dfrac12\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 \(\dfrac12\times 1\times 4=2\).
Equating the areas and solving for \(k\), we get \[\begin{align*} 2k^2&=\left(\dfrac12\right)^{12}\times 2 \\ k^2&=\left(\dfrac12\right)^{12} \\ k&=\left(\dfrac12\right)^{6}\end{align*}\] and so \(k=\dfrac{1}{64}\).
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\div2\).
Thus, the total number of handshakes that took place was \(8\div2=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.
As in part (a) Solution 1, if 9 people each shook hands with
exactly 3 people, then \(S=9\times3=27\), and the total number of
handshakes was \(N=27\div2=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.
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\leq8\).
Since each handshake occurs between 2 people and \(N\leq8\), then \(S\) is at most \(8\times2=16\).
If each of the 7 people shook 3 or more hands, then \(S\) would be at least \(7\times3=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\).