2021 Euclid Contest
Solutions

Wednesday, April 7, 2021
(in North America and South America)

Thursday, April 8, 2021
(outside of North American and South America)

©2021 University of Waterloo

1. 1. Since $(a-1)+(2a-3)=14$, then $3a=18$ and so $a=6$.

   2. Since $(c^2-c)+(2c-3)=9$, then $c^2+c-3=9$ and so $c^2+c-12=0$.

      Factoring, we obtain $(c+4)(c-3)=0$ and so $c=3$ or $c=-4$.

   3. Solution 1

      Manipulating algebraically, we obtain the following equivalent equations: $$\begin{array}{rl}{\displaystyle \frac{1}{x^2}}+{\displaystyle \frac{3}{2x^2}}& =10\\ 2+3& =20x^2\text{(multiplying through by }2x^2\text{, given that }x\ne 0\text{)}\\ 5& =20x^2\\ x^2& =\frac{1}{4}\end{array}$$ and so $x=\pm {\displaystyle \frac{1}{2}}$.

      Solution 2

      Manipulating algebraically, we obtain the following equivalent equations: $$\begin{array}{rl}{\displaystyle \frac{1}{x^2}}+{\displaystyle \frac{3}{2x^2}}& =10\\ {\displaystyle \frac{2}{2x^2}}+{\displaystyle \frac{3}{2x^2}}& =10\\ {\displaystyle \frac{5}{2x^2}}& =10\\ 5& =20x^2\text{(since }x\ne 0\text{)}\\ x^2& =\frac{1}{4}\end{array}$$ and so $x=\pm {\displaystyle \frac{1}{2}}$.

2. 1. Using a calculator, we see that $$({10}^3+1{)}^2={1001}^2=1002001$$ The sum of the digits of this integer is $1+2+1$ which equals 4.

      To determine this integer without using a calculator, we can let $x={10}^3$.

      Then $$\begin{array}{rl}({10}^3+1{)}^2& =(x+1{)}^2\\ & =x^2+2x+1\\ & =({10}^3{)}^2+2({10}^3)+1\\ & =1002001\end{array}$$

   2. Before the price increase, the total cost of 2 small cookies and 1 large cookie is $2\cdot \mathrm{\$}1.50+\mathrm{\$}2.00=\mathrm{\$}5.00$.

      10% of $1.50 is $0.1\cdot \mathrm{\$}1.50=\mathrm{\$}0.15$. After the price increase, 1 small cookie costs $\mathrm{\$}1.50+\mathrm{\$}0.15=\mathrm{\$}1.65$.

      5% of $2.00 is $0.05\cdot \mathrm{\$}2.00=\mathrm{\$}0.10$. After the price increase, 1 large cookie costs $\mathrm{\$}2.00+\mathrm{\$}0.10=\mathrm{\$}2.10$.

      After the price increase, the total cost of 2 small cookies and 1 large cookie is $2\cdot \mathrm{\$}1.65+\mathrm{\$}2.10=\mathrm{\$}5.40$.

      The percentage increase in the total cost is ${\displaystyle \frac{\mathrm{\$}5.40-\mathrm{\$}5.00}{\mathrm{\$}5.00}}\times 100\mathrm{\%}={\displaystyle \frac{40}{500}}\times 100\mathrm{\%}=8\mathrm{\%}$.

   3. Suppose that Rayna’s age is $x$ years.

      Since Qing is twice as old as Rayna, Qing’s age is $2x$ years.

      Since Qing is 4 years younger than Paolo, Paolo’s age is $2x+4$ years.

      Since the average of their ages is 13 years, we obtain $${\displaystyle \frac{x+(2x)+(2x+4)}{3}}=13$$ This gives $5x+4=39$ and so $5x=35$ or $x=7$.

      Therefore, Rayna is 7 years old, Qing is 14 years old, and Paolo is 18 years old.

      (Checking, the average of 7, 14 and 18 is ${\displaystyle \frac{7+14+18}{3}}={\displaystyle \frac{39}{3}}=13$.)

3. 1. The length of $PQ$ is equal to $\sqrt{(0-5{)}^2+(12-0{)}^2}=\sqrt{(-5{)}^2+{12}^2}=13$.

      In a similar way, we can see that $QR=RS=SP=13$.

      Therefore, the perimeter of $PQRS$ is $4\cdot 13=52$.

      (We can also see that if $O$ is the origin, then $\mathrm{△}POQ$, $\mathrm{△}POS$, $\mathrm{△}ROQ$, and $\mathrm{△}ROS$ are congruent because $OQ=OS$ and $OP=OR$, which means that $PQ=QR=RS=SP$.)

   2. Solution 1

      Suppose that $B$ has coordinates $(r,s)$ and $C$ has coordinates $(t,u)$.

      Since $M(3,9)$ is the midpoint of $A(0,8)$ and $B(r,s)$, then 3 is the average of 0 and $r$ (which gives $r=6$) and 9 is the average of 8 and $s$ (which gives $s=10$).

      Since $N(7,6)$ is the midpoint of $B(6,10)$ and $C(t,u)$, then 7 is the average of 6 and $t$ (which gives $t=8$) and 6 is the average of 10 and $u$ (which gives $u=2$).

      The slope of the line segment joining $A(0,8)$ and $C(8,2)$ is ${\displaystyle \frac{8-2}{0-8}}$ which equals $-{\displaystyle \frac{3}{4}}$.

      Solution 2

      Since $M$ is the midpoint of $AB$ and $N$ is the midpoint of $BC$, then $MN$ is parallel to $AC$.

      Therefore, the slope of $AC$ equals the slope of the line segment joining $M(3,9)$ to $N(7,6)$, which is ${\displaystyle \frac{9-6}{3-7}}$ or $-{\displaystyle \frac{3}{4}}$.

   3. Since $V(1,18)$ is on the parabola, then $18=-2(1^2)+4(1)+c$ and so $c=18+2-4=16$.

      Thus, the equation of the parabola is $y=-2x^2+4x+16$.

      The $y$-intercept occurs when $x=0$, and so $y=16$. Thus, $D$ has coordinates $(0,16)$.

      The $x$-intercepts occur when $y=0$. Here, $$\begin{array}{rl}-2x^2+4x+16& =0\\ -2(x^2-2x-8)& =0\\ -2(x-4)(x+2)& =0\end{array}$$ and so $x=4$ and $x=-2$.

      This means that $E$ and $F$, in some order, have coordinates $(4,0)$ and $(-2,0)$.

      Therefore, $\mathrm{△}DEF$ has base $EF$ of length $4-(-2)=6$ and height 16 (vertical distance from the $x$-axis to the point $D$).

      Finally, the area of $\mathrm{△}DEF$ is $\frac{1}{2}\cdot 6\cdot 16=48$.

