2016 Galois Contest
Solutions
(Grade 10)

Thursday, April 13, 2016
(in North America and South America)

Friday, April 14, 2016
(outside of North American and South America)

©2016 University of Waterloo

1. 1. The first bucket contains 7 red discs.

      Each bucket after the first contains 3 more red discs than the previous bucket.

      Thus, the second bucket contains $7+3=10$ red discs, the third bucket contains $10+3=13$ red discs, and the fourth bucket contains $13+3=16$ red discs.

   2. Solution 1

      Let $b$ represent the number of buckets after the first.

      Since the first bucket contains 17 green discs and each bucket after the first contains 1 more green disc than the previous bucket, then there are $17+b$ green discs inside the bucket $b$ after the first.

      Since the first bucket contains 7 red discs and each bucket after the first contains 3 more red discs than the previous bucket, then there are $7+3b$ red discs inside the bucket $b$ after the first.

      The number of green discs in a bucket is equal to the number of red discs inside the same bucket when $17+b=7+3b$ or when $2b=10$, and so when $b=5$.

      Thus, there are an equal number of red discs and green discs in the bucket 5 after the first bucket, which is the 6${}^{th}$ bucket.

      Solution 2

      Using the fact that the first bucket contains 17 green discs and 7 red discs, and each bucket after the first contains 1 more green disc and 3 more red discs than the previous bucket, then we may summarize the number of green and red discs inside each bucket.

      Bucket Number	Number of green discs	Number of red discs
      1	17	7
      2	18	10
      3	19	13
      4	20	16
      5	21	19
      6	22	22

      Therefore, the 6${}^{th}$ bucket contains an equal number of red discs and green discs.

      (Note that since the number of red discs is increasing by 3 each bucket and the number of green discs is increasing by 1 each bucket, then this is the only bucket in which the number of red discs and green discs will be equal.)

      Solution 3

      In the first bucket, there are 17 green discs and 7 red discs. Each bucket after the first contains 1 more green disc and 3 more red discs than the previous bucket.

      Since there are 2 more red discs than green being put in, then the difference between the numbers of green and red discs will decrease by 2 for each bucket after the first.

      Since the original difference is $17-7=10$, then it takes $10÷2=5$ more buckets to arrive at a bucket where the numbers of green and red discs will be equal.

      Therefore, the 6${}^{th}$ bucket contains an equal number of red discs and green discs.

   3. As in part (b), there are $17+b$ green discs and $7+3b$ red discs inside the bucket $b$ after the first.

      The number of red discs in a bucket is equal to twice the number of green discs inside the same bucket when $7+3b=2(17+b)$ or when $7+3b=34+2b$, and so when $b=27$.

      In the 27${}^{th}$ bucket after the first (the 28${}^{th}$ bucket), there are $17+27=44$ green discs and $7+3(27)=88$ red discs. (We note that 88 is indeed twice 44.)

      The total number of discs in this bucket is $44+88=132$.

2. 1. A plate with 36 shaded squares has 10 shaded squares along each side of the plate, as shown.

      

      We can see this from the diagram, or by considering a plate with $s$ squares along each side.

      In this case, we can count $s$ squares on the top edge and $s$ squares on the bottom edge, plus $s-2$ new squares on each of the left edge and the right edge. (The 2 corner squares on each of these edges are already counted.)

      This means that there are $2s+2(s-2)=4s-4$ squares along the edges.

      Here, we want $4s-4=36$ or $4s=40$, and so $s=10$.

      There are 10 squares along each side of the plate and the side length of the square plate is 60 cm, thus the side length of each of the shaded squares is $\frac{60}{10}=6$ cm.

   2. Since the plate is a square, and there are an equal number of identical shaded squares along each edge of the plate, then the unshaded area in the centre of the plate is also a square.

      The area of this unshaded square in the centre of the plate is 1600 cm${}^2$, and so each of its sides has length $\sqrt{1600}=40$ cm, as shown.

      Consider the row of squares along the left edge of the plate.

      Since the side length of the square plate is 60 cm and the side length of the inner square is 40 cm, then the sum of the side lengths of the two shaded corner squares is $60-40=20$ cm.

      Therefore, each shaded corner square (and thus each shaded square) has side length $\frac{20}{2}=10$ cm.

      

   3. Using the same argument as in part (b), the area of the unshaded square in the centre of the plate is 2500 cm${}^2$, and so each of its sides has length $\sqrt{2500}=50$ cm, as shown.

      The side length of the square plate is 60 cm and so the sum of the side lengths of 4 shaded squares (2 stacked vertically in the top two rows and 2 stacked vertically in the bottom two rows) is $60-50=10$ cm.

      Therefore, each of these shaded squares (and thus each shaded square on the plate) has side length $\frac{10}{4}=\frac{5}{2}$ cm.

      

      The side length of the square plate is 60 cm and each shaded square has length $\frac{5}{2}$ cm, and so along an outside edge of the plate there are $60÷\frac{5}{2}=60\times \frac{2}{5}=12\times 2=24$ shaded squares.

      There are 2 rows that each contain 24 shaded squares along each of the top and bottom of the square, and 2 additional rows that each contain $24-4=20$ shaded squares along the left and right sides of the square.

      That is, the total number of shaded squares on the plate is$4\times 24+4\times 20=96+80=176$.

