2016 Euclid Contest
Solutions

Tuesday, April 12, 2016
(in North America and South America)

Wednesday, April 13, 2016
(outside of North American and South America)

©2016 University of Waterloo

1. 1. The average is \[\dfrac{5+15+25+35+45+55}{6} = \dfrac{(5+55)+(15+45)+(25+35)}{6} = \dfrac{60+60+60}{6} = 30\]

   2. Since \(x^2 = 2016\), then \((x+2)(x-2) = x^2 - 4 = 2016 - 4 = 2012\).

   3. Since points \(P\), \(Q\) and \(R\) lie on a straight line, then the slope of \(PQ\) equals the slope of \(PR\).

      The slope of \(PQ\) equals \(\dfrac{2a - 5}{a - 7}\) and the slope of \(PR\) equals \(\dfrac{30-5}{12- 7} = \dfrac{25}{5} = 5\).

      Therefore, \(\dfrac{2a-5}{a-7} = 5\) and so \(2a - 5 = 5(a-7)\).

      This gives \(2a - 5 = 5a - 35\) or \(3a = 30\), and so \(a=10\).

2. 1. If \(\dfrac{n}{9} = \dfrac{25}{n}\), then \(n^2 = 25(9) = 225\). Therefore, \(n = 15\) or \(n = -15\).

      (We can check by substitution that each of these values satisfies the original equation.)

   2. When we expand the left side of \((x-3)(x-2) = 6\), we obtain \(x^2 - 5x + 6 = 6\).

      Thus, \(x^2 - 5x= 0\) or \(x(x-5)=0\), which gives \(x = 0\) or \(x = 5\).

      (We can check by substitution that each of these values satisfies the original equation.)

   3. Let \(a\) be the cost, in dollars, of 1 apple and let \(b\) be the cost, in dollars, of 1 banana.

      From the given information, \(2a = 3b\) and \(6a + 12b = 6.30\).

      Since \(3b = 2a\), then \(12b = 4(3b) = 4(2a) = 8a\).

      Therefore, \(6a + 8a = 6.3\) or \(14a = 6.3\), which gives \(a = 0.45\).

      In other words, the cost of 1 apple is $0.45.

3. 1. Solution 1

      Since the sum of the angles in any triangle is \(180^\circ\), then the combined sum of the angles in \(\triangle ABD\), \(\triangle FBG\) and \(\triangle CBE\) is \(3 \cdot 180^\circ\) or \(540^\circ\).

      The nine angles in these triangles include those with measures, in degrees, of \(p,q,r,s,t,u\) as well as the three angles \(\angle ABD\), \(\angle FBG\) and \(\angle CBE\).

      These last three angles form a straight angle, and so their sum is \(180^\circ\).

      Therefore, the sum of the remaining six angles must be \(540^\circ - 180^\circ = 360^\circ\).

      In other words, \(p+q+r+s+t+u = 360\).

      Solution 2

      We repeatedly use the fact that the sum of the angles in any triangle is \(180^\circ\).

      From \(\triangle ABD\), \(\angle ABD = 180^\circ - p^\circ - q^\circ\).

      From \(\triangle FBG\), \(\angle FBG = 180^\circ - r^\circ - s^\circ\).

      From \(\triangle CBE\), \(\angle CBE = 180^\circ - t^\circ - u^\circ\).

      Since \(ABC\) forms a straight line segment, then \[\angle ABD + \angle FBG + \angle CBE = 180^\circ\] which gives \[(180^\circ - p^\circ - q^\circ) + (180^\circ - r^\circ - s^\circ) + (180^\circ - t^\circ - u^\circ) = 180^\circ\] Rearranging, we obtain \(360 = p+q+r+s+t+u\) and so the value of \(p+q+r+s+t+u\) is 360.

   2. Solution 1

      The integer equal to \(10^{20}\) consists of the digit 1 followed by 20 0s.

      The integer equal to \(10^{20} - 1\) thus consists of 20 9s.

      Now, \(n = 10^{20} - 20\) is 19 less than \(10^{20}-1\) which is the integer that consists of 20 9s.

      So \(n=10^{20}-20 = 99\cdots980\) where this integer has 18 9s.

      Therefore, the sum of the digits of \(n\) is \(18(9)+8+0 = 162+8=170\).

      Solution 2

      Since \(10^{20}-20 = 10(10^{19}-2)\) and \(10^{19}-2 = 99\cdots 98\) (where this integer has 18 9s), then \(10^{20}-20 = 99\cdots 980\), where this integer has 18 9s.

      Therefore, the sum of the digits of \(n\) is \(18(9)+8+0 = 162+8=170\).

   3. Solution 1

      Since \(P(2,0)\) and \(Q(8,0)\), then \(PQ = 8-2=6\).

      Let \(h\) be the perpendicular distance from \(V\) to \(PQ\).

      Then the area of \(\triangle VPQ\) equals \(\frac{1}{2}(PQ)h\).

      Since the area of \(\triangle VPQ\) is 12, then \(\frac{1}{2}(PQ)h = 12\) and so \(\frac{1}{2}(6)h = 12\) or \(h = 4\).

      Since \(V\) is below the \(x\)-axis, then the \(y\)-coordinate of \(V\) is \(-4\).

      Since \(V\) is the vertex of a parabola and \(P\) and \(Q\) are points where the parabola intersects the \(x\)-axis, then the \(x\)-coordinate of \(V\) is the average of the \(x\)-coordinates of \(P\) and \(Q\), which is \(\frac{1}{2}(2+8)=5\).

      Finally, the coordinates of \(V\) are \((5,-4)\).

      Solution 2

      Since the parabola intersects the \(x\)-axis at \(P(2,0)\) and \(Q(8,0)\), then the equation of the parabola will be of the form \(y = a(x-2)(x-8)\) for some \(a \neq 0\).

      Completing the square, we obtain \[y = a(x^2 - 10x + 16) = a((x-5)^2 - 9) = a(x-5)^2 - 9a\] From this, we see that the vertex of this parabola has coordinates \((5,-9a)\).

      Since the vertex of the parabola is below the \(x\)-axis, then \(-9a<0\) or \(a>0\).

      Now \(\triangle VPQ\) has base \(PQ\) along the \(x\)-axis (which has length \(8 - 2 = 6\)).

      The corresponding height is the perpendicular distance from \(V\) to the \(x\)-axis. This equals \(9a\), since \(a>0\).

      Since the area of \(\triangle VPQ\) is 12, then \(\frac{1}{2}(6)(9a) = 12\) or \(27a = 12\) which gives \(a = \frac{4}{9}\).

      Finally, substituting \(a = \frac{4}{9}\) into \((5,-9a)\) gives the conclusion that the coordinates of \(V\) are \((5,-4)\).