4. 1. We obtain successively $$\begin{array}{rl}3(8^x)+5(8^x)& =2^{61}\\ 8(8^x)& =2^{61}\\ 8^{x+1}& =2^{61}\\ (2^3{)}^{x+1}& =2^{61}\\ 2^{3(x+1)}& =2^{61}\end{array}$$ Thus, $3(x+1)=61$ and so $3x+3=61$ which gives $3x=58$ or $x=\frac{58}{3}$.

   2. Since the list $3n^2$, $m^2$, $2(n+1{)}^2$ consists of three consecutive integers written in increasing order, then $$\begin{array}{rl}2(n+1{)}^2-3n^2& =2\\ 2n^2+4n+2-3n^2& =2\\ -n^2+4n& =0\\ -n(n-4)& =0\end{array}$$ and so $n=0$ or $n=4$.

      If $n=0$, the list becomes $0$, $m^2$, $2$. This means that $m^2=1$ and so $m=\pm 1$.

      If $n=4$, we have $3n^2=3\cdot 16=48$ and $2(n+1{)}^2=2\cdot 25=50$ giving the list $48$, $m^2$, $50$. This means that $m^2=49$ and so $m=\pm 7$.

      Thus, the possible values for $m$ are $1$, $-1$, $7$, $-7$.

5. 1. Solution 1

      Suppose that $S_0$ has coordinates $(a,b)$.

      Step 1 moves $(a,b)$ to $(a,-b)$.

      Step 2 moves $(a,-b)$ to $(a,-b+2)$.

      Step 3 moves $(a,-b+2)$ to $(-a,-b+2)$.

      Thus, $S_1$ has coordinates $(-a,-b+2)$.

      Step 1 moves $(-a,-b+2)$ to $(-a,b-2)$.

      Step 2 moves $(-a,b-2)$ to $(-a,b)$.

      Step 3 moves $(-a,b)$ to $(a,b)$.

      Thus, $S_2$ has coordinates $(a,b)$, which are the same coordinates as $S_0$.

      Continuing this process, $S_4$ will have the same coordinates as $S_2$ (and thus as $S_0$) and $S_6$ will have the same coordinates as $S_4$, $S_2$ and $S_0$.

      Since the coordinates of $S_6$ are $(-7,-1)$, the coordinates of $S_0$ are also $(-7,-1)$.

      Solution 2

      We work backwards from $S_6(-7,-1)$.

      To do this, we undo the Steps of the process $\mathcal{P}$ by applying them in reverse order.

      Since Step 3 reflects a point in the $y$-axis, its inverse does the same.

      Since Step 2 translates a point 2 units upwards, its inverse translates a point 2 units downwards.

      Since Step 1 reflects a point in the $x$-axis, its inverse does the same.

      Applying these inverse steps to $S_6(-7,-1)$, we obtain $(7,-1)$, then $(7,-3)$, then $(7,3)$.

      Thus, $S_5$ has coordinates $(7,3)$.

      Applying the inverse steps to $S_5(7,3)$, we obtain $(-7,3)$, then $(-7,1)$, then $(-7,-1)$.

      Thus, $S_4$ has coordinates $(-7,-1)$, which are the same coordinates as $S_6$.

      If we apply these steps two more times, we will see that $S_2$ is the same point as $S_4$.

      Two more applications tell us that $S_0$ is the same point as $S_2$.

      Therefore, the coordinates of $S_0$ are the same as the coordinates of $S_6$, which are $(-7,-1)$.

   2. We begin by determining the length of $AB$ in terms of $x$.

      Since $ABDE$ is a rectangle, $BD=AE=2x$.

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

      Join $A$ to $D$.

      

      Since $AD$ and $BC$ are parallel, $\mathrm{\angle }ADB=\mathrm{\angle }DBC={60}^{\circ }$.

      Consider $\mathrm{△}ADB$. This is a ${30}^{\circ }$-${60}^{\circ }$-${90}^{\circ }$ triangle since $\mathrm{\angle }ABD$ is a right angle.

      Using ratios of side lengths, ${\displaystyle \frac{AB}{BD}}={\displaystyle \frac{\sqrt{3}}{1}}$ and so $AB=\sqrt{3}BD=2\sqrt{3}x$, which is the answer to (i).

      Next, we determine ${\displaystyle \frac{AC}{AD}}$.

      Now, ${\displaystyle \frac{AD}{BD}}={\displaystyle \frac{2}{1}}$ and so $AD=2BD=4x$.

      Suppose that $M$ is the midpoint of $AE$ and $N$ is the midpoint of $BD$.

      Since $AE=BD=2x$, then $AM=ME=BN=ND=x$.

      Join $M$ to $N$ and $N$ to $C$ and $A$ to $C$.

      

      Since $ABDE$ is a rectangle, then $MN$ is parallel to $AB$ and so $MN$ is perpendicular to both $AE$ and $BD$.

      Also, $MN=AB=2\sqrt{3}x$.

      Since $\mathrm{△}BCD$ is equilateral, its median $CN$ is perpendicular to $BD$.

      Since $MN$ and $NC$ are perpendicular to $BD$, $MNC$ is actually a straight line segment and so $MC=MN+NC$.

      Now $\mathrm{△}BNC$ is also a ${30}^{\circ }$-${60}^{\circ }$-${90}^{\circ }$ triangle, and so $NC=\sqrt{3}BN=\sqrt{3}x$.

      This means that $MC=2\sqrt{3}x+\sqrt{3}x=3\sqrt{3}x$.

      Finally, $\mathrm{△}AMC$ is right-angled at $M$ and so $$AC=\sqrt{A{M}^2+M{C}^2}=\sqrt{x^2+(3\sqrt{3}x{)}^2}=\sqrt{x^2+27x^2}=\sqrt{28x^2}=2\sqrt{7}x$$ since $x>0$.

      This means that ${\displaystyle \frac{AC}{AD}}={\displaystyle \frac{2\sqrt{7}x}{4x}}={\displaystyle \frac{\sqrt{7}}{2}}=\sqrt{{\displaystyle \frac{7}{4}}}$, which means that the integers $r=7$ and $s=4$ satisfy the conditions for (ii).

6. 1. Solution 1

      Since the sequence $t_1,t_2,t_3,\dots ,t_{n-2},t_{n-1},t_n$ is arithmetic, then $$t_1+t_n=t_2+t_{n-1}=t_3+t_{n-2}$$ This is because, if $d$ is the common difference, we have $t_2=t_1+d$ and $t_{n-1}=t_n-d$, as well as having $t_3=t_1+2d$ and $t_{n-2}=t_n-2d$.

      Since the sum of all $n$ terms is 1000, using one formula for the sum of an arithmetic sequence gives $$\begin{array}{rl}{\displaystyle \frac{n}{2}}(t_1+t_n)& =1000\\ n(t_1+t_n)& =2000\\ n(t_3+t_{n-2})& =2000\\ n(5+95)& =2000\end{array}$$ and so $n=20$.

      Solution 2

      Suppose that the arithmetic sequence with $n$ terms has first term $a$ and common difference $d$.

      Then $t_3=a+2d=5$ and $t_{n-2}=a+(n-3)d=95$.

      Since the sum of the $n$ terms equals 1000, then $${\displaystyle \frac{n}{2}}(2a+(n-1)d)=1000$$ Adding the equations $a+2d=5$ and $a+(n-3)d=95$, we obtain $2a+(n-1)d=100$.

      Substituting, we get ${\displaystyle \frac{n}{2}}(100)=1000$ from which we obtain $n=20$.

   2. Since the sum of a geometric sequence with first term $a$, common ratio $r$ and 4 terms is $6+6\sqrt{2}$, then $$a+ar+a{r}^2+a{r}^3=6+6\sqrt{2}$$ Since the sum of a geometric sequence with first term $a$, common ratio $r$ and 8 terms is $30+30\sqrt{2}$, then $$a+ar+a{r}^2+a{r}^3+a{r}^4+a{r}^5+a{r}^6+a{r}^7=30+30\sqrt{2}$$ But $$\begin{array}{rl}& a+ar+a{r}^2+a{r}^3+a{r}^4+a{r}^5+a{r}^6+a{r}^7\\ & =(a+ar+a{r}^2+a{r}^3)+r^4(a+ar+a{r}^2+a{r}^3)\\ & =(1+r^4)(a+ar+a{r}^2+a{r}^3)\end{array}$$ Therefore, $$\begin{array}{rl}30+30\sqrt{2}& =(1+r^4)(6+6\sqrt{2})\\ {\displaystyle \frac{30+30\sqrt{2}}{6+6\sqrt{2}}}& =1+r^4\\ 5& =1+r^4\\ r^4& =4\\ r^2& =2\text{(since }{r}^2>0\text{)}\\ r& =\pm \sqrt{2}\end{array}$$ If $r=\sqrt{2}$, $$a+ar+a{r}^2+a{r}^3=a+\sqrt{2}a+a(\sqrt{2}{)}^2+a(\sqrt{2}{)}^3=a+\sqrt{2}a+2a+2\sqrt{2}a=a(3+3\sqrt{2})$$ Since $a+ar+a{r}^2+a{r}^3=6+6\sqrt{2}$, then $a(3+3\sqrt{2})=6+6\sqrt{2}$ and so $a={\displaystyle \frac{6+6\sqrt{2}}{3+3\sqrt{2}}}=2$.

      If $r=-\sqrt{2}$, $$a+ar+a{r}^2+a{r}^3=a-\sqrt{2}a+a(-\sqrt{2}{)}^2+a(-\sqrt{2}{)}^3=a-\sqrt{2}a+2a-2\sqrt{2}a=a(3-3\sqrt{2})$$ Since $a+ar+a{r}^2+a{r}^3=6+6\sqrt{2}$, then $a(3-3\sqrt{2})=6+6\sqrt{2}$ and so $$a={\displaystyle \frac{6+6\sqrt{2}}{3-3\sqrt{2}}}={\displaystyle \frac{2+2\sqrt{2}}{1-\sqrt{2}}}={\displaystyle \frac{(2+2\sqrt{2})(1+\sqrt{2})}{(1-\sqrt{2})(1+\sqrt{2})}}={\displaystyle \frac{2+2\sqrt{2}+2\sqrt{2}+4}{1-2}}=-6-4\sqrt{2}$$ Therefore, the possible values of $a$ are $a=2$ and $a=-6-4\sqrt{2}$.

      An alternate way of arriving at the equation $1+r^4=5$ is to use the formula for the sum of a geometric sequence twice to obtain $${\displaystyle \frac{a(1-r^4)}{1-r}}=6+6\sqrt{2}{\displaystyle \frac{a(1-r^8)}{1-r}}=30+30\sqrt{2}$$ assuming that $r\ne 1$. (Can you explain why $r\ne 1$ and $r^4\ne 1$ without knowing already that $r=\pm \sqrt{2}$?)

      Dividing the second equation by the first, we obtain $${\displaystyle \frac{a(1-r^8)}{1-r}}\cdot {\displaystyle \frac{1-r}{a(1-r^4)}}={\displaystyle \frac{30+30\sqrt{2}}{6+6\sqrt{2}}}$$ which gives $${\displaystyle \frac{1-r^8}{1-r^4}}=5$$ Since $1-r^8=(1+r^4)(1-r^4)$, we obtain $1+r^4=5$. We then can proceed as above.

7. 1. Victor stops when there are either 2 green balls on the table or 2 red balls on the table.

      If the first 2 balls that Victor removes are the same colour, Victor will stop.

      If the first 2 balls that Victor removes are different colours, Victor does not yet stop, but when he removes a third ball, its colour must match the colour of one of the first 2 balls and so Victor does stop.

      Therefore, the probability that he stops with at least 1 red ball and 1 green ball on the table is equal to the probability that the first 2 balls that he removes are different colours.

      Also, the probability that the first 2 balls that he removes are different colours is equal to 1 minus the probability that the first 2 balls that he removes are the same colour.

      The probability that the first two balls that Victor draws are both green is $\frac{3}{7}\cdot \frac{2}{6}$ because for the first ball there are 7 balls in the bag, 3 of which are green and for the second ball there are 6 balls in the bag, 2 of which are green.

      The probability that the first two balls that Victor draws are both red is $\frac{4}{7}\cdot \frac{3}{6}$ because for the first ball there are 7 balls in the bag, 4 of which are red and for the second ball there are 6 balls in the bag, 3 of which are red.

      Thus, the probability that the first two balls that Victor removes are the same colour is $$\frac{3}{7}\cdot \frac{2}{6}+\frac{4}{7}\cdot \frac{3}{6}=\frac{1}{7}+\frac{2}{7}=\frac{3}{7}$$ This means that the desired probability is $1-\frac{3}{7}=\frac{4}{7}$.

   2. Using the definition of $f$, the following equations are equivalent: $$\begin{array}{rl}f(a)& =0\\ 2a^2-3a+1& =0\\ (a-1)(2a-1)& =0\end{array}$$ Therefore, $f(a)=0$ exactly when $a=1$ or $a=\frac{1}{2}$.

      Thus, $f(g(\sin \theta ))=0$ exactly when $g(\sin \theta )=1$ or $g(\sin \theta )=\frac{1}{2}$.

      Using the definition of $g$,

      • $g(b)=1$ exactly when ${\log }_{\frac{1}{2}}b=1$, which gives $b={\left(\frac{1}{2}\right)}^1=\frac{1}{2}$, and

      • $g(b)=1/2$ exactly when ${\log }_{\frac{1}{2}}b=1/2$, which gives $b={\left(\frac{1}{2}\right)}^{1/2}=\frac{1}{\sqrt{2}}$.

      Therefore, $f(g(\sin \theta ))=0$ exactly when $\sin \theta =\frac{1}{2}$ or $\sin \theta =\frac{1}{\sqrt{2}}$.

      Since $0\le \theta \le 2\pi$, the solutions are $\theta =\frac{1}{6}\pi ,\frac{5}{6}\pi ,\frac{1}{4}\pi ,\frac{3}{4}\pi$.

8. 1. Suppose that the integers in the first row are, in order, $a$, $b$, $c$, $d$, $e$.

      Using these, we calculate the integer in each of the boxes below the top row in terms of these variables, using the rule that each integer is the product of the integers in the two boxes above:

      

      Hide/Reveal Expressions for Integers

      The expressions, in order from left to right, in each of the five rows, from top to bottom, are as follows:

      1. $a$, $b$, $c$, $d$, and $e$
      2. $ab$, $bc$, $cd$, and $de$
      3. $a{b}^{2}c$, $b{c}^{2}d$, and $c{d}^{2}e$
      4. $a{b}^3{c}^{3}d$ and $b{c}^3{d}^{3}e$
      5. $a{b}^4{c}^6{d}^{4}e$

      ---

      Therefore, $a{b}^4{c}^6{d}^{4}e=9953280000$.

      Next, we determine the prime factorization of the integer $9953280000$: $$\begin{array}{rl}9953280000& ={10}^4\cdot 995328\\ & =2^4\cdot 5^4\cdot 2^3\cdot 124416\\ & =2^7\cdot 5^4\cdot 2^3\cdot 15552\\ & =2^{10}\cdot 5^4\cdot 2^3\cdot 1944\\ & =2^{13}\cdot 5^4\cdot 2^3\cdot 243\\ & =2^{16}\cdot 5^4\cdot 3^5\\ & =2^{16}\cdot 3^5\cdot 5^4\end{array}$$ Thus, $a{b}^4{c}^6{d}^{4}e=2^{16}\cdot 3^5\cdot 5^4$.

      Since the right side is not divisible by 7, none of $a$, $b$, $c$, $d$, $e$ can equal 7.

      Thus, $a$, $b$, $c$, $d$, $e$ are five distinct integers chosen from $\{1,2,3,4,5,6,8\}$.

      The only one of these integers divisible by 5 is 5 itself.

      Since $2^{16}\cdot 3^5\cdot 5^4$ includes exactly 4 factors of 5, then either $b=5$ or $d=5$. No other placement of the 5 can give exactly 4 factors of 5.

      Case 1: $b=5$

      Here, $a{c}^6{d}^{4}e=2^{16}\cdot 3^5$ and $a$, $c$, $d$, $e$ are four distinct integers chosen from $\{1,2,3,4,6,8\}$.

      Since $a{c}^6{d}^{4}e$ includes exactly 5 factors of 3 and the possible values of $a$, $c$, $d$, $e$ that are divisible by 3 are 3 and 6, then either $d=3$ and one of $a$ and $e$ is 6, or $d=6$ and one of $a$ and $e$ is 3. No other placements of the multiples of 3 can give exactly 5 factors of 3.

      Case 1a: $b=5$, $d=3$, $a=6$

      Here, $a\cdot c^6\cdot d^4\cdot e=6\cdot c^6\cdot 3^4\cdot e=2\cdot 3^5\cdot c^6\cdot e$.

      This gives $c^{6}e=2^{15}$ and $c$ and $e$ are distinct integers from $\{1,2,4,8\}$.

      Trying the four possible values of $c$ shows that $c=4$ and $e=8$ is the only solution in this case. Here, $(a,b,c,d,e)=(6,5,4,3,8)$.

      Case 1b: $b=5$, $d=3$, $e=6$ We obtain $(a,b,c,d,e)=(8,5,4,3,6)$.

      Case 1c: $b=5$, $d=6$, $a=3$

      Here, $a\cdot c^6\cdot d^4\cdot e=3\cdot c^6\cdot 6^4\cdot e=2^4\cdot 3^5\cdot c^6\cdot e$.

      This gives $c^{6}e=2^{12}$ and $c$ and $e$ are distinct integers from $\{1,2,4,8\}$.

      Trying the four possible values of $c$ shows that $c=4$ and $e=1$ is the only solution in this case. Here, $(a,b,c,d,e)=(3,5,4,6,1)$.

      Case 1d: $b=5$, $d=6$, $e=3$ We obtain $(a,b,c,d,e)=(1,5,4,6,3)$.

      Case 2: $d=5$: A similar analysis leads to 4 further quintuples $(a,b,c,d,e)$.

      Therefore, there are 8 ways in which the integers can be chosen and placed in the top row to obtain the desired integer in the bottom box.

   2. Let $N={\displaystyle \frac{(1!)(2!)(3!)\cdots (398!)(399!)(400!)}{200!}}$.

      For each integer $k$ from 1 to 200, inclusive, we rewrite $(2k)!$ as $2k\cdot (2k-1)!$.

      Therefore, $(2k-1)!(2k)!=(2k-1)!\cdot 2k\cdot (2k-1)!=2k((2k-1)!{)}^2$.

      (In particular, $(1!)(2!)=2(1!{)}^2$, $(3!)(4!)=4(3!{)}^2$, and so on.)

      Thus, $$N={\displaystyle \frac{2(1!{)}^2\cdot 4(3!{)}^2\cdot \cdots \cdot 398(397!{)}^2\cdot 400(399!{)}^2}{200!}}$$ Re-arranging the numerator of the expression, we obtain $$N={\displaystyle \frac{(1!{)}^2(3!{)}^2\cdots (397!{)}^2(399!{)}^2\cdot (2\cdot 4\cdot \cdots \cdot 398\cdot 400)}{200!}}$$ We can now re-write $2\cdot 4\cdot \cdots \cdot 398\cdot 400$ as $(2\cdot 1)\cdot (2\cdot 2)\cdot \cdots \cdot (2\cdot 199)\cdot (2\cdot 200)$.

      Since there are 200 sets of parentheses, we obtain $$N={\displaystyle \frac{(1!{)}^2(3!{)}^2\cdots (397!{)}^2(399!{)}^2\cdot 2^{200}\cdot (1\cdot 2\cdot \cdots \cdot 199\cdot 200)}{200!}}$$ Since $1\cdot 2\cdot \cdots \cdot 199\cdot 200=200!$, we can conclude that $$N=2^{200}(1!{)}^2(3!{)}^2\cdots (397!{)}^2(399!{)}^2$$ Therefore, $$\sqrt{N}=2^{100}(1!)(3!)\cdots (397!)(399!)$$ which is a product of integers and thus an integer itself.

      Since $\sqrt{N}$ is an integer, $N$ is a perfect square, as required.

9. 1. When $a=5$ and $b=4$, we obtain $a^2+b^2-ab=5^2+4^2-5\cdot 4=21$.

      Therefore, we want to find all pairs of integers $(K,L)$ with $K^2+3L^2=21$.

      If $L=0$, then $L^2=0$, which gives $K^2=21$ which has no integer solutions.

      If $L=\pm 1$, then $L^2=1$, which gives $K^2=18$ which has no integer solutions.

      If $L=\pm 2$, then $L^2=4$, which gives $K^2=9$ which gives $K=\pm 3$.

      If $L=\pm 3$, then $L^2=9$. Since $3L^2=27>21$, then there are no real solutions for $K$.

      Similarly, if $L^2>9$, there are no real solutions for $K$.

      Therefore, the solutions are $(K,L)=(3,2),(-3,2),(3,-2),(-3,-2)$.

   2. Suppose that $K$ and $L$ are integers.

      Then $$\begin{array}{rl}& (K+L{)}^2+(K-L{)}^2-(K+L)(K-L)\\ & =(K^2+2KL+L^2)+(K^2-2KL+L^2)-(K^2-L^2)\\ & =K^2+3L^2\end{array}$$ Therefore, the integers $a=K+L$ and $b=K-L$ satisfy the equation $K^2+3L^2=a^2+b^2-ab$, and so for all integers $K$ and $L$, there is at least one pair of integers $(a,b)$ that satisfy the equation.

      How could we come up with this? One way to do this would be trying some small values of $K$ and $L$, calculating $K^2+3L^2$ and using this to make a guess, which can then be proven algebraically as above. In particular, here are some values:

      $K$	$L$	$K^2+3L^2=a^2+b^2-ab$	$a$	$b$
      1	1	4	2	0
      2	1	7	3	1
      3	1	12	4	2
      1	2	13	3	-1
      2	2	16	4	0
      3	2	21	5	1

      The columns for $a$ and $b$ might lead us to guess that $a=K+L$ and $b=K-L$, which we proved above does in fact work.

   3. Suppose that $a$ and $b$ are integers.

      If $a$ is even, then ${\displaystyle \frac{a}{2}}$ is an integer and so $${({\displaystyle \frac{a}{2}}-b)}^2+3{\left({\displaystyle \frac{a}{2}}\right)}^2={\displaystyle \frac{a^2}{4}}-2\cdot {\displaystyle \frac{a}{2}}\cdot b+b^2+{\displaystyle \frac{3a^2}{4}}=a^2+b^2-ab$$ Thus, if $K={\displaystyle \frac{a}{2}}-b$ and $L={\displaystyle \frac{a}{2}}$, we have $K^2+3L^2=a^2+b^2-ab$.

      If $b$ is even, then ${\displaystyle \frac{b}{2}}$ is an integer and so a similar algebraic argument shows that $${({\displaystyle \frac{b}{2}}-a)}^2+3{\left({\displaystyle \frac{b}{2}}\right)}^2=a^2+b^2-ab$$ and so if $K={\displaystyle \frac{b}{2}}-a$ and $L={\displaystyle \frac{b}{2}}$, we have $K^2+3L^2=a^2+b^2-ab$.

      If $a$ and $b$ are both odd, then $a+b$ and $a-b$ are both even, which means that ${\displaystyle \frac{a+b}{2}}$ and ${\displaystyle \frac{a-b}{2}}$ are both integers, and so $${\left({\displaystyle \frac{a+b}{2}}\right)}^2+3{\left({\displaystyle \frac{a-b}{2}}\right)}^2={\displaystyle \frac{a^2+2ab+b^2}{4}}+{\displaystyle \frac{3a^2-6ab+3b^2}{4}}={\displaystyle \frac{4a^2+4b^2-4ab}{4}}=a^2+b^2-ab$$ Thus, if $K={\displaystyle \frac{a+b}{2}}$ and $L={\displaystyle \frac{a-b}{2}}$, we have $K^2+3L^2=a^2+b^2-ab$.

      Therefore, in all cases, for all integers $a$ and $b$, there is at least one pair of integers $(K,L)$ with $K^2+3L^2=a^2+b^2-ab$.

      As in (b), trying some small cases might help us make a guess of possible expressions for $K$ and $L$ in terms of $a$ and $b$:

      $a$	$b$	$K^2+3L^2=a^2+b^2-ab$	$K$	$L$
      1	1	1	1	0
      2	1	3	0	1
      3	1	7	2	1
      4	1	13	1	2
      1	2	3	0	1
      2	2	4	1	1
      3	2	7	2	1
      4	2	12	3	1
      5	3	19	4	1

      While there might not initially seem to be useful patterns here, re-arranging the rows and adding some duplicates might help show a pattern:

      $a$	$b$	$K^2+3L^2=a^2+b^2-ab$	$K$	$L$
      2	1	3	0	1
      4	1	13	1	2
      2	2	4	1	1
      4	2	12	3	1
      1	2	3	0	1
      3	2	7	2	1
      4	2	12	3	1
      1	1	1	1	0
      3	1	7	2	1
      5	3	19	4	1

10. 1. We label the centres of the outer circles, starting with the circle labelled $Z$ and proceeding clockwise, as $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$, $J$, and $K$, and the centre of the circle labelled $Y$ as $L$.

       

       Join $L$ to each of $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$, $J$, and $K$. Join $A$ to $B$, $B$ to $C$, $C$ to $D$, $D$ to $E$, $E$ to $F$, $F$ to $G$, $G$ to $H$, $H$ to $J$, $J$ to $K$, and $K$ to $A$.

       When two circles are tangent, the distance between their centres equals the sum of their radii.

       Thus, $$\begin{array}{rl}BC=CD=DE=EF=FG=GH=HJ=JK=2+1& =3\\ BL=DL=FL=HL=KL=2+4& =6\\ CL=EL=GL=JL& =1+4=5\\ AB=AK& =r+2\\ AL& =r+4\end{array}$$ By side-side-side congruence, the following triangles are congruent: $$\mathrm{△}BLC,\mathrm{△}DLC,\mathrm{△}DLE,\mathrm{△}FLE,\mathrm{△}FLG,\mathrm{△}HLG,\mathrm{△}HLJ,\mathrm{△}KLJ$$ Similarly, $\mathrm{△}ALB$ and $\mathrm{△}ALK$ are congruent by side-side-side.

       Let $\mathrm{\angle }ALB=\theta$ and let $\mathrm{\angle }BLC=\alpha$.

       By congruent triangles, $\mathrm{\angle }ALK=\theta$ and $$\mathrm{\angle }BLC=\mathrm{\angle }DLC=\mathrm{\angle }DLE=\mathrm{\angle }FLE=\mathrm{\angle }FLG=\mathrm{\angle }HLG=\mathrm{\angle }HLJ=\mathrm{\angle }KLJ=\alpha$$ The angles around $L$ add to ${360}^{\circ }$ and so $2\theta +8\alpha ={360}^{\circ }$ which gives $\theta +4\alpha ={180}^{\circ }$ and so $\theta ={180}^{\circ }-4\alpha$.

       Since $\theta ={180}^{\circ }-4\alpha$, then $\cos \theta =\cos ({180}^{\circ }-4\alpha )=-\cos 4\alpha$.

       Consider $\mathrm{△}ALB$ and $\mathrm{△}BLC$.

       

       By the cosine law in $\mathrm{△}ALB$, $$\begin{array}{rl}A{B}^2& =A{L}^2+B{L}^2-2\cdot AL\cdot BL\cdot \cos \theta \\ (r+2{)}^2& =(r+4{)}^2+6^2-2(r+4)(6)\cos \theta \\ 12(r+4)\cos \theta & =r^2+8r+16+36-r^2-4r-4\\ \cos \theta & ={\displaystyle \frac{4r+48}{12(r+4)}}\\ \cos \theta & ={\displaystyle \frac{r+12}{3r+12}}\end{array}$$ By the cosine law in $\mathrm{△}BLC$, $$\begin{array}{rl}B{C}^2& =B{L}^2+C{L}^2-2\cdot BL\cdot CL\cdot \cos \alpha \\ 3^2& =6^2+5^2-2(6)(5)\cos \alpha \\ 60\cos \alpha & =36+25-9\\ \cos \alpha & ={\displaystyle \frac{52}{60}}\\ \cos \alpha & ={\displaystyle \frac{13}{15}}\end{array}$$ Since $\cos \alpha ={\displaystyle \frac{13}{15}}$, then $$\begin{array}{rl}\cos 2\alpha & =2{\cos }^2\alpha -1\\ & =2\cdot {\displaystyle \frac{169}{225}}-1\\ & ={\displaystyle \frac{338}{225}}-{\displaystyle \frac{225}{225}}\\ & ={\displaystyle \frac{113}{225}}\end{array}$$ and $$\begin{array}{rl}\cos 4\alpha & =2{\cos }^{2}2\alpha -1\\ & =2\cdot {\displaystyle \frac{{113}^2}{{225}^2}}-1\\ & ={\displaystyle \frac{25538}{50625}}-{\displaystyle \frac{50625}{50625}}\\ & =-{\displaystyle \frac{25087}{50625}}\end{array}$$ Finally, $$\begin{array}{rl}\cos \theta & =-\cos 4\alpha \\ {\displaystyle \frac{r+12}{3r+12}}& ={\displaystyle \frac{25087}{50625}}\\ {\displaystyle \frac{r+12}{r+4}}& ={\displaystyle \frac{25087}{16875}}\\ {\displaystyle \frac{(r+4)+8}{r+4}}& ={\displaystyle \frac{25087}{16875}}\\ 1+{\displaystyle \frac{8}{r+4}}& ={\displaystyle \frac{25087}{16875}}\\ {\displaystyle \frac{8}{r+4}}& ={\displaystyle \frac{8212}{16875}}\\ {\displaystyle \frac{2}{r+4}}& ={\displaystyle \frac{2053}{16875}}\\ {\displaystyle \frac{r+4}{2}}& ={\displaystyle \frac{16875}{2053}}\\ r+4& ={\displaystyle \frac{33750}{2053}}\\ r& ={\displaystyle \frac{25538}{2053}}\end{array}$$ Therefore, the positive integers $s=25538$ and $t=2053$ satisfy the required conditions.

    2. Let the centre of the middle circle be $O$, and the centres of the other circles be $P$, $Q$, $R$, and $S$, as shown.

       Join $O$ to $P$, $Q$, $R$, and $S$, and join $P$ to $Q$, $Q$ to $R$, $R$ to $S$, and $S$ to $P$.

       

       Using a similar argument as in (a), we see that $$\begin{array}{rl}OP=OR& =a+c\\ OQ=OS& =b+c\\ PQ=QR=RS=SP& =a+b\end{array}$$ By side-side-side congruence, $\mathrm{△}OPQ$, $\mathrm{△}OPS$, $\mathrm{△}ORQ$, and $\mathrm{△}ORS$ are congruent.

       This means that $\mathrm{\angle }POQ=\mathrm{\angle }POS=\mathrm{\angle }ROQ=\mathrm{\angle }ROS$.

       Since $\mathrm{\angle }POQ+\mathrm{\angle }POS+\mathrm{\angle }ROQ+\mathrm{\angle }ROS={360}^{\circ }$ (these angles surround $O$), then $$\mathrm{\angle }POQ=\frac{1}{4}\cdot {360}^{\circ }={90}^{\circ }$$ This means that $\mathrm{△}OPQ$ is right-angled at $O$.

       By the Pythagorean Theorem, $P{Q}^2=O{P}^2+O{Q}^2$ and so $(a+b{)}^2=(a+c{)}^2+(b+c{)}^2$.

       Manipulating algebraically, the following equations are equivalent: $$\begin{array}{rl}(a+b{)}^2& =(a+c{)}^2+(b+c{)}^2\\ a^2+2ab+b^2& =a^2+2ac+c^2+b^2+2bc+c^2\\ 2ab& =2ac+2bc+2c^2\\ ab& =ac+bc+c^2\\ ab-ac-bc& =c^2\\ ab-ac-bc+c^2& =2c^2\\ a(b-c)-c(b-c)& =2c^2\\ (a-c)(b-c)& =2c^2\end{array}$$ Therefore, if $a$, $b$ and $c$ are real numbers for which the diagram can be constructed, then $a$, $b$ and $c$ satisfy this last equation.

       Also, if real numbers $a$, $b$ and $c$ satisfy the final equation, then $(a+b{)}^2=(a+c{)}^2+(b+c{)}^2$ (because these equations were equivalent) and so the triangle with side lengths $a+b$, $a+c$ and $b+c$ is right-angled with hypotenuse $a+b$ (because the Pythagorean Theorem works in both directions), which means that four such triangles can be assembled to form a rhombus $PQRS$ with side lengths $a+b$ and centre $O$, which means that the five circles can be drawn by marking off the appropriate lengths $a$, $b$ and $c$ and drawing the circles as in the original diagram.

       In other words, the diagram can be drawn exactly when $(a-c)(b-c)=2c^2$.

       Suppose that $c$ is a fixed positive integer.

       Determining the value of $f(c)$ is thus equivalent to counting the number of pairs of positive integers $(a,b)$ with $c<a<b$ and $(a-c)(b-c)=2c^2$.

       Since $a$ and $b$ are integers with $a>c$ and $b>c$, the integers $a-c$ and $b-c$ are positive and form a positive divisor pair of the integer $2c^2$.

       Since $a<b$, we have $a-c<b-c$ and so $a-c$ and $b-c$ are distinct integers.

       Also, since $c>0$, $\sqrt{2c^2}=\sqrt{2}c$ which is not an integer since $c$ is an integer, which means that $2c^2$ is not a perfect square.

       Therefore, every pair $(a,b)$ corresponds to a positive divisor pair of $2c^2$ (namely, $a-c$ and $b-c$).

       Similarly, every divisor pair $e$ and $g$ of $2c^2$ with $e>g$ gives a pair of positive integers $(a,b)$ with $a<b$ by setting $a=e+c$ and $b=g+c$.

       In other words, $f(c)$ is exactly the number of positive divisor pairs of $2c^2$. (Again, we note that $2c^2$ is not a perfect square.)

       Therefore, we want to determine all positive integers $c$ for which the integer $2c^2$ has an even number of divisor pairs, which means that we want to determine all positive integers $c$ for which the number of positive divisors of $2c^2$ is a multiple of 4 (because each positive divisor pair corresponds to 2 positive divisors and 2 times an even integer is a multiple of 4).

       Suppose that the prime factorization of $c$ is $$c=2^r{p}_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$$ for some integer $k\ge 0$, integer $r\ge 0$, odd prime numbers $p_1$, $p_2$, $\dots$, $p_k$, and positive integers $e_1$, $e_2$, $\dots$, $e_k$.

       Then $$2c^2=2^{2r+1}{p}_1^{2e_1}{p}_2^{2e_2}\cdots p_k^{2e_k}$$ and so $2c^2$ has $$(2r+2)(2e_1+1)(2e_2+1)\cdots (2e_k+1)$$ positive divisors.

       The first factor in this product is even and each factor after the first is odd.

       Therefore, this product is a multiple of 4 exactly when $2r+2$ is a multiple of 4.

       This is true exactly when $2r+2=4s$ for some positive integer $s$ and so $2r=4s-2$ or $r=2s-1$.

       In other words, the number of positive divisors of $2c^2$ is a multiple of 4 exactly when $r$ is an odd integer.

       Finally, this means that the positive integers for which $f(c)$ are even are exactly those positive integers that have exactly an odd number of factors of 2 in their prime factorization.