3. 1. Triangle $ABC$ is equilateral with side length 6, and so $AB=BC=CA=6$.

      Since $D$ is the midpoint of $BC$, then $BD=DC=3$.

      In $\mathrm{△}ADC$, $\mathrm{\angle }ADC={90}^{\circ }$ and so by the Pythagorean Theorem $A{D}^2=A{C}^2-D{C}^2$.

      Therefore, $h^2=6^2-3^2=36-9=27$ and so $h=\sqrt{27}=\sqrt{9\times 3}=\sqrt{9}\times \sqrt{3}=3\sqrt{3}$,since $h>0$.

   2. The shaded region lies inside the circle and outside the hexagon and thus its area is determined by subtracting the area of the hexagon from the area of the circle.

      First we find the area of the hexagon.

      Each vertex of hexagon $EFGHIJ$ lies on the circle.

      Since the circle has centre $O$ and radius 6, then $OE=OF=OG=OH=OI=OJ=6$.

      Each side length of the hexagon is also 6, and so the hexagon is formed by six congruent equilateral triangles with side length 6. (For example, $\mathrm{△}OGH$ is one these 6 triangles.)

      Each of these triangles is congruent to $\mathrm{△}ABC$ from part (a) and thus has height $h=3\sqrt{3}$.

      The area of each of the six congruent triangles is $\frac{1}{2}(6)(3\sqrt{3})=9\sqrt{3}$.

      Therefore, the area of hexagon $EFGHIJ$ is $6\times 9\sqrt{3}=54\sqrt{3}$.

      The area of the circle with centre $O$ and radius 6 is $\pi (6{)}^2=36\pi$.

      Finally, the area of the shaded region is $36\pi -54\sqrt{3}$.

   3. Let the area of the shaded region that we are required to find be $A$.

      Let the area of the shaded region in the diagram to the right be $S$.

      

      We may determine $A$ by subtracting $S$ from the area of the semi-circle with centre $P$.

      First we determine $S$.

      Consider the circle with centre $O$. The shaded region having area $S$ lies inside sector $MON$ of this circle, but outside $\mathrm{△}MON$.

      That is, $S$ is determined by subtracting the area of $\mathrm{△}MON$ from the area of sector $MON$.

      In $\mathrm{△}MON$, $MN=ON=OM=r$ (since $ON$ and $OM$ are radii), and so the triangle is equilateral. Join $O$ to $P$.

      Since $ON=OM$ and $P$ is the midpoint of $MN$, then $OP$ is the altitude (height) of $\mathrm{△}MON$ with base $MN$.

      In $\mathrm{△}OPN$, $\mathrm{\angle }OPN={90}^{\circ }$ and so by the Pythagorean Theorem $O{P}^2=O{N}^2-P{N}^2$.

      Since $PN=\frac{1}{2}(MN)=\frac{1}{2}r$, $O{P}^2=r^2-(\frac{1}{2}r{)}^2=r^2-\frac{1}{4}{r}^2=\frac{3}{4}{r}^2$, and so $OP=\sqrt{\frac{3}{4}{r}^2}=\frac{\sqrt{3}}{2}r$.

      Therefore, the area of $\mathrm{△}MON$ is $\frac{1}{2}(MN)(OP)=\frac{1}{2}(r)\left(\frac{\sqrt{3}}{2}r\right)=\frac{\sqrt{3}}{4}{r}^2$.

      Next, we determine the area of sector $MON$.

      Since $\mathrm{△}MON$ is equilateral, then $\mathrm{\angle }MON={60}^{\circ }$.

      Thus, the area of sector $MON$ is $\frac{{60}^{\circ }}{{360}^{\circ }}=\frac{1}{6}$ of the area of the circle with centre $O$ and radius $r$, or $\frac{1}{6}\pi r^2$.

      Therefore, $S=\frac{1}{6}\pi r^2-\frac{\sqrt{3}}{4}{r}^2$.

      Finally, one-half of the area of the circle with centre $P$ and radius $PN=\frac{1}{2}r$ is$\frac{1}{2}\pi {\left(\frac{1}{2}r\right)}^2=\frac{1}{8}\pi r^2$, and so $A=\frac{1}{8}\pi r^2-S=\frac{1}{8}\pi r^2-(\frac{1}{6}\pi r^2-\frac{\sqrt{3}}{4}{r}^2)=(\frac{1}{8}\pi -\frac{1}{6}\pi +\frac{\sqrt{3}}{4})r^2$.

      Simplifying further, the exact area of the shaded region is $\frac{6\sqrt{3}-\pi }{24}{r}^2$.

4. 1. The prime factorization of $126$ is $126=2^1{3}^2{7}^1$.

      Given an input of $126=2^1{3}^2{7}^1$, the output from the Barbeau Process is $$126(\frac{1}{2}+\frac{2}{3}+\frac{1}{7})=126\left(\frac{21+28+6}{42}\right)=3(55)=165.$$

   2. Given an input of $p^{2}q$, the output from the Barbeau Process is $p^{2}q({\displaystyle \frac{2}{p}}+{\displaystyle \frac{1}{q}})=2pq+p^2$.

      We are told that this output is equal to 135.

      Since $135=3^{3}5$, then $2pq+p^2=3^{3}5$ or $p(2q+p)=3^{3}5$.

      Since $p$ is a prime number that is a divisor of $3^{3}5$, then $p=3$ or $p=5$.

      If $p=3$, then $3(2q+3)=3^{3}5$ or $2q+3=45$ and so $q=21$.

      However $q$ is a prime number and 21 is not a prime number, so $p\ne 3$.

      If $p=5$, then $5(2q+5)=3^{3}5$ or $2q+5=27$ and so $q=11$.

      Therefore, the only pair $(p,q)$ of different prime numbers that satisfies the given conditions is $(5,11)$.

   3. Solution 1

      Given an input of $2^a{3}^b{5}^c$, the output from the Barbeau Process is $$2^a{3}^b{5}^c(\frac{a}{2}+\frac{b}{3}+\frac{c}{5})=2^a{3}^b{5}^c\left(\frac{15a+10b+6c}{30}\right).$$ We are told that this output is equal to $4\times 2^a{3}^b{5}^c$.

      Comparing these gives ${\displaystyle \frac{15a+10b+6c}{30}}=4$ or $15a+10b+6c=120$.

      Since $a,b,c$ are positive integers, and $15\times 8=120$, $10\times 12=120$, and $6\times 20=120$, then $1\le a\le 7,1\le b\le 11,$ and $1\le c\le 19$.

      Further, $10b,6c$ and 120 are divisible by 2, and so $15a=120-10b-6c$ is divisible by 2.

      Therefore, $a$ is divisible by 2 and since $1\le a\le 7$, then $a$ equals $2,4$ or 6.

      Similarly, $15a,6c$, and 120 are divisible by 3, and so $10b$ is divisible by 3.

      Therefore, $b$ is divisible by 3 and since $1\le b\le 11$, then $b$ equals $3,6$ or 9.

      Finally, $15a,10b$, and 120 are divisible by 5, and so $6c$ is divisible by 5.

      Therefore, $c$ is divisible by 5 and since $1\le c\le 19$, then $c$ equals $5,10$ or 15.

      Since $a\ge 2,b\ge 3,$ and $c\ge 5$, then $15a\ge 15\times 2=30,10b\ge 10\times 3=30,$ and $6c\ge 6\times 5=30$.

      That is, each of the terms $15a,10b,6c$ is at least 30, and so each of the terms is at most $120-2(30)=60$ (for example, $15a=120-10b-6c\le 120-30-30=60$).

      Therefore, $15a\le 60$ and so $a$ is equal to 2 or 4, $10b\le 60$ and so $b$ is equal to 3 or 6, and $6c\le 60$ and so $c$ is equal to 5 or 10.

      If $a=2$ and $b=3$, then $6c=120-15(2)-10(3)=60$, and so $c=10$.

      If $a=2$ and $b=6$, then $6c=120-15(2)-10(6)=30$, and so $c=5$.

      If $a=4$ and $b=3$, then $6c=120-15(4)-10(3)=30$, and so $c=5$.

      If $a=4$ and $b=6$, then $6c=120-15(4)-10(6)=0$, which is not possible.

      Therefore, the triples $(a,b,c)$ of positive integers which satisfy the given conditions are $(2,3,10),(2,6,5),$ and $(4,3,5)$.

      Solution 2

      Given an input of $2^a{3}^b{5}^c$, the output from the Barbeau Process is $$2^a{3}^b{5}^c(\frac{a}{2}+\frac{b}{3}+\frac{c}{5})=2^a{3}^b{5}^c\left(\frac{15a+10b+6c}{30}\right).$$ We are told that this output is equal to $4\times 2^a{3}^b{5}^c$.

      Comparing these gives ${\displaystyle \frac{15a+10b+6c}{30}}=4$ or $15a+10b+6c=120$.

      Since $10b$, $6c$ and 120 are divisible by 2 and $15a=120-10b-6c$, then $15a$ is divisible by 2 which means that $a$ is divisible by 2. Thus, we set $a=2A$ for some positive integer $A$.

      Since $15a$, $6c$ and 120 are divisible by 3 and $10b=120-15a-6c$, then $10b$ is divisible by 3 which means that $b$ is divisible by 3. Thus, we set $b=3B$ for some positive integer $B$.

      Since $15a$, $10b$ and 120 are divisible by 5 and $6c=120-15a-10b$, then $6c$ is divisible by 5 which means that $c$ is divisible by 5. Thus, we set $c=5C$ for some positive integer $C$.

      Therefore, the equation $15a+10b+6c=120$ becomes $30A+30B+30C=120$ or $A+B+C=4$.

      Since $A$, $B$ and $C$ are positive integers that add to 4, the possible values for $(A,B,C)$ are $(2,1,1)$, $(1,2,1)$, and $(1,1,2)$, because each is at least 1 which only leaves 1 “left over” to make up the total of 4.

      Since $(a,b,c)=(2A,3B,5C)$, then the possible triples $(a,b,c)$ are $(4,3,5)$, $(2,6,5)$, and $(2,3,10)$.

   4. We proceed in a number of steps.

      Step 1: Each exponent in the prime factorization must be a multiple of its prime

      We show that, since the output is an integer multiple of the input, each exponent in the prime factorization must be an integer multiple of its corresponding prime.

      This generalizes what we found in Solution 2 to part (c).

      In other words, suppose that $n=p_1^{a_1}{p}_2^{a_2}{p}_3^{a_3}\dots p_k^{a_k}$ where $p_1,p_2,...,p_k$ are different prime numbers and $a_1,a_2,...,a_k$ are integers that are each at least 0.

      By definition, the output of the Barbeau Process is $n({\displaystyle \frac{a_1}{p_1}}+{\displaystyle \frac{a_2}{p_2}}+{\displaystyle \frac{a_3}{p_3}}+\cdots +{\displaystyle \frac{a_k}{p_k}})$.

      Note that we are allowing each of $a_1,a_2,\dots ,a_k$ to be 0, which does not affect the value of the output.

      Here, we are told that the output of the Barbeau process is $3n$.

      Therefore, $n({\displaystyle \frac{a_1}{p_1}}+{\displaystyle \frac{a_2}{p_2}}+{\displaystyle \frac{a_3}{p_3}}+\cdots +{\displaystyle \frac{a_k}{p_k}})=3n$ or ${\displaystyle \frac{a_1}{p_1}}+{\displaystyle \frac{a_2}{p_2}}+{\displaystyle \frac{a_3}{p_3}}+\cdots +{\displaystyle \frac{a_k}{p_k}}=3$.

      Rearranging, we obtain ${\displaystyle \frac{a_1}{p_1}}=3-{\displaystyle \frac{a_2}{p_2}}-{\displaystyle \frac{a_3}{p_3}}-\cdots -{\displaystyle \frac{a_k}{p_k}}$.

      Multiplying both sides by $p_2{p}_3\cdots p_k$, we obtain $${\displaystyle \frac{a_1{p}_2{p}_3\cdots p_k}{p_1}}=3p_2{p}_3\cdots p_k-a_2{p}_3\cdots p_k-a_3{p}_2{p}_4\cdots p_k-\cdots -a_k{p}_2{p}_3\cdots p_{k-1}$$ Since every term on the right side is an integer, then ${\displaystyle \frac{a_1{p}_2{p}_3\cdots p_k}{p_1}}$ must be an integer.

      Since the prime numbers $p_1,p_2,\dots ,p_k$ are all distinct, then $a_1$ must be a multiple of $p_1$ to make this fraction actually equal an integer.

      A similar argument will show that $a_2$ is a multiple of $p_2$, $a_3$ is a multiple of $p_3$, and so on.

      Step 2: $n$ does not have any prime factor larger than 7

      Suppose that $n$ does have a prime factor that is larger than 7.

      In other words, suppose that $n$ has a prime factor $p_i$ that is at least 11.

      In this case, the factor $p_i^{a_i}$ in the prime factorization of $n$ is at least ${11}^{11}$ since $p_i\ge 11$ and $a_i$ is a multiple of $p_i$ and so must also be at least 11.

      In this case, $n\ge {11}^{11}$.

      But $n$ is restricted to be less than ${10}^{10}$, so this is not possible.

      Therefore, $n$ does not have any prime factor larger than 7.

      Step 3: Simplifying the algebra

      Combining Steps 1 and 2, $n$ must be of the form $n=2^a{3}^b{5}^c{7}^d$ for some non-negative integers $a$, $b$, $c$, and $d$ that are multiples of $2$, $3$, $5$, and $7$, respectively.

      As in Solution 2 to part (c), we set $a=2A$, $b=3B$, $c=5C$, and $d=7D$ for some non-negative integers $A,B,C,D$.

      Therefore, the equation ${\displaystyle \frac{a_1}{p_1}}+{\displaystyle \frac{a_2}{p_2}}+{\displaystyle \frac{a_3}{p_3}}+\cdots +{\displaystyle \frac{a_k}{p_k}}=3$ becomes ${\displaystyle \frac{a}{2}}+{\displaystyle \frac{b}{3}}+{\displaystyle \frac{c}{5}}+{\displaystyle \frac{d}{7}}=3$, which becomes $A+B+C+D=3$.

      Therefore, we want to find all of the non-negative integer solutions to $A+B+C+D=3$ which give $n=2^{2A}{3}^{3B}{5}^{5C}{7}^{7D}<{10}^{10}$.

      Step 4: Restrictions on $A,B,C,D$

      Since $A+B+C+D=3$ and each of $A,B,C,D$ is non-negative, then each of $A,B,C,D$ is at most 3.

      If $D=2$ or $D=3$, then $n$ is divisible by $7^{14}$ or $7^{21}$, each of which is larger than ${10}^{10}$.

      Therefore, $D\le 1$.

      If $C=3$, then $n$ is divisible by $5^{15}$, which is larger than ${10}^{10}$.

      Therefore, $C\le 2$.

      Step 5: Determining the values of $n$

      Since $A+B+C+D=3$ and each of $A,B,C,D$ is non-negative, then $A,B,C,D$ could be (i) $3,0,0,0$ in some order, or (ii) $2,1,0,0$ in some order, or (iii) $1,1,1,0$, in some order.

      (If one value is 3, the rest must be 0. If one value is 2, then there must be one 1 and two 0s. If no value is 2, then there must be three 1s and one 0.)

      Using the facts that $C\le 2$ and $D\le 1$, we enumerate the possibilities:

      Category	$\mathit{A}$	$\mathit{B}$	$\mathit{C}$	$\mathit{D}$	$\mathit{n}$	Less than ${10}^{10}$?
      (i)	3	0	0	0	$2^6$	Yes
      (i)	0	3	0	0	$3^9$	Yes
      (ii)	2	1	0	0	$2^4{3}^3$	Yes
      (ii)	2	0	1	0	$2^4{5}^5$	Yes
      (ii)	2	0	0	1	$2^4{7}^7$	Yes
      (ii)	1	2	0	0	$2^2{3}^6$	Yes
      (ii)	0	2	1	0	$3^6{5}^5$	Yes
      (ii)	0	2	0	1	$3^6{7}^7$	Yes
      (ii)	1	0	2	0	$2^2{5}^{10}$	Yes
      (ii)	0	1	2	0	$3^3{5}^{10}$	Yes
      (ii)	0	0	2	1	$5^{10}{7}^7$	No
      (iii)	1	1	1	0	$2^2{3}^3{5}^5$	Yes
      (iii)	1	1	0	1	$2^2{3}^3{7}^7$	Yes
      (iii)	1	0	1	1	$2^2{5}^5{7}^7$	No
      (iii)	0	1	1	1	$3^3{5}^5{7}^7$	No

      In each case, we can check whether the possible value of $n$ is smaller than ${10}^{10}$ using a calculator. (Which of these calculations can you “reason” through without using a calculator?)

      In summary, the possible values of $n$ are $$2^6,3^9,2^4{3}^3,2^4{5}^5,2^4{7}^7,2^2{3}^6,3^6{5}^5,3^6{7}^7,2^2{5}^{10},3^3{5}^{10},2^2{3}^3{5}^5,2^2{3}^3{7}^7$$