2017 Galois Contest
Solutions
(Grade 10)

Wednesday, April 12, 2017
(in North America and South America)

Thursday, April 13, 2017
(outside of North American and South America)

©2017 University of Waterloo

1. 1. In Box E, 6 of the 30 cups were purple.

      The percentage of purple cups in Box E was ${\displaystyle \frac{6}{30}}\times 100\mathrm{\%}={\displaystyle \frac{2}{10}}\times 100\mathrm{\%}=20\mathrm{\%}$.

   2. On Monday, 30% of Daniel’s 90 cups or $30\mathrm{\%}\times 90={\displaystyle \frac{30}{100}}\times 90=27$ cups were purple.

      Daniel had 9 purple cups in Box D and 6 purple cups in Box E.

      Therefore, the number of purple cups in Box F was $27-9-6=12$.

   3. Daniel had 27 purple cups and 90 cups in total.

      On Tuesday, Avril added 9 more purple cups to Daniel’s cups, bringing the number of purple cups to $27+9=36$, and the total number of cups to $90+9=99$.

      Barry brought some yellow cups and included them with the 99 cups.

      Let the number of yellow cups that Barry brought be $y$.

      The total number of cups was then $99+y$, while the number of purple cups was still 36 (since Barry brought yellow cups only).

      Since the percentage of cups that were purple was again 30% or ${\displaystyle \frac{30}{100}}$, then ${\displaystyle \frac{30}{100}}$ of $99+y$ must equal 36.

      Solving, we get ${\displaystyle \frac{30}{100}}\times (99+y)=36$ or $30(99+y)=3600$ or $99+y=120$, and so $y=21$.

      Therefore, Barry brought 21 cups.

2. 1. Abdi arrived at 5:02 a.m., and so Abdi paid $5.02.

      Caleigh arrived at 5:10 a.m., and so Caleigh paid $5.10.

      In total, Abdi and Caleigh paid $\mathrm{\$}5.02+\mathrm{\$}5.10=\mathrm{\$}10.12$.

   2. If both Daniel and Emily had arrived at the same time, then they each would have paid the same amount, or $\mathrm{\$}12.34÷2=\mathrm{\$}6.17$.

      In this case, they would have both arrived at 6:17 a.m.

      If Daniel arrived 5 minutes earlier, at 6:12 a.m., and Emily arrived 5 minutes later, at 6:22 a.m., then they would have arrived 10 minutes apart and in total they would have still paid $12.34.

      (We may check that these arrival times are 10 minutes apart, and that Daniel and Emily’s total price is $\mathrm{\$}6.12+\mathrm{\$}6.22=\mathrm{\$}12.34$, as required.)

   3. To minimize the amount that Karla could have paid, we maximize the amount that Isaac and Jacob pay.

      Isaac and Jacob arrived together and Karla arrived after.

      Since Karla arrived at a later time than Isaac and Jacob, then Karla paid more than Isaac and Jacob.

      If Isaac and Jacob both arrived together at 6:18 a.m., then they would each have paid $6.18, and Karla would have paid $\mathrm{\$}18.55-\mathrm{\$}6.18-\mathrm{\$}6.18=\mathrm{\$}6.19$.

      This is the minimum amount that Karla could have paid. Why?

      If Isaac and Jacob arrived at 6:19 a.m. or later, then Karla would have arrived at a time earlier than 6:19 a.m. (since $\mathrm{\$}18.55-\mathrm{\$}6.19-\mathrm{\$}6.19=\mathrm{\$}6.17$).

      Since Karla arrived after Isaac and Jacob, this is not possible.

      If Isaac and Jacob arrived earlier than 6:18 a.m., then they would have each paid less than $6.18, and so Karla would have paid more than $6.19.

      Therefore, the minimum amount that Karla could have paid is $6.19.

   4. If Larry arrived earlier than 5:39 a.m., then he would have paid less than $5.39 and so Mio would have paid more than $\mathrm{\$}11.98-\mathrm{\$}5.39=\mathrm{\$}6.59$.

      Since Mio arrived during the time of the special pricing, it is not possible for Mio to have paid more than $6.59, and so Larry must have arrived at 5:39 a.m. or later.

      If Larry arrived between 5:39 a.m. and 5:59 a.m. (inclusive), then Larry would have paid the amount between $5.39 and $5.59 corresponding to his arrival time.

      Therefore, Mio would have paid an amount between $\mathrm{\$}11.98-\mathrm{\$}5.59=\mathrm{\$}6.39$ and $\mathrm{\$}11.98-\mathrm{\$}5.39=\mathrm{\$}6.59$ (inclusive).

      Each of the amounts between $6.39 and $6.59 corresponds to an arrival time for Mio between 6:39 a.m. and 6:59 a.m., each of which is a possible time that Mio could have arrived during the special pricing period.

      That is, each arrival time for Larry from 5:39 a.m. to 5:59 a.m. corresponds to an arrival time for Mio from 6:39 a.m. to 6:59 a.m.

      Each of these times is during the period of the special pricing and each corresponding pair of times gives a total price of $11.98.

      To see this, consider that if Larry arrived $x$ minutes after 5:39 a.m. (where $x$ is an integer and $0\le x\le 20$), then Mio arrived $x$ minutes before 6:59 a.m., and in total they paid $\mathrm{\$}5.39+x$ $+\mathrm{\$}6.59-x$ $=\mathrm{\$}11.98$.

      Since Larry’s arrival time and Mio’s arrival time may be switched to give the same total, $11.98, then Larry could also have arrived between 6:39 a.m. and 6:59 a.m.

      The only times left to consider are those from 6:00 a.m. to 6:38 a.m.

      If Larry arrived at one of these times, his price would have been between $6.00 and $6.38, and so Mio’s price would have been between $\mathrm{\$}11.98-\mathrm{\$}6.38=\mathrm{\$}5.60$ and $\mathrm{\$}11.98-\mathrm{\$}6.00=\mathrm{\$}5.98$.

      Since there are no arrival times which correspond to Mio having to pay an amount between $5.60 and $5.98, then it is not possible that Larry arrived at any time from 6:00 a.m. to 6:38 a.m.

      Therefore, the ranges of times during which Larry could have arrived are 5:39 a.m. to 5:59 a.m or 6:39 a.m. to 6:59 a.m.

3. 1. Since $\mathrm{\angle }OPQ={90}^{\circ }$, then $\mathrm{△}OPQ$ is a right-angled triangle.

      By the Pythagorean Theorem, $O{Q}^2=O{P}^2+P{Q}^2={18}^2+{24}^2=900$, and so $OQ=\sqrt{900}=30$ (since $OQ>0$).

      Line segment $OS$ is a radius of the circle and thus has length 18.

      Therefore, $SQ=OQ-OS=30-18=12$.

   2. Sides $AB,BC,CD,$ and $DA$ are tangent to the circle at points $E,F,G,$ and $H$, respectively.

      Therefore, radii $OE$, $OF$, $OG$, and $OH$ are perpendicular to their corresponding sides, as shown.

      In quadrilateral $DHOG$, $\mathrm{\angle }OGD=\mathrm{\angle }GDH=\mathrm{\angle }DHO={90}^{\circ }$ and so $\mathrm{\angle }GOH={90}^{\circ }$.

      Since $OH=OG=12$ (they are radii of the circle), then $DHOG$ is a square with side length 12.

      Similarly, $HAEO$ is also a square with side length 12.

      Since $\mathrm{\angle }OGC={90}^{\circ }$, then $\mathrm{△}OGC$ is a right-angled triangle.

      By the Pythagorean Theorem, $G{C}^2=O{C}^2-O{G}^2={20}^2-{12}^2=256$, and so $GC=\sqrt{256}=16$ (since $GC>0$).

      It can be similarly shown that $FC=16$.

      Since $\mathrm{\angle }OEB={90}^{\circ }$, then $\mathrm{△}OEB$ is a right-angled triangle.

      By the Pythagorean Theorem, $E{B}^2=O{B}^2-O{E}^2={15}^2-{12}^2=81$, and so $EB=\sqrt{81}=9$ (since $EB>0$).

      It can be similarly shown that $FB=9$.

      Therefore, the perimeter of $ABCD$ is $GD+DH+HA+AE+EB+BF+FC+CG$ or $4\times 12+2\times 9+2\times 16=98$.

      

   3. In Figure 1:

      Since the circles are inscribed in their respective squares, then $TU$ is a tangent to the larger circle and $UV$ is a tangent to the smaller circle.

      Let $TU$ touch the larger circle at $W$, and let $UV$ touch the smaller circle at $X$.

      The radius $OW$ is perpendicular to $TU$, and the radius $CX$ is perpendicular to $UV$.

      

      In Figure 2:

      The diameter of the larger circle is equal to the side length of the larger square.

      To see this, label the points $P$ and $R$ where the vertical sides of the larger square touch the larger circle.

      Join $P$ to $O$ and join $R$ to $O$.

      The radius $OP$ is perpendicular to $PT$ and the radius $OR$ is perpendicular to $RU$.

      In quadrilateral $PTWO$, $\mathrm{\angle }OPT=\mathrm{\angle }PTW=\mathrm{\angle }TWO={90}^{\circ }$, and so $\mathrm{\angle }POW={90}^{\circ }$.

      Similarly, in quadrilateral $RUWO$, $\mathrm{\angle }ROW={90}^{\circ }$.

      Therefore, $\mathrm{\angle }POW+\mathrm{\angle }ROW={180}^{\circ }$ and so $PR$ passes through $O$ and is thus a diameter of the larger circle.

      In quadrilateral $PTUR$, all 4 interior angles measure ${90}^{\circ }$, and so $PTUR$ is a rectangle.

      It can similarly be shown that if $S$ and $Q$ are the points where the vertical sides of the smaller square touch the smaller circle, then $SQ$ is a diameter of the smaller circle and $SUVQ$ is a rectangle.

      

      In Figure 3:

      The area of the larger square is 289, and so each side of the larger square has length $\sqrt{289}=17$.

      The diameter of the larger circle is equal to the side length of the larger square, or $PR=TU=17$.

      Since $O$ is the midpoint of $PR$, and $OW$ is perpendicular to $TU$, then $W$ is the midpoint of $TU$.

      Therefore, $WU=OR=OW=17÷2=8.5$.

      The area of the smaller square is 49, and so each side of the smaller square has length $\sqrt{49}=7$.

      Similarly, $X$ is the midpoint of $UV$ and so $UX=SC=CX=7÷2=3.5$.

      

      In Figure 4:

      Finally, we construct the line segment from $C$, parallel to $XW$, and meeting $OW$ at $Y$.

      In quadrilateral $YWXC$, $CY$ is parallel to $XW$, $YW$ is perpendicular to $XW$, and $CX$ is perpendicular to $XW$, and so $YWXC$ is a rectangle.

      Thus, $CX=YW=3.5$, and

      $CY=XW=XU+WU=3.5+8.5=12$.

      Since $\mathrm{\angle }OYC={90}^{\circ }$, then $\mathrm{△}OYC$ is a right-angled triangle with $CY=12$, and $OY=OW-YW=8.5-3.5=5$.

      

      By the Pythagorean Theorem, $O{C}^2=C{Y}^2+O{Y}^2={12}^2+5^2=144+25=169$, and so $OC=\sqrt{169}=13$ (since $OC>0$).

4. 1. The total area of the $m=14$ by $n=10$ Koeller-rectangle is $m\times n=14\times 10=140$.

      The dimensions of the shaded area inside a Koeller-rectangle are $(m-2)$ by $(n-2)$ since the 1 by 1 squares along the sides are unshaded, so each dimension is reduced by 2.

      Therefore, the shaded area of a 14 by 10 Koeller-rectangle is $(14-2)\times (10-2)=12\times 8=96$.

      The unshaded area is the difference between the total area and the shaded area, or $mn-(m-2)(n-2)=mn-(mn-2m-2n+4)=2m+2n-4$ or $2\times 14+2\times 10-4=44$.

      Finally, $r$ is the ratio of the shaded area to the unshaded area, or ${\displaystyle \frac{96}{44}}={\displaystyle \frac{24}{11}}$ (or $24:11$).

   2. As we saw in part (a), the shaded area of an $m$ by $n$ Koeller-rectangle is $(m-2)(n-2)$, and the unshaded area is $2m+2n-4$.

      Therefore, $r={\displaystyle \frac{(m-2)(n-2)}{2m+2n-4}}$. When $n=4$, $r={\displaystyle \frac{2(m-2)}{2m+4}}={\displaystyle \frac{2(m-2)}{2(m+2)}}={\displaystyle \frac{m-2}{m+2}}$.

      We rewrite ${\displaystyle \frac{m-2}{m+2}}$ as ${\displaystyle \frac{m+2-4}{m+2}}={\displaystyle \frac{m+2}{m+2}}-{\displaystyle \frac{4}{m+2}}=1-{\displaystyle \frac{4}{m+2}}$.

      We must determine all possible integer values of $u$ for which $r=1-{\displaystyle \frac{4}{m+2}}={\displaystyle \frac{u}{77}}$, for some integer $m\ge 3$.

      Simplifying this equation, we get $$\begin{array}{rl}1-{\displaystyle \frac{4}{m+2}}& ={\displaystyle \frac{u}{77}}\\ 1-{\displaystyle \frac{u}{77}}& ={\displaystyle \frac{4}{m+2}}\\ {\displaystyle \frac{77-u}{77}}& ={\displaystyle \frac{4}{m+2}}\\ (m+2)(77-u)& =4\times 77\end{array}$$

      Both $u$ and $m$ are integers, and so $(m+2)(77-u)$ is the product of two integers.

      If $a$ and $b$ are positive integers so that $ab=4\times 77=2^2\times 7\times 11$, then there are 6 possible factor pairs $(a,b)$ with $a<b$.

      These are: $(1,308),(2,154),(4,77),(7,44),(11,28),$ and $(14,22).$

      Since $m\ge 3$, then $m+2\ge 5$ and so $m+2$ cannot equal $1,2$ and $4$.

      However, $m+2$ can equal any of the remaining 9 divisors: $7,11,14,22,28,44,77,154,308$.

      In the table below, we determine the possible values for $u$ given that $(m+2)(77-u)=2^2\times 7\times 11$, and $m+2\ge 5$.

      $\mathit{m}\mathbf{+}\mathbf{2}$	7	11	14	22	28	44	77	154	308
      $\mathbf{77}\mathbf{-}\mathit{u}$	44	28	22	14	11	7	4	2	1
      $\mathit{u}$	33	49	55	63	66	70	73	75	76

      The integer values of $u$ for which there exists a Koeller-rectangle with $n=4$ and $r={\displaystyle \frac{u}{77}}$, are $u=33,49,55,63,66,70,73,75,76$.

      (For example, the 5 by 4 Koeller-rectangle has $r={\displaystyle \frac{m-2}{m+2}}={\displaystyle \frac{3}{7}}={\displaystyle \frac{33}{77}}$, and so $u=33$.)

   3. As in part (b), $r={\displaystyle \frac{(m-2)(n-2)}{2m+2n-4}}$, and when $n=10$, $r={\displaystyle \frac{8(m-2)}{2m+16}}={\displaystyle \frac{4(m-2)}{m+8}}$.

      Rearranging this equation, we get

      $$\begin{array}{rl}r& ={\displaystyle \frac{4(m-2)}{m+8}}\\ {\displaystyle \frac{r}{4}}& ={\displaystyle \frac{m-2}{m+8}}\\ {\displaystyle \frac{r}{4}}& ={\displaystyle \frac{m+8-10}{m+8}}\\ {\displaystyle \frac{r}{4}}& ={\displaystyle \frac{m+8}{m+8}}-{\displaystyle \frac{10}{m+8}}\\ {\displaystyle \frac{r}{4}}& =1-{\displaystyle \frac{10}{m+8}}\\ {\displaystyle \frac{10}{m+8}}& =1-{\displaystyle \frac{r}{4}}\\ {\displaystyle \frac{10}{m+8}}& =1-{\displaystyle \frac{u}{4p^2}}& \text{since }r={\displaystyle \frac{u}{p^2}}\\ {\displaystyle \frac{10}{m+8}}& ={\displaystyle \frac{4p^2-u}{4p^2}}\\ 40p^2& =(m+8)(4p^2-u)\end{array}$$

      Since $p,u$ and $m$ are integers, then $(m+8)(4p^2-u)$ is the product of two integers.

      We must determine all prime numbers $p$ for which there are exactly 17 positive integer values of $u$ for Koeller-rectangles satisfying this equation $40p^2=(m+8)(4p^2-u)$.

      For $p=2,3,5,7$, and then $p\ge 11$, we proceed with the following strategy:

      • determine the value of $40p^2$

      • count the number of divisors of $40p^2$

      • eliminate possible values of $m+8$, thus eliminating possible values of $4p^2-u$

      • count the number of values of $u$ by counting the number of values of $4p^2-u$

      If $p=2$, then $40p^2=40\times 2^2=2^5\times 5$, and so $2^5\times 5=(m+8)(16-u)$.

      Each divisor of $2^5\times 5$ is of the form $2^i\times 5^j$, for integers $0\le i\le 5$ and $0\le j\le 1$.

      That is, there are 6 choices for $i$ (each of the integers from 0 to 5) and 2 choices for $j$ (0 or 1), and so there are $6\times 2=12$ different divisors of $2^5\times 5$.

      Since $2^5\times 5=(m+8)(16-u)$, then there are at most 12 different integer values of $16-u$ (the 12 divisors of $2^5\times 5$), and so there are at most 12 different integer values of $u$.

      Therefore, when $p=2$, there cannot be exactly 17 positive integer values of $u$.

      If $p=5$, then $40p^2=40\times 5^2=2^3\times 5^3$, and so $2^3\times 5^3=(m+8)(100-u)$.

      Each divisor of $2^3\times 5^3$ is of the form $2^i\times 5^j$, for integers $0\le i\le 3$ and $0\le j\le 3$.

      That is, there are 4 choices for $i$ and 4 choices for $j$, and so there are $4\times 4=16$ different divisors of $2^3\times 5^3$.

      Since $2^3\times 5^3=(m+8)(100-u)$, then there are at most 16 different integer values of $100-u$, and so there are at most 16 different integer values of $u$.

      Therefore, when $p=5$, there cannot be exactly 17 positive integer values of $u$.

      If $p=3$, then $40p^2=40\times 3^2=2^3\times 3^2\times 5$, and so $2^3\times 3^2\times 5=(m+8)(36-u)$.

      Each divisor of $2^3\times 3^2\times 5$ is of the form $2^i\times 3^j\times 5^k$, for integers $0\le i\le 3$, $0\le j\le 2$, and $0\le k\le 1$.

      That is, there are $4\times 3\times 2=24$ different divisors of $2^3\times 3^2\times 5$.

      Since $m\ge 3$, then $m+8\ge 11$, and so the divisors of $2^3\times 3^2\times 5$ which $m+8$ cannot equal are: $1,2,3,4,5,6,8,9$, and 10.

      Since there are 9 divisors which $m+8$ cannot equal, then there are 9 divisors that $36-u$ cannot equal. (These divisors can be determined by dividing $2^3\times 3^2\times 5$ by each of the 9 divisors $1,2,3,4,5,6,8,9$, and 10.)

      So then there are $24-9=15$ different integer values of $36-u$, and so there are exactly 15 different integer values of $u$ when $p=3$.

      Therefore, there are not 17 positive integer values of $u$ when $p=3$.

      If $p=7$, then $40p^2=40\times 7^2=2^3\times 5\times 7^2$, and so $2^3\times 5\times 7^2=(m+8)(196-u)$.

      Each divisor of $2^3\times 5\times 7^2$ is of the form $2^i\times 5^j\times 7^k$, for integers $0\le i\le 3$, $0\le j\le 1$, and $0\le k\le 2$.

      That is, there are $4\times 2\times 3=24$ different divisors of $2^3\times 5\times 7^2$.

      Since $m+8\ge 11$, then the divisors of $2^3\times 5\times 7^2$ that $m+8$ cannot equal are: $1,2,4,5,7,8$, and 10.

      Since there are 7 divisors which $m+8$ cannot equal, then there are 7 divisors that $196-u$ cannot equal. (These divisors can be determined by dividing $2^3\times 5\times 7^2$ by each of the 7 divisors $1,2,4,5,7,8$, and 10. We also note that each of the remaining divisors that $196-u$ can equal, is less than 196, giving a positive integer value for $u$.)

      So then there are $24-7=17$ different integer values of $196-u$, and so there are exactly 17 different integer values of $u$ when $p=7$.

      For all remaining primes $p\ge 11$, we get $40p^2=2^3\times 5\times p^2$, and so $2^3\times 5\times p^2=(m+8)(4p^2-u)$.

      Since $p\ne 2$ and $p\ne 5$, each divisor of $2^3\times 5\times p^2$ is of the form $2^i\times 5^j\times p^k$, for integers $0\le i\le 3$, $0\le j\le 1$, and $0\le k\le 2$.

      That is, there are $4\times 2\times 3=24$ different divisors of $2^3\times 5\times p^2$.

      Since $m+8\ge 11$ and $p\ge 11$, then the divisors of $2^3\times 5\times p^2$ that $m+8$ cannot equal are: $1,2,4,5,8$, and 10.

      Since there are 6 divisors which $m+8$ cannot equal, then there are 6 divisors which $4p^2-u$ cannot equal. (These divisors can be determined by dividing $2^3\times 5\times p^2$ by each of the 6 divisors $1,2,4,5,8$, and 10. We also note that each of the remaining divisors that $4p^2-u$ can equal, is less than $4p^2$, giving a positive integer value for $u$.)

      So then there are $24-6=18$ different integer values of $4p^2-u$, and so there are exactly 18 different integer values of $u$ for all prime numbers $p\ge 11$.

      Therefore, $p=7$ is the only prime number for which there are exactly 17 positive integer values of $u$ for Koeller-rectangles with $n=10$ and $r={\displaystyle \frac{u}{p^2}}$.