4. 1. Rewriting \(\sin^2\theta + 2\cos^2\theta = \frac{7}{4}\), we get \((\sin^2\theta + \cos^2\theta) + \cos^2\theta = \frac{7}{4}\).

      Since \(\sin^2\theta + \cos^2\theta = 1\) for any angle \(\theta\), then \(1 + \cos^2\theta = \frac{7}{4}\) and so \(\cos^2\theta = \frac{3}{4}\) or \(\cos\theta = \pm \frac{\sqrt{3}}{2}\).

      Since \(0^\circ \leq \theta \leq 180^\circ\), then \(\cos\theta = \frac{\sqrt{3}}{2}\) exactly when \(\theta = 30^\circ\).

      Since \(0^\circ \leq \theta \leq 180^\circ\), then \(\cos\theta = -\frac{\sqrt{3}}{2}\) exactly when \(\theta = 150^\circ\).

      Therefore, \(\theta = 30^\circ\) or \(\theta = 150^\circ\).

      (We can check by substitution that each of these values satisfies the original equation.)

   2. Let the radius of the smaller circle be \(r\) cm and let the radius of the larger circle be \(R\) cm.

      Thus, the circumference of the smaller circle is \(2\pi r\) cm, the circumference of the larger circle is \(2 \pi R\) cm, the area of the smaller circle is \(\pi r^2\mbox{ cm}^2\), and the area of the larger circle is \(\pi R^2\mbox{ cm}^2\).

      Since the sum of the radii of the two circles is 10 cm, then \(r+R= 10\).

      Since the circumference of the larger circle is 3 cm larger than the circumference of the smaller circle, then \(2\pi R - 2 \pi r = 3\), or \(2\pi(R-r) = 3\).

      Then the difference, in \(\mbox{cm}^2\), between the area of the larger circle and the area of the smaller circle is \[\pi R^2 - \pi r^2 = \pi(R-r)(R+r) = \tfrac{1}{2}[2\pi(R-r)](R+r) = \tfrac{1}{2}(3)(10)=15\] Therefore, the difference between the areas is \(15\mbox{ cm}^2\).

5. 1. When the price of \(\$p\) is raised by \(n\%\), the price is multiplied by \(1 + \dfrac{n}{100}\).

      When the new price is reduced by \(20\%\), the new price is multiplied by \(1 - \dfrac{20}{100} = \dfrac{80}{100}\).

      Therefore, after these two price adjustments, the price is \(\$p\left(1 + \dfrac{n}{100}\right)\left(\dfrac{80}{100}\right)\).

      We are told that this final price is \(20\%\) higher than \(\$p\), and so the final price equals \(\$p\left(1 + \dfrac{20}{100}\right)\) or \(\$p \left(\dfrac{120}{100}\right)\).

      In other words, \[\$p\left(1 + \dfrac{n}{100}\right)\left(\dfrac{80}{100}\right) = \$p \left(\dfrac{120}{100}\right)\] Simplifying and using the fact that \(p \neq 0\), we obtain \(80\left(1 + \dfrac{n}{100}\right)=120\).

      Thus, \(1 + \dfrac{n}{100} = \dfrac{120}{80} = \dfrac{3}{2} = \dfrac{150}{100}\) and so \(\dfrac{n}{100} = \dfrac{50}{100}\) or \(n = 50\).

   2. Solution 1

      Let \(m=f(n)\). The equation \(f(f(n))=3\) becomes \(f(m) = 3\).

      Suppose that \(f(m) = 3\) and \(m\) is odd.

      By definition, we have \(f(m)=m-1=3\) and so \(m=4\), which is not odd, so this case cannot happen.

      Suppose that \(f(m) = 3\) and \(m\) is even.

      By definition, we have \(f(m) = m^2 - 1 = 3\) and so \(m^2 = 4\) or \(m = \pm 2\), each of which is even.

      Therefore, if \(f(f(n))=3\), then \(f(n) = 2\) or \(f(n) = -2\).

      Suppose that \(f(n) = 2\) or \(f(n) = -2\) and \(n\) is odd.

      By definition, we have \(n-1=2\) (giving \(n=3\)) or \(n-1=-2\) (giving \(n=-1\)). Each of these resulting values of \(n\) is odd.

      Suppose that \(f(n) = 2\) or \(f(n) = -2\) and \(n\) is even.

      Then \(n^2 - 1 = 2\) or \(n^2 - 1=-2\) which give \(n^2 = 3\) or \(n^2 = -1\), neither of which is possible if \(n\) is an integer.

      Thus, the integers \(n\) for which \(f(f(n)) = 3\) are \(n=3\) and \(n=-1\).

      (We can check by substitution that each of these satisfies the original equation.)

      Solution 2

      We consider the cases of \(n\) even and \(n\) odd separately.

      Suppose that \(n\) is even.

      Then \(n^2\) is even and so \(f(n) = n^2-1\) must be odd.

      Thus, \(f(f(n)) = f(n^2 - 1) = (n^2-1)-1 = n^2-2\), since \(f(m) = m -1\) when \(m\) is odd.

      For \(n\) to be even and \(f(f(n))=3\), we must have \(n^2 - 2 = 3\) or \(n^2 = 5\).

      There are no integer solutions to this equation, and so there are no solutions in this case.

      Suppose that \(n\) is odd.

      Then \(f(n) = n-1\) must be even.

      Thus, \(f(f(n)) = f(n-1) = (n-1)^2-1 = n^2-2n + 1 - 1 = n^2 - 2n\).

      For \(n\) to be odd and \(f(f(n))=3\), we must have \(n^2 - 2n = 3\) or \(n^2 - 2n - 3 = 0\).

      Factoring, we obtain \((n-3)(n+1)=0\) and so \(n=3\) or \(n=-1\), both of which are odd.

      Thus, the integers \(n\) for which \(f(f(n)) = 3\) are \(n=3\) and \(n=-1\).

      (We can check by substitution that each of these satisfies the original equation.)

6. 1. Since \(10^y \neq 0\), the equation \(\dfrac{1}{32} = \dfrac{x}{10^y}\) is equivalent to \(10^y = 32x\).

      So the given question is equivalent to asking for the smallest positive integer \(x\) for which \(32x\) equals a positive integer power of 10.

      Now \(32 = 2^5\) and so \(32x = 2^5 x\).

      For \(32x\) to equal a power of 10, each factor of 2 must be matched with a factor of 5.

      Therefore, \(x\) must be divisible by \(5^5\) (that is, \(x\) must include at least 5 powers of 5), and so \(x \geq 5^5 = 3125\).

      But \(32(5^5) = 2^5 5^5 = 10^5\), and so if \(x = 5^5 = 3125\), then \(32x\) is indeed a power of 10, namely \(10^5\).

      This tells us that the smallest positive integer \(x\) for which \(\dfrac{1}{32} = \dfrac{x}{10^y}\) for some positive integer \(y\) is \(x = 5^5 = 3125\).

   2. Solution 1

      Since the three side lengths of a right-angled triangle form an arithemetic sequence and must include \(60\), then the three side lengths are \(60, 60+d, 60+2d\) or \(60-d,60,60+d\) or \(60-2d,60-d,60\), for some \(d \geq 0\).

      For a triangle with sides of length \(60, 60+d, 60+2d\) to be right-angled, by the Pythagorean Theorem, the following equivalent equations must be true: \[\begin{aligned} 60^2 + (60+d)^2 & = (60+2d)^2 \\ 3600 + 3600 + 120d + d^2 & = 3600 + 240d + 4d^2 \\ 0 & = 3d^2 + 120d - 3600 \\ 0 & = d^2 + 40d - 1200 \\ 0 & = (d+60)(d-20) \end{aligned}\] (Note that, since \(d \geq 0\), then \(60+2d\) must be the hypotenuse of the triangle.)

      Since \(d\geq0\), then \(d=20\), which gives the triangle with side lengths \(60,80,100\).

      The longest side length is the hypotenuse and the shorter two sides meet at right angles, giving an area of \(\frac{1}{2}(60)(80)=2400\).

      For a triangle with sides of length \(60-d, 60, 60+d\) to be right-angled, by the Pythagorean Theorem, the following equivalent equations must be true: \[\begin{aligned} (60-d)^2 + 60^2 & = (60+d)^2 \\ 3600 -120d + d^2 + 3600 & = 3600 + 120d + d^2 \\ 3600 & = 240d \\ d & = 15\end{aligned}\] Since \(d\geq0\), then \(d=15\) is admissible, which gives the triangle with side lengths \(45,60,75\).

      Using a similar analysis, the area of this triangle is \(\frac{1}{2}(45)(60)=1350\).

      For a triangle with sides of length \(60-2d, 60-d, 60\) to be right-angled, by the Pythagorean Theorem, the following equivalent equations must be true: \[\begin{aligned} (60-2d)^2 + (60-d)^2 & = 60^2 \\ 3600 -240d + 4d^2 + 3600 - 120d + d^2 & = 3600 \\ 5d^2 - 360d + 3600 & = 0 \\ d^2 - 72d + 720 & = 0\\ (d-60)(d-12) & = 0\end{aligned}\] Since \(d\geq0\), then \(d=60\) or \(d=12\), which give possible side lengths of \(-60,0,60\) (which do not form a triangle) and \(36,48,60\) (which do form a triangle).

      Using a similar analysis, the area of this triangle is \(\frac{1}{2}(36)(48) = 864\).

      Therefore, the possible values for the area of such a triangle are \(2400\), \(1350\), and \(864\).

      Solution 2

      Suppose that a triangle has side lengths in arithemetic sequence.

      Then the side lengths can be written as \(a-d, a, a+d\) for some \(a>0\) and \(d \geq 0\).

      Note that \(a-d \leq a \leq a+d\).

      For such a triangle to be right-angled, by the Pythagorean Theorem, the following equivalent equations are true: \[\begin{aligned} (a-d)^2 + a^2 & = (a+d)^2 \\ a^2 - 2ad + d^2 + a^2 & = a^2 + 2ad + d^2 \\ a^2 & = 4ad\end{aligned}\] Since \(a>0\), then \(a=4d\), and so the side lengths of the triangle are \(a-d=3d\), \(a=4d\), and \(a+d=5d\) for some \(d \geq 0\).

      (Note that such triangles are all similar to the 3-4-5 triangle.)

      If such a triangle has 60 as a side length, then there are three possibilities:

      1. \(3d=60\): This gives \(d=20\) and side lengths \(60,80,100\).

         Since the triangle is right-angled and its hypotenuse has length 100, then its area will equal \(\frac{1}{2}(60)(80) = 2400\).

      2. \(4d=60\): This gives \(d=15\) and side lengths \(45,60,75\).

         In a similar way to case (i), its area will equal \(\frac{1}{2}(45)(60) = 1350\).

      3. \(5d=60\): This gives \(d=12\) and side lengths \(36,48,60\).

         In a similar way to case (i), its area will equal \(\frac{1}{2}(36)(48) = 864\).

      Therefore, the possible values for the area of such a triangle are \(2400\), \(1350\), and \(864\).

7. 1. Solution 1

      Suppose that Amrita paddles the kayak for \(p\) km and swims for \(s\) km.

      Since Amrita leaves the kayak in the lake and it does not move, then Zhang swims \(p\) km and paddles the kayak for \(s\) km.

      Note that each paddles at 7 km/h and each swims at 2 km/h and each takes exactly 90 minutes (or 1.5 hours) to complete the trip.

      If \(s<p\), then Amrita would paddle farther and swim less distance than Zhang and so would reach the other side in less time than Zhang.

      If \(s>p\), then Zhang would paddle farther and swim less distance than Amrita and so would reach the other side in less time than Amrita.

      Since they each take 90 minutes, then we must have \(s=p\).

      Alternatively, since each paddles at 7 km/h and each swims at 2 km/h and each takes exactly 90 minutes (or 1.5 hours) to complete the trip, then we obtain the two equations \[\frac{p}{7} + \frac{s}{2} = 1.5 \qquad \frac{p}{2} + \frac{s}{7} = 1.5\] Using the fact that the right sides of these equations are equal, we obtain \[\begin{aligned} \frac{p}{7} + \frac{s}{2} & = \frac{s}{7} + \frac{p}{2} \\ \frac{s}{2} - \frac{s}{7} & = \frac{p}{2} - \frac{p}{7} \\ s\left(\frac{1}{2}-\frac{1}{7}\right) & = p\left(\frac{1}{2}-\frac{1}{7}\right) \\ s & = p\end{aligned}\] Therefore, \(\dfrac{p}{7} + \dfrac{p}{2} = 1.5\) or \(\dfrac{9}{14}p = 1.5 = \dfrac{3}{2}\) and so \(p = \dfrac{7}{3}\).

      For Amrita to paddle these \(\dfrac{7}{3}\) km at 7 km/h, it takes \(\dfrac{7/3}{7} = \dfrac{1}{3}\) hour, or 20 minutes.

      For Zhang to swim these \(\dfrac{7}{3}\) km at 2 km/h, it takes \(\dfrac{7/3}{2} = \dfrac{7}{6}\) hour, or 70 minutes.

      The kayak is not being paddled for the period of time from when Amrita stops paddling to the time when Zhang stops swimming, which is a period of \(70 - 20 = 50\) minutes.

      Solution 2

      Let \(t_1\) hours be the length of time during which Amrita paddles and Zhang swims.

      Let \(t_2\) hours be the length of time during which Amrita swims and Zhang swims; the kayak is not moving during this time.

      Let \(t_3\) hours be the length of time during which Amrita swims and Zhang paddles.

      Let \(d\) km be the total distance across the lake.

      Since Amrita paddles at 7 km/h and swims at 2 km/h, then \(7t_1 + 2t_2 + 2t_3 = d\).

      Since Zhang paddles at 7 km/h and swims at 2 km/h, then \(2t_1 + 2t_2 + 7t_3 = d\).

      Since the kayak travels at 7 km/h and does not move while both Amrita and Zhang are swimming, then \(7t_1 + 0t_2 + 7t_3 = d\).

      Since Amrita and Zhang each take 90 minutes (\(\frac{3}{2}\) hours) to cross the lake, then the total time gives \(t_1+t_2+t_3=\frac{3}{2}\).

      From \(7t_1 + 2t_2 + 2t_3 = d\) and \(2t_1 + 2t_2 + 7t_3 = d\), we obtain \(7t_1 + 2t_2 + 2t_3 = 2t_1 + 2t_2 + 7t_3\) or \(5t_1 = 5t_3\) and so \(t_1=t_3\).

      Since \(7t_1 + 2t_2 + 2t_3 = d\) and \(7t_1 + 0t_2 + 7t_3 = d\) and \(t_1=t_3\), then \(7t_1+2t_2+2t_1=7t_1 + 7t_1\) or \(2t_2 = 5t_1\) or \(t_2 = \frac{5}{2}t_1\).

      Since \(t_1+t_2+t_3 = \frac{3}{2}\), then \(t_1+\frac{5}{2}t_1 + t_1 = \frac{3}{2}\) or \(\frac{9}{2}t_1 = \frac{3}{2}\) and so \(t_1 = \frac{1}{3}\).

      Thus, \(t_2 = \frac{5}{2}\cdot \frac{1}{3} = \frac{5}{6}\) hours (or 50 minutes) is the period of time that the kayak is not moving.

   2. From the first equation, \(x\left(\tfrac{1}{2}+y-2x^2\right) = 0\), we obtain \(x = 0\) or \(\tfrac{1}{2}+y-2x^2 = 0\).

      From the second equation, \(y\left(\tfrac{5}{2}+x-y\right) = 0\), we obtain \(y = 0\) or \(\tfrac{5}{2}+x-y = 0\).

      If \(x=0\), the first equation is satisified.

      For the second equation to be true in this case, we need \(y = 0\) (giving the solution \((0,0)\)) or \(\tfrac{5}{2}+0-y = 0\). The second equation gives \(y = \frac{5}{2}\) (giving the solution \((0,\frac{5}{2})\)).

      If \(y=0\), the second equation is satisified.

      For the first equation to be true in this case, we need \(x=0\) (giving the solution \((0,0)\)) or \(\tfrac{1}{2}+0-2x^2 = 0\). The second equation gives \(x^2 = \frac{1}{4}\) or \(x = \pm \frac{1}{2}\) (giving the solutions \((\frac{1}{2},0)\) and \((-\frac{1}{2},0)\)).

      So far, we have accounted for all solutions with \(x=0\) or \(y=0\).

      If \(x \neq 0\) and \(y \neq 0\), then for both equations to be true, we need \(\tfrac{1}{2}+y-2x^2 = 0\) (or \(1 + 2y - 4x^2 = 0\)) and \(\tfrac{5}{2}+x-y = 0\) (or \(5+2x-2y=0\)).

      Adding these two equations, we obtain \(6 + 2x - 4x^2 = 0\).

      This is equivalent to \(2x^2 - x - 3=0\) or \((2x - 3)(x+1) = 0\), whose solutions are \(x = \frac{3}{2}\) and \(x = -1\).

      The equation \(\tfrac{5}{2}+x-y = 0\) tells us that \(y = x + \frac{5}{2}\).

      If \(x = \frac{3}{2}\), then \(y = 4\); if \(x = -1\), then \(y = \frac{3}{2}\).

      Therefore, the complete list of pairs that satisfy the given system of equations is \[(x,y) = (0,0), (0,\tfrac{5}{2}), (\tfrac{1}{2},0), (-\tfrac{1}{2},0), (\tfrac{3}{2},4), (-1,\tfrac{3}{2})~.\]

8. 1. Let \(\angle EAF = \theta\).

      Since \(ABCD\) is a parallelogram, then \(AB\) and \(DC\) are parallel with \(AB = DC\), and \(DA\) and \(CB\) are parallel with \(DA = CB\).

      Since \(AE\) is perpendicular to \(DC\) and \(AB\) and \(DC\) are parallel, then \(AE\) is perpendicular to \(AB\).

      In other words, \(\angle EAB = 90^\circ\), and so \(\angle FAB = 90^\circ - \theta\).

      Since \(\triangle AFB\) is right-angled at \(F\) and \(\angle FAB = 90^\circ - \theta\), then \(\angle ABF = \theta\).

      Using similar arguments, we obtain that \(\angle DAE = 90^\circ - \theta\) and \(\angle ADE = \theta\).

      

      Since \(\cos(\angle EAF) = \cos\theta = \frac{1}{3}\) and \(\cos^2\theta+\sin^2\theta = 1\), then \[\sin \theta = \sqrt{1-\cos^2\theta} = \sqrt{1-\tfrac{1}{9}} = \sqrt{\tfrac{8}{9}} = \tfrac{2\sqrt{2}}{3}\] (Note that \(\sin \theta > 0\) since \(\theta\) is an angle in a triangle.)

      In \(\triangle AFB\), \(\sin \theta = \dfrac{AF}{AB}\) and \(\cos \theta = \dfrac{FB}{AB}\).

      Since \(AF = 32\) and \(\sin \theta = \frac{2\sqrt{2}}{3}\), then \(AB = \dfrac{AF}{\sin\theta} = \dfrac{32}{2\sqrt{2}/3} = \dfrac{48}{\sqrt{2}} = 24\sqrt{2}\).

      Since \(AB = 24\sqrt{2}\) and \(\cos \theta = \frac{1}{3}\), then \(FB = AB \cos\theta = 24\sqrt{2}(\frac{1}{3}) = 8\sqrt{2}\).

      In \(\triangle AED\), \(\sin \theta = \dfrac{AE}{AD}\) and \(\cos \theta = \dfrac{DE}{AD}\).

      Since \(AE = 20\) and \(\sin \theta = \frac{2\sqrt{2}}{3}\), then \(AD = \dfrac{AE}{\sin\theta} = \dfrac{20}{2\sqrt{2}/3} = \dfrac{30}{\sqrt{2}} = 15\sqrt{2}\).

      Since \(AD = 15\sqrt{2}\) and \(\cos \theta = \frac{1}{3}\), then \(DE = AD \cos\theta = 15\sqrt{2}(\frac{1}{3}) = 5\sqrt{2}\).

      (To calculate \(AD\) and \(DE\), we could also have used the fact that \(\triangle ADE\) is similar to \(\triangle ABF\).)

      Finally, the area of quadrilateral \(AECF\) equals the area of parallelogram \(ABCD\) minus the combined areas of \(\triangle AFB\) and \(\triangle ADE\).

      The area of parallelogram \(ABCD\) equals \(AB \cdot AE = 24\sqrt{2}\cdot 20 = 480\sqrt{2}\).

      The area of \(\triangle AFB\) equals \(\frac{1}{2}(AF)(FB) = \frac{1}{2}(32)(8\sqrt{2}) = 128\sqrt{2}\).

      The area of \(\triangle AED\) equals \(\frac{1}{2}(AE)(DE) = \frac{1}{2}(20)(5\sqrt{2}) = 50\sqrt{2}\).

      Thus, the area of quadrilateral \(AECF\) is \(480\sqrt{2} - 128\sqrt{2} - 50\sqrt{2} = 302\sqrt{2}\).

   2. Note that \(x \neq 1\) since \(1\) cannot be the base of a logarithm. This tells us that \(\log x \neq 0\).

      Using the fact that \(\log_a b = \dfrac{\log b}{\log a}\) and then using other logarithm laws, we obtain the following equivalent equations: \[\begin{aligned} \log_4 x - \log_x 16 & = \tfrac{7}{6} - \log_x 8 \\ \dfrac{\log x}{\log 4} - \dfrac{\log 16}{\log x} & = \dfrac{7}{6} - \dfrac{\log 8}{\log x} \qquad\mbox{(note that $x \neq 1$, so $\log x \neq 0$)}\\ \dfrac{\log x}{\log 4} & = \dfrac{7}{6} + \dfrac{\log 16 - \log 8}{\log x}\\ \dfrac{\log x}{\log(2^2)} & = \dfrac{7}{6} + \dfrac{\log(\frac{16}{8})}{\log x} \\ \dfrac{\log x}{2\log 2} & = \dfrac{7}{6} + \dfrac{\log 2}{\log x}\\ \dfrac{1}{2}\left(\dfrac{\log x}{\log 2}\right) & = \dfrac{7}{6} + \dfrac{\log 2}{\log x}\end{aligned}\] Letting \(t = \dfrac{\log x}{\log 2} = \log_2 x\) and noting that \(t \neq 0\) since \(x \neq 1\), we obtain the following equations equivalent to the previous ones: \[\begin{aligned} \dfrac{t}{2} & = \dfrac{7}{6} + \dfrac{1}{t} \\ 3t^2 & = 7t + 6 \qquad\mbox{(multiplying both sides by $6t$)}\\ 3t^2 - 7t - 6 & = 0 \\ (3t+2)(t - 3) & = 0\end{aligned}\] Therefore, the original equation is equivalent to \(t = -\frac{2}{3}\) or \(t= 3\).

      Converting back to the variable \(x\), we obtain \(\log_2 x = -\frac{2}{3}\) or \(\log_2 x = 3\), which gives \(x = 2^{-2/3}\) or \(x = 2^3 = 8\).

9. 1. There are \(2^{10} = 1024\) strings of ten letters, each of which is \(A\) or \(B\), because there are 2 choices for each of the 10 positions in the string.

      We determine the number of these strings that do not include the “substring” \(ABBA\) (that is, that do not include consecutive letters \(ABBA\)) by counting the number of strings that do include the substring \(ABBA\) and subtracting this total from 1024.

      If a string includes the substring \(ABBA\), there are 7 possible positions in which this substring could start (\(ABBAxxxxxx\), \(xABBAxxxxx\), \(\ldots\), \(xxxxxxABBA\)).

      There are 2 choices for each of the remaining 6 letters in such a string, so there are \(7\cdot 2^6 = 448\) occurrences of the substring \(ABBA\) among the 1024 strings.

      This does not mean that there are 448 strings that contain the substring \(ABBA\). Since \(ABBA\) can appear multiple times in a single string, this total will count some strings more than once. (For example, the string \(ABBAAAABBA\) is included in both the first and seventh of these categories, so this string is counted twice.)

      So we must “correct” this total of 448 by accounting for the strings in which \(ABBA\) occurs more than once.

      We note that, since two substrings of \(ABBA\) can overlap in 0 letters (for example, \(ABBAABBAxx\)) or in 1 letter (for example, \(ABBABBAxxx\)), then the maximum number of times that the substring \(ABBA\) can appear is 3, and there is only one such string: \(ABBABBABBA\).

      If a string contains two copies of \(ABBA\) that overlap, then it must be of one of the following forms:

      \[ABBABBAxxx \qquad xABBABBAxx \qquad xxABBABBAx \qquad xxxABBABBA \] Since there are 4 choices for the starting position of \(ABBABBA\) and 2 choices for each of the three unknown letters, then there are \(4 \cdot 2^3 = 32\) occurrences of \(ABBABBA\) among all of these strings.

      But the string \(ABBABBABBA\) is counted in each of the first and last categories, so we subtract 2 occurrences from this total to obtain 30, the total number of strings of ten letters that included exactly two overlapping copies of \(ABBA\). (We’ll count the string \(ABBABBABBA\) later.)

      If a string contains exactly two substrings of \(ABBA\) and these do not overlap, then it must be of one of the following forms:

      \[ABBAABBAxx \qquad ABBAxABBAx \qquad ABBAxxABBA\] \[xABBAABBAx \qquad xABBAxABBA \qquad xxABBAABBA \] Since there are 6 such forms and 2 choices for each of the 2 unknown letters in each case, then there appear to be \(6 \cdot 2^2 = 24\) such strings.

      This total includes the string \(ABBABBABBA\) in the third category, so we subtract 1 from this total to obtain 23, the total number of strings of ten letters that include exactly two copies of \(ABBA\) which do not overlap.

      So there are 30 strings that contain exactly two overlapping substrings \(ABBA\), 23 strings that contain exactly two non-overlapping substrings \(ABBA\), and 1 string that contains exactly three substrings \(ABBA\).

      To get the total number of strings with one or more substrings \(ABBA\) we take the total number of occurrences of \(ABBA\) (\(448\)), subtract the number of strings with exactly two substrings \(ABBA\) (since these were included twice in the original count), and subtract two times the number of strings with exactly three substrings \(ABBA\) (since these were included three times in the original count).

      Therefore, there are \(448 - 23 - 30 - 2\cdot 1 = 393\) strings that include at least one substring \(ABBA\), and so there are \(1024-393 = 631\) strings of ten letters that do not include the substring \(ABBA\).

   2. Solution 1

      Rotate \(\triangle DFC\) through an angle of \(90^\circ\) counterclockwise about \(D\), so that \(DC\) now lies along \(DA\) and \(F'\) is outside the square, as shown.

      Join \(F'\) to \(E\).

      

      Since \(AC\) is a diagonal of square \(ABCD\), then \(\angle EAD = \angle FCD = 45^\circ\).

      Since \(\angle EAD = 45^\circ\) and \(\angle F'AD = \angle FCD = 45^\circ\), then \(\angle F'AE = 45^\circ + 45^\circ = 90^\circ\).

      By the Pythagorean Theorem in \(\triangle F'AE\), we have \(F'E^2 = F'A^2 + AE^2\).

      But \(F'A = FC = z\) and \(AE = x\), so \(F'E^2 = z^2 + x^2\).

      To show that \(y^2 = x^2 + z^2\), it is sufficient to show that \(F'E=y\).

      Consider \(\triangle F'DE\) and \(\triangle FDE\).

      Note that \(F'D = FD\) and \(\angle F'DA = \angle FDC\) by construction and \(ED = ED\).

      Also, \(\angle F'DE = \angle F'DA + \angle EDA = \angle FDC + \angle EDA = 90^\circ - \angle EDF = 45^\circ\), which tells us that \(\angle F'DE = \angle FDE = 45^\circ\).

      Therefore, \(\triangle F'DE\) is congruent to \(\triangle FDE\) (side-angle-side), and so \(F'E=FE = y\).

      This gives us the desired conclusion that \(y^2 = x^2 + z^2\).

      Solution 2

      Since \(AC\) is a diagonal of square \(ABCD\), then \(\angle EAD = \angle FCD = 45^\circ\).

      Let \(\angle ADE = \theta\).

      Since the angles in a triangle have a sum of \(180^\circ\), then \[\angle AED = 180^\circ - \angle EAD - \angle ADE = 180^\circ - 45^\circ - \theta = 135^\circ - \theta\] Since \(AEF\) is a straight angle, then \(\angle DEF = 180^\circ - \angle AED = 180^\circ - (135^\circ - \theta) = 45^\circ + \theta\).

      Continuing in this way, we find that \(\angle EFD = 90^\circ - \theta\), \(\angle DFC = 90^\circ + \theta\), and \(\angle FDC = 45^\circ - \theta\).

      

      Using the sine law in \(\triangle AED\), we see that \(\dfrac{AE}{\sin \angle ADE} = \dfrac{ED}{\sin \angle EAD}\) or \(\dfrac{x}{\sin \theta} = \dfrac{ED}{\sin 45^\circ}\).

      Using the sine law in \(\triangle DEF\), we see that \(\dfrac{EF}{\sin \angle EDF} = \dfrac{ED}{\sin \angle EFD}\) or \(\dfrac{y}{\sin 45^\circ} = \dfrac{ED}{\sin (90^\circ-\theta)}\).

      Using the sine law in \(\triangle DEF\), we see that \(\dfrac{EF}{\sin \angle EDF} = \dfrac{FD}{\sin \angle DEF}\) or \(\dfrac{y}{\sin 45^\circ} = \dfrac{FD}{\sin (45^\circ+\theta)}\).

      Using the sine law in \(\triangle DFC\), we get \(\dfrac{FC}{\sin \angle FDC} = \dfrac{FD}{\sin \angle DCF}\) or \(\dfrac{z}{\sin (45^\circ-\theta)} = \dfrac{FD}{\sin 45^\circ}\).

      Dividing the first of these equations by the second, we obtain \(\dfrac{x\sin45^\circ}{y\sin\theta} = \dfrac{\sin(90^\circ-\theta)}{\sin 45^\circ}\) or \(\dfrac{x}{y} = \dfrac{\sin(90^\circ-\theta)\sin\theta}{\sin^2 45^\circ}\).

      Dividing the fourth of these equations by the third, we obtain \(\dfrac{z\sin45^\circ}{y\sin(45^\circ-\theta)} = \dfrac{\sin(45^\circ+\theta)}{\sin 45^\circ}\) or \(\dfrac{z}{y} = \dfrac{\sin(45^\circ+\theta)\sin(45^\circ-\theta)}{\sin^2 45^\circ}\).

      Since \(\sin(90^\circ - \alpha) = \cos \alpha\) for every angle \(\alpha\), then \(\sin(90^\circ - \theta) = \cos \theta\).

      Also, \(\sin(45^\circ + \theta) = \sin(90^\circ - (45^\circ - \theta)) = \cos(45^\circ - \theta)\).

      Using this and the fact that \(\dfrac{1}{\sin^2 45^\circ} = \dfrac{1}{(1/\sqrt{2})^2} = 2\), the expressions for \(\dfrac{x}{y}\) and \(\dfrac{z}{y}\) become \[\dfrac{x}{y} = 2\cos\theta\sin\theta = \sin2\theta\] and \[\dfrac{z}{y} = 2\cos(45^\circ-\theta)\sin(45^\circ-\theta) = \sin(2(45^\circ - \theta)) = \sin(90^\circ - 2\theta) = \cos 2\theta\] Finally, this tells us that \[\dfrac{x^2}{y^2} + \dfrac{z^2}{y^2} = \left(\dfrac{x}{y}\right)^2 + \left(\dfrac{z}{y}\right)^2 = \sin^2 2\theta + \cos^2 2\theta = 1\] Since \(\dfrac{x^2}{y^2} + \dfrac{z^2}{y^2} = 1\), then \(x^2+z^2 = y^2\), as required.

10. 1. Here, \(k=10\) and so there are 10 balls in each bag.

       Since there are 10 balls in each bag, there are \(10 \cdot 10 = 100\) pairs of balls that can be chosen.

       Let \(a\) be the number on the first ball chosen and \(b\) be the number on the second ball chosen. To determine \(P(10)\), we count the number of pairs \((a,b)\) for which \(ab\) is divisible by 10.

       If the number of pairs is \(m\), then \(P(10) = \dfrac{m}{100}\).

       For \(ab\) to be divisible by 10, at least one of \(a\) and \(b\) must be a multiple of 5 and at least one of \(a\) and \(b\) must be even.

       If \(a=10\) or \(b=10\), then the pair \((a,b)\) gives a product \(ab\) divisible by 10.

       In this case, we obtain the 19 pairs \[(a,b)=(1,10),(2,10),\ldots,(9,10),(10,10),(10,9),\ldots,(10,2),(10,1)\] If neither \(a\) nor \(b\) equals 10, then either \(a=5\) or \(b=5\) in order for \(a\) or \(b\) to be divisible by 5.

       In this case, the other of \(a\) and \(b\) must be even and not equal to 10. (We have already counted the pairs where \(a=10\) or \(b=10\).)

       In this case, we obtain the 8 pairs \[(a,b)=(5,2),(5,4),(5,6),(5,8),(2,5),(4,5),(6,5),(8,5)\] From our work above, there are no additional pairs for which \(ab\) is divisible by 10.

       Thus, there are \(19+8=27\) pairs \((a,b)\) for which \(ab\) is divisible by 10, which means that \(P(10) = \frac{27}{100}\).

       (We note that we could have made a \(10\) by \(10\) table that listed all possible combinations of \(a\) and \(b\) and their product, from which we could obtain \(P(10)\).)

    2. Let \(n\) be a positive integer with \(n \geq 2\).

       Consider \(f(n) = 2n-1\). This is a polynomial in \(n\).

       We demonstrate that \(P(n) \geq \dfrac{2n-1}{n^2}\) for all positive integers \(n\) with \(n \geq 2\) and that \(P(n) = \dfrac{2n-1}{n^2}\) for infinitely many positive integers \(n\) with \(n \geq 2\).

       Suppose that there are two bags, each containing \(n\) balls labelled from \(1\) to \(n\).

       Since there are \(n\) balls in each bag, there are \(n^2\) pairs of balls that can be chosen.

       Let \(a\) be the number on the first ball chosen and \(b\) be the number on the second ball chosen.

       The pairs \[(a,b) = (1,n),(2,n),\ldots,(n-1,n),(n,n),(n,n-1),\ldots,(n,2),(n,1)\] each have the property that \(ab\) is divisible by \(n\).

       There are \((n-1)+1+(n-1)=2n-1\) of these pairs.

       Therefore, at least \(2n-1\) of the pairs of balls that can be chosen have labels whose product is divisible by \(n\).

       Since there are \(n^2\) pairs that can be chosen and the number of pairs of balls with the desired property is at least \(2n-1\), then \(P(n) \geq \dfrac{2n-1}{n^2}\).

       This proves the first part of what we needed to prove.

       Next, suppose that \(n = p\), a prime number.

       For \(ab\) to be divisible by \(p\), then either \(a\) is divisible by \(p\) or \(b\) is divisible by \(p\) (or both). (This property is not true when \(p\) is not a prime number; for example, \(2 \cdot 2\) is divisible by 4 even though neither factor is divisible by 4.)

       Since \(1 \leq a \leq p\) and \(1 \leq b \leq p\), then if either \(a\) is divisible by \(p\) or \(b\) is divisible by \(p\) (or both), we must have either \(a=p\) or \(b=p\), or both.

       In other words, \(ab\) is divisible by \(p\) exactly when \((a,b)\) is in the list \[(1,p),(2,p),\ldots,(p-1,p),(p,p),(p,p-1),\ldots,(p,2),(p,1)\] There are \(2p-1\) pairs in this list and these are the only pairs for which \(ab\) is divisible by \(p\).

       Therefore, \(P(n) = \dfrac{2n-1}{n^2}\) when \(n\) is a prime number.

       Since there are infinitely many prime numbers, then \(P(n) = \dfrac{2n-1}{n^2}\) for infinitely many positive integers \(n\) with \(n \geq 2\).

       Thus, \(f(n)=2n-1\) is a polynomial with the desired properties.

    3. Let \(N = 2^k\), where \(k\) is a positive integer with \(k \geq 2\).

       Suppose that there are two bags, each containing \(N\) balls labelled from \(1\) to \(N\).

       Since there are \(N\) balls in each bag, there are \(N^2\) pairs of balls that can be chosen.

       Let \(a\) be the number on the first ball chosen and \(b\) be the number on the second ball chosen.

       Let \(j\) be a positive integer with \(1 \leq j \leq k-1\).

       Consider pairs of the form \((a,b)=(2^j x,2^{k-j} y)\) where \(x\) and \(y\) are odd positive integers that keep \(a\) and \(b\) in the desired range.

       Note that, in each case, \(ab = (2^j x)(2^{k-j}y) = 2^k xy\) which is divisible by \(N = 2^k\).

       Since \(1 \leq a \leq 2^k\), then \(1 \leq 2^j x \leq 2^k\) and so \(x \leq 2^{k-j}\).

       Since half of the positive integers from \(1\) to \(2^{k-j}\) are odd, then there are \(\frac{1}{2}2^{k-j} = 2^{k-j-1}\) choices for \(x\).

       Similarly, there are \(2^{k-(k-j)-1} = 2^{j-1}\) choices for \(y\).

       Note that each choice of \(x\) and \(y\) gives a unique pair \((a,b)\).

       For any fixed \(j\), there are \(2^{k-j-1}\) choices for \(x\) and \(2^{j-1}\) choices for \(y\).

       Thus, there are \(2^{k-j-1}\cdot 2^{j-1} = 2^{k-2}\) choices of this form for the pair \((a,b)\).

       So for a fixed \(j\) with \(1 \leq j \leq k-1\), this method gives \(2^{k-2}\) pairs \((a,b)\) for which \(ab\) is divisible by \(N\).

       Since there are \(k-1\) different values for \(j\), then there are at least \((k-1)2^{k-2}\) pairs \((a,b)\) for which \(ab\) is divisible by \(N\). (Note that two pairs that come from different values of \(j\) will in fact be different since the number of factors of 2 in their values of \(a\) will be different.)

       Since there are \(N^2\) choices for \((a,b)\), then \[P(N) \geq \dfrac{(k-1)2^{k-2}}{N^2} = \dfrac{(k-1)2^k 2^{-2}}{N^2} = \dfrac{k-1}{4} \cdot \dfrac{1}{N}\] When \(\dfrac{k-1}{4} > 2016\), we will have \(P(N) > 2016\cdot \dfrac{1}{N}\).

       The inequality \(\dfrac{k-1}{4} > 2016\) is equivalent to \(k-1 > 8064\) or \(k > 8065\).

       We want to show that there exists a positive integer \(m\) with \(P(m) > \dfrac{2016}{m}\).

       Set \(m = 2^{8066}\).

       By the work above, \(P(m) \geq \dfrac{8065}{4} \cdot \dfrac{1}{m} > \dfrac{2016}{m}\), as required.