2020 Euclid Contest
Solutions

Tuesday, April 7, 2020
(in North America and South America)

Wednesday, April 8, 2020
(outside of North American and South America)

1. Solution 1:
  
  If $x \neq -2$, then $\dfrac{3x+6}{x+2} = \dfrac{3(x+2)}{x+2} = 3$.
  In other words, for every $x \neq -2$, the expression is equal to 3.
  Therefore, when $x = 11$, we get $\dfrac{3x+6}{x+2} = 3$.
  
  Solution 2:
  
  When $x =11$, we obtain $\dfrac{3x+6}{x+2} = \dfrac{3(11)+6}{11+2} = \dfrac{39}{13} = 3$.
2. Solution 1:
  
  The point at which a line crosses the $y$-axis has $x$-coordinate 0.
  Because $A$ has $x$-coordinate $-1$ and $B$ has $x$-coordinate 1, then the midpoint of $AB$ is on the $y$-axis and is on the line through $A$ and $B$, so is the point at which this line crosses the $x$-axis.
  The midpoint of $A(-1,5)$ and $B(1,7)$ is $\left(\frac{1}{2}(-1+1),\frac{1}{2}(5+7)\right)$ or $(0,6)$.
  Therefore, the line that passes through $A(-1,5)$ and $B(1,7)$ has $y$-intercept 6.
  
  Solution 2:
  
  The line through $A(-1,5)$ and $B(1,7)$ has slope $\dfrac{7-5}{1-(-1)} = \dfrac{2}{2} = 1$.
  Since the line passes through $B(1,7)$, its equation can be written as $y - 7 = 1(x-1)$ or $y=x+6$.
  The line with equation $y=x+6$ has $y$-intercept 6.
3. First, we find the coordinates of the point at which the lines with equations $y = 3x+7$ and $y=x+9$ intersect.
  Equating values of $y$, we obtain $3x+7 = x+9$ and so $2x = 2$ or $x=1$.
  When $x=1$, we get $y = x + 9 = 10$.
  Thus, these two lines intersect at $(1,10)$.
  Since all three lines pass through the same point, the line with equation $y = mx + 17$ passes through $(1,10)$.
  Therefore, $10 = m \cdot 1 + 17$ which gives $m = 10 - 17 = -7$.
1. Suppose that $m$ has hundreds digit $a$, tens digit $b$, and ones (units) digit $c$.
  From the given information, $a$, $b$ and $c$ are distinct, each of $a$, $b$ and $c$ is less than 10, $a = bc$, and $c$ is odd (since $m$ is odd).
  The integer $m = 623$ satisfies all of these conditions. Since we are told there is only one such number, then 623 must be the only answer.
  Why is this the only possible value of $m$?
  We note that we cannot have $b=1$ or $c=1$, otherwise $a=c$ or $a=b$.
  Thus, $b \geq 2$ and $c \geq 2$.
  Since $c \geq 2$ and $c$ is odd, then $c$ can equal 3, 5, 7, or 9.
  Since $b \geq 2$ and $a=bc$, then if $c$ equals 5, 7 or 9, $a$ would be larger than 10, which is not possible.
  Thus, $c=3$.
  Since $b \geq 2$ and $b \neq c$, then $b=2$ or $b \geq 4$.
  If $b \geq 4$ and $c=3$, then $a > 10$, which is not possible.
  Therefore, we must have $c=3$ and $b=2$, which gives $a=6$.
2. Since Eleanor has 100 marbles which are black and gold in the ratio $1:4$, then $\frac{1}{5}$ of her marbles are black, which means that she has $\frac{1}{5} \cdot 100 = 20$ black marbles.
  When more gold marbles are added, the ratio of black to gold is $1:6$, which means that she has $6 \cdot 20 = 120$ gold marbles.
  Eleanor now has $20 + 120 = 140$ marbles, which means that she added $140 - 100 = 40$ gold marbles.
3. First, we see that $\dfrac{n^2+n+15}{n} = \dfrac{n^2}{n} + \dfrac{n}{n} + \dfrac{15}{n} = n + 1 + \dfrac{15}{n}$.
  This means that $\dfrac{n^2+n+15}{n}$ is an integer exactly when $n + 1 + \dfrac{15}{n}$ is an integer.
  Since $n+1$ is an integer, then $\dfrac{n^2+n+15}{n}$ is an integer exactly when $\dfrac{15}{n}$ is an integer.
  The expression $\dfrac{15}{n}$ is an integer exactly when $n$ is a divisor of 15.
  Since $n$ is a positive integer, then the possible values of $n$ are 1, 3, 5, and 15.
1. First, we note that a triangle with one right angle and one angle with measure $45^\circ$ is isosceles.
  This is because the measure of the third angle equals $180^\circ - 90^\circ - 45^\circ = 45^\circ$ which means that the triangle has two equal angles.
  In particular, $\triangle CDE$ is isosceles with $CD = DE$ and $\triangle EFG$ is isosceles with $EF = FG$.
  Since $DE = EF = 1\mbox{ m}$, then $CD = FG = 1\mbox{ m}$.
  Join $C$ to $G$.
  
  Consider quadrilateral $CDFG$. Since the angles at $D$ and $F$ are right angles and since $CD = GF$, it must be the case that $CDFG$ is a rectangle.
  This means that $CG = DF = 2\mbox{ m}$ and that the angles at $C$ and $G$ are right angles.
  Since $\angle CGF = 90^\circ$ and $\angle DCG = 90^\circ$, then $\angle BGC = 180^\circ - 90^\circ - 45^\circ = 45^\circ$ and $\angle BCG = 90^\circ$.
  This means that $\triangle BCG$ is also isosceles with $BC = CG = 2\mbox{ m}$.
  Finally, $BD = BC + CD = 2\mbox{ m} + 1\mbox{ m} = 3\mbox{ m}$.
2. We apply the process two more times:
  
  $\boldsymbol{x}$ $\boldsymbol{y}$
  
  Before Step 1 24 3
  
  After Step 1 27 3
  
  After Step 2 81 3
  
  After Step 3 81 4
  
  $\boldsymbol{x}$ $\boldsymbol{y}$
  
  Before Step 1 81 4
  
  After Step 1 85 4
  
  After Step 2 340 4
  
  After Step 3 340 5
  
  Therefore, the final value of $x$ is 340.
3. The parabola with equation $y = kx^2 + 6x + k$ has two distinct $x$-intercepts exactly when the discriminant of the quadratic equation $kx^2 + 6x + k = 0$ is positive.
  Here, the disciminant equals $\Delta = 6^2 - 4 \cdot k \cdot k = 36 - 4k^2$.
  The inequality $36-4k^2 > 0$ is equivalent to $k^2 < 9$.
  Since $k$ is an integer and $k \neq 0$, then $k$ can equal $-2, -1, 1, 2$.
  (If $k \geq 3$ or $k \leq -3$, we get $k^2 \geq 9$ so no values of $k$ in these ranges give the desired result.)
1. Since $\dfrac{a}{b}<\dfrac{4}{7}$ and $\dfrac{4}{7}<1$, then $\dfrac{a}{b}<1$.
  Since $a$ and $b$ are positive integers, then $a<b$.
  Since the difference between $a$ and $b$ is 15 and $a<b$, then $b = a+15$.
  Therefore, we have $\dfrac{5}{9} < \dfrac{a}{a+15} < \dfrac{4}{7}$.
  We multiply both sides of the left inequality by $9(a+15)$ (which is positive) to obtain $5(a+15) < 9a$ from which we get $5a + 75 < 9a$ and so $4a > 75$.
  From this, we see that $a > \dfrac{75}{4} = 18.75$.
  Since $a$ is an integer, then $a \geq 19$.
  We multiply both sides of the right inequality by $7(a+15)$ (which is positive) to obtain $7a < 4(a+15)$ from which we get $7a < 4a+60$ and so $3a < 60$.
  From this, we see that $a < 20$.
  Since $a$ is an integer, then $a \leq 19$.
  Since $a \geq 19$ and $a \leq 19$, then $a=19$, which means that $\dfrac{a}{b} = \dfrac{19}{34}$.
2. The first 6 terms of a geometric sequence with first term 10 and common ratio $\dfrac{1}{2}$ are $10, 5, \dfrac{5}{2}, \dfrac{5}{4}, \dfrac{5}{8}, \dfrac{5}{16}$.
  Here, the ratio of its 6th term to its 4th term is $\dfrac{5/16}{5/4}$ which equals $\dfrac{1}{4}$. (We could have determined this without writing out the sequence, since moving from the 4th term to the 6th involves multiplying by $\dfrac{1}{2}$ twice.)
  The first 6 terms of an arithmetic sequence with first term 10 and common difference $d$ are $10, 10+d, 10+2d, 10+3d, 10+4d, 10+5d$.
  Here, the ratio of the 6th term to the 4th term is $\dfrac{10+5d}{10+3d}$.
  Since these ratios are equal, then $\dfrac{10+5d}{10+3d} = \dfrac{1}{4}$, which gives $4(10+5d) = 10+3d$ and so $40 + 20d = 10 + 3d$ or $17d = -30$ and so $d = -\dfrac{30}{17}$.
1. Let $a = f(20)$. Then $f(f(20)) = f(a)$.
  To calculate $f(f(20))$, we determine the value of $a$ and then the value of $f(a)$.
  By definition, $a = f(20)$ is the number of prime numbers $p$ that satisfy $20 \leq p \leq 30$.
  The prime numbers between 20 and 30, inclusive, are 23 and 29, so $a = f(20) = 2$.
  Thus, $f(f(20)) = f(a) = f(2)$.
  By definition, $f(2)$ is the number of prime numbers $p$ that satisfy $2 \leq p \leq 12$.
  The prime numbers between 2 and 12, inclusive, are 2, 3, 5, 7, 11, of which there are 5.
  Therefore, $f(f(20)) = 5$.
2. Since $(x-1)(y-2) = 0$, then $x=1$ or $y=2$.
  Suppose that $x=1$. In this case, the remaining equations become: \[\begin{aligned} (1-3)(z+2) & = 0 \\ 1 + yz & = 9\end{aligned}\] or \[\begin{aligned} -2(z+2) & = 0 \\ yz & = 8\end{aligned}\] From the first of these equations, $z = -2$.
  From the second of these equations, $y(-2) = 8$ and so $y = -4$.
  Therefore, if $x=1$, the only solution is $(x,y,z)=(1,-4,-2)$.
  Suppose that $y = 2$. In this case, the remaining equations become: \[\begin{aligned} (x-3)(z+2) & = 0 \\ x + 2z & = 9\end{aligned}\] From the first equation $x=3$ or $z=-2$.
  If $x=3$, then $3 + 2z = 9$ and so $z = 3$.
  If $z=-2$, then $x + 2(-2) = 9$ and so $x = 13$.
  Therefore, if $y=2$, the solutions are $(x,y,z)=(3,2,3)$ and $(x,y,z)=(13,2,-2)$.
  In summary, the solutions to the system of equations are \[(x,y,z) = (1,-4,-2), (3,2,3), (13,2,-2)\] We can check by substitution that each of these triples does indeed satisfy each of the equations.
1. Draw a perpendicular from $S$ to $V$ on $BC$.
  Since $ASVB$ is a quadrilateral with three right angles, then it has four right angles and so is a rectangle.
  Therefore, $BV = AS = r$, since $AS$ is a radius of the top semi-circle, and $SV = AB = 4$.
  Join $S$ and $T$ to $P$. Since the two semi-circles are tangent at $P$, then $SPT$ is a straight line, which means that $ST = SP + PT = r + r = 2r$.
  
  Consider right-angled $\triangle SVT$. We have $SV = 4$ and $ST = 2r$.
  Also, $VT = BC - BV - TC = 6 - r - r = 6 - 2r$.
  By the Pythagorean Theorem, \[\begin{aligned} SV^2 + VT^2 & = ST^2 \\ 4^2 + (6 - 2r)^2 & = (2r)^2 \\ 16 + 36 - 24r + 4r^2 & = 4r^2 \\ 52 & = 24r\end{aligned}\] Thus, $r = \frac{52}{24} = \frac{13}{6}$.
2. Since $\triangle ABE$ is right-angled at $A$ and is isosceles with $AB = AE = 7\sqrt{2}$, then $\triangle ABE$ is a $45^\circ$-$45^\circ$-$90^\circ$ triangle, which means that $\angle ABE = 45^\circ$ and $BE = \sqrt{2} AB = \sqrt{2} \cdot 7\sqrt{2} = 14$.
  Since $\triangle BCD$ is right-angled at $C$ with $\dfrac{DB}{DC} = \dfrac{8x}{4x} = 2$, then $\triangle BCD$ is a $30^\circ$-$60^\circ$-$90^\circ$ triangle, which means that $\angle DBC = 30^\circ$.
  Since $\angle ABC = 135^\circ$, then $\angle EBD = \angle ABC - \angle ABE - \angle DBC = 135^\circ - 45^\circ - 30^\circ = 60^\circ$.
  Now consider $\triangle EBD$. We have $EB = 14$, $BD = 8x$, $DE = 8x - 6$, and $\angle EBD = 60^\circ$.
  Using the cosine law, we obtain the following equivalent equations: \[\begin{aligned} DE^2 & = EB^2 + BD^2 - 2\cdot EB \cdot BD \cdot \cos(\angle EBD) \\ (8x-6)^2 & = 14^2 + (8x)^2 - 2(14)(8x) \cos(60^\circ) \\ 64x^2 - 96x + 36 & = 196 + 64x^2 - 2(14)(8x) \cdot \tfrac{1}{2}\\ -96x & = 160 - 14(8x) \\ 112x - 96x & = 160 \\ 16x & = 160 \\ x & = 10\end{aligned}\] Therefore, the only possible value of $x$ is $x=10$.
1. Solution 1:
  
  Since the function $g$ is linear and has positive slope, then it is one-to-one and so invertible.
  This means that $g^{-1}(g(a))=a$ for every real number $a$ and $g(g^{-1}(b))=b$ for every real number $b$.
  Therefore, $g(f(g^{-1}(g(a)))) = g(f(a))$ for every real number $a$.
  This means that \[\begin{aligned} g(f(a)) & = g(f(g^{-1}(g(a))))\\ & = 2(g(a))^2 + 16g(a) + 26\\ & = 2(2a-4)^2 + 16(2a-4) + 26\\ & = 2(4a^2 - 16a + 16) + 32a - 64 + 26 \\ & = 8a^2 - 6\end{aligned}\] Furthermore, if $b = f(a)$, then $g^{-1}(g(f(a))) = g^{-1}(g(b)) = b = f(a)$.
  Therefore, \[f(a) = g^{-1}(g(f(a))) = g^{-1}(8a^2 - 6)\] Since $g(x) = 2x - 4$, then $y = 2g^{-1}(y) - 4$ and so $g^{-1}(y) = \frac{1}{2}y + 2$.
  Therefore, \[f(a) = \tfrac{1}{2}(8a^2 - 6) + 2 = 4a^2 - 1\] and so $f(\pi) = 4\pi^2 - 1$.
  
  Solution 2:
  
  Since the function $g$ is linear and has positive slope, then it is one-to-one and so invertible.
  To find a formula for $g^{-1}(y)$, we start with the equation $g(x) = 2x-4$, convert to $y = 2g^{-1}(y) - 4$ and then solve for $g^{-1}(y)$ to obtain $2g^{-1}(y) = y+4$ and so $g^{-1}(y) = \dfrac{y+4}{2}$.
  We are given that $g(f(g^{-1}(x))) = 2x^2 + 16x + 26$.
  We can apply the function $g^{-1}$ to both sides to obtain successively: \[\begin{aligned} f(g^{-1}(x)) & = g^{-1}(2x^2 + 16x + 26) \\ f(g^{-1}(x)) & = \dfrac{(2x^2 + 16x + 26)+4}{2} & \text{(knowing a formula for $g^{-1}$)}\\ f(g^{-1}(x)) & = x^2 + 8x + 15 \\ f\left(\dfrac{x+4}{2}\right) & = x^2 + 8x + 15 & \text{(knowing a formula for $g^{-1}$)}\\ f\left(\dfrac{x+4}{2}\right) & = x^2 + 8x + 16 - 1 \\ f\left(\dfrac{x+4}{2}\right) & = (x+4)^2 - 1\end{aligned}\] We want to determine the value of $f(\pi)$.
  Thus, we can replace $\dfrac{x+4}{2}$ with $\pi$, which is equivalent to replacing $x+4$ with $2\pi$.
  Thus, $f(\pi) = (2\pi)^2 - 1 = 4\pi^2 - 1$.
2. Solution 1:
  
  Using logarithm laws, the given equations are equivalent to \[\begin{aligned} \log_2(\sin x) + \log_2(\cos y) & = -\dfrac{3}{2}\\ \log_2(\sin x) - \log_2(\cos y) & = \dfrac{1}{2}\end{aligned}\] Adding these two equations, we obtain $2 \log_2(\sin x) = -1$ which gives $\log_2(\sin x) = -\dfrac{1}{2}$ and so $\sin x = 2^{-1/2} = \dfrac{1}{2^{1/2}} = \dfrac{1}{\sqrt{2}}$.
  Since $0^\circ \leq x < 180^\circ$, then $x = 45^\circ$ or $x = 135^\circ$.
  Since $\log_2(\sin x) + \log_2(\cos y) = -\dfrac{3}{2}$ and $\log_2(\sin x) = -\dfrac{1}{2}$, then $\log_2(\cos y) = -1$, which gives $\cos y = 2^{-1} = \dfrac{1}{2}$.
  Since $0^\circ \leq y < 180^\circ$, then $y = 60^\circ$.
  Therefore, $(x,y) = (45^\circ, 60^\circ)$ or $(x,y) = (135^\circ, 60^\circ)$.
  
  Solution 2:
  
  First, we note that $2^{1/2} = \sqrt{2}$ and $2^{-3/2} = \dfrac{1}{2^{3/2}} = \dfrac{1}{2^1 2^{1/2}} = \dfrac{1}{2\sqrt{2}}$.
  From the given equations, we obtain \[\begin{aligned} \sin x \cos y & = 2^{-3/2} = \dfrac{1}{2\sqrt{2}} \\ \dfrac{\sin x}{\cos y} & = 2^{1/2} = \sqrt{2}\end{aligned}\] Multiplying these two equations together, we obtain $(\sin x)^2 = \dfrac{1}{2}$ which gives $\sin x = \pm \dfrac{1}{\sqrt{2}}$.
  Since $0^\circ \leq x < 180^\circ$, it must be the case that $\sin x \geq 0$ and so $\sin x = \dfrac{1}{\sqrt{2}}$.
  Since $0^\circ \leq x < 180^\circ$, we obtain $x = 45^\circ$ or $x = 135^\circ$.
  Since $\sin x \cos y = \dfrac{1}{2\sqrt{2}}$ and $\sin x = \dfrac{1}{\sqrt{2}}$, we obtain $\cos y = \dfrac{1}{2}$.
  Since $0^\circ \leq y < 180^\circ$, then $y = 60^\circ$.
  Therefore, $(x,y) = (45^\circ, 60^\circ)$ or $(x,y) = (135^\circ, 60^\circ)$.
1. Solution 1:
  
  Let $x$ be the probability that Bianca wins the tournament.
  Because Alain, Bianca and Chen are equally matched and because their roles in the tournament are identical, then the probability that each of them wins will be the same.
  Thus, the probability that Alain wins the tournament is $x$ and the probability that Chen wins the tournament is $x$.
  Let $y$ be the probability that Dave wins the tournament.
  Since exactly one of Alain, Bianca, Chen, and Dave wins the tournament, then $3x + y = 1$ and so $x = \dfrac{1-y}{3}$. We can calculate $y$ in terms of $p$.
  In order for Dave to win the tournament, he needs to win two matches.
  No matter who Dave plays, his probability of winning each match is $p$.
  Thus, the probability that he wins his two consecutive matches is $p^2$ and so the probability that he wins the tournament is $y = p^2$.
  Thus, the probability that Bianca wins the tournament is $\dfrac{1-p^2}{3}$.
  (We could rewrite this as $\dfrac{-p^2 + 0p + 1}{3}$ to match the desired form.)
  
  Solution 2:
  
  Let $x$ be the probability that Bianca wins the tournament.
  There are three possible pairings for the first two matches:
  1. Bianca versus Alain, and Chen versus Dave
  2. Bianca versus Chen, and Alain versus Dave
  3. Bianca versus Dave, and Alain versus Chen
  Each of these three pairings occurs with probability $\frac{1}{3}$.
  In (i), Bianca wins either if Bianca beats Alain, Chen beats Dave, and Bianca beats Chen, or if Bianca beats Alain, Dave beats Chen, and Bianca beats Dave.
  Since Bianca beats Alain with probability $\frac{1}{2}$, Chen beats Dave with probability $1-p$, and Bianca beats Chen with probability $\frac{1}{2}$, then the first possibility has probability $\frac{1}{2} \cdot (1-p) \cdot \frac{1}{2}$.
  Since Bianca beats Alain with probability $\frac{1}{2}$, Dave beats Chen with probability $p$, and Bianca beats Dave with probability $1-p$, then the second possibility has probability $\frac{1}{2} \cdot p \cdot (1-p)$.
  Therefore, the probability of Bianca winning, given that possibility (i) occurs, is $\frac{1}{2} \cdot (1-p) \cdot \frac{1}{2} + \frac{1}{2} \cdot p \cdot (1-p)$.
  In (ii), Bianca wins either if Bianca beats Chen, Alain beats Dave, and Bianca beats Alain, or if Bianca beats Alain, Dave beats Alain, and Bianca beats Dave.
  The combined probability of these is $\frac{1}{2} \cdot (1-p) \cdot \frac{1}{2} + \frac{1}{2} \cdot p \cdot (1-p)$.
  In (iii), Bianca wins either if Bianca beats Dave, Alain beats Chen, and Bianca beats Alain, or if Bianca beats Dave, Chen beats Alain, and Bianca beats Chen.
  The combined probability of these is $(1-p) \cdot \frac{1}{2} \cdot \frac{1}{2} + (1-p) \cdot \frac{1}{2} \cdot \frac{1}{2}$.
  Therefore, \[\begin{aligned} x & = \tfrac{1}{3}\left(\tfrac{1}{4}(1-p) + \tfrac{1}{2}p(1-p) + \tfrac{1}{4}(1-p) + \tfrac{1}{2}p(1-p) + \tfrac{1}{4}(1-p) + \tfrac{1}{4}(1-p)\right)\\ & = \tfrac{1}{3}(p(1-p) + (1-p)) \\ & = \tfrac{1}{3}(p - p^2 + 1 - p)\end{aligned}\] Thus, the probability that Bianca wins the tournament is $\dfrac{1-p^2}{3}$.
2. Throughout this solution, we will mostly not include units, but will assume that all lengths are in kilometres, all times are in seconds, and all speeds are in kilometres per second.
  We place the points in the coordinate plane with $B$ at $(0,0)$, $A$ on the negative $x$-axis, and $C$ on the positive $x$-axis.
  We put $A$ at $(-1,0)$ and $C$ at $(2,0)$.
  Suppose that $P$ has coordinates $(x,y)$ and that the distance from $P$ to $B$ is $d$ km.
  
  Since the sound arrives at $A$ $\frac{1}{2}$ s after arriving at $B$ and sound travels at $\frac{1}{3}$ km/s, then $A$ is $(\frac{1}{2}\mbox{ s}) \cdot (\frac{1}{3}\mbox{ km/s}) = \frac{1}{6}\mbox{ km}$ farther from $P$ than $B$ is.
  Thus, the distance from $P$ to $A$ is $(d + \frac{1}{6})\mbox{ km}$.
  Since the sound arrives at $C$ an additional 1 second later, then $C$ is an additional $\frac{1}{3}\mbox{ km}$ farther, and so is $(d + \frac{1}{6})\mbox{ km} + (\frac{1}{3}\mbox{ km}) = (d + \frac{1}{2})\mbox{ km}$ from $P$.
  Since the distance from $P$ to $B$ is $d$ km, then $(x-0)^2 + (y-0)^2 = d^2$.
  Since the distance from $P$ to $A$ is $(d+\frac{1}{6})\mbox{ km}$, then $(x+1)^2 + (y-0)^2 = (d+\frac{1}{6})^2$.
  Since the distance from $P$ to $C$ is $(d+\frac{1}{2})\mbox{ km}$, then $(x-2)^2 + (y-0)^2 = (d+\frac{1}{2})^2$.
  When these equations are expanded and simplified, we obtain \[\begin{aligned} x^2 + y^2 & = d^2 \\[2mm] x^2 + 2x + 1 + y^2 & = d^2 + \tfrac{1}{3}d + \tfrac{1}{36} \\[2mm] x^2 - 4x + 4 + y^2 & = d^2 + d + \tfrac{1}{4} \end{aligned}\] Subtracting the first equation from the second, we obtain \[2x + 1 = \tfrac{1}{3}d + \tfrac{1}{36}\] Subtracting the first equation from the third, we obtain \[-4x + 4 = d + \tfrac{1}{4}\] Therefore, \[\begin{aligned} 2(2x+1) + (-4x+4) & = 2(\tfrac{1}{3}d + \tfrac{1}{36}) + (d + \tfrac{1}{4}) \\ 6 & = \tfrac{2}{3}d + \tfrac{1}{18} + d + \tfrac{1}{4} \\ 216 & = 24d + 2 + 36d + 9 & \text{(multiplying by $36$)}\\ 205 & = 60d \\ d & = \tfrac{41}{12}\end{aligned}\] Therefore, the distance from $B$ to $P$ is $\frac{41}{12}$ km.
1. After each round, each L shape is divided into 4 smaller L shapes.
  This means that the number of L shapes increases by a factor of 4 after each round.
  After 1 round, there are 4 L shapes.
  After 2 rounds, there are $4^2 = 16$ L’s of the smallest size.
  After 3 rounds, there are $4^3 = 64$ L’s of the smallest size.
2. There are four orientations of L shapes of a given size: , , , .
  
  When an L of each orientation is subdivided, the following figures are obtained:
  
  From these figures, we can see that after each subsequent round,
  - Each produces 2 , 0 , 1 , and 1 of the smallest size.
  - Each produces 0 , 2 , 1 , and 1 .
  - Each produces 1 , 1 , 2 , and 0 .
  - Each produces 1 , 1 , 0 , and 2 .
  After 1 round, there are 2 , 0 , 1 , and 1 .
  After 2 rounds, the number of L’s of each orientation are as follows:
  - : $2 \cdot 2 + 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 1 = 6$
  - : $2 \cdot 0 + 0 \cdot 2 + 1 \cdot 1 + 1 \cdot 1 = 2$
  - : $2 \cdot 1 + 0 \cdot 1 + 1 \cdot 2 + 1 \cdot 0 = 4$
  - : $2 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 + 1 \cdot 2 = 4$
  After 3 rounds, the number of L’s of each orientation are as follows:
  - : $6 \cdot 2 + 2 \cdot 0 + 4 \cdot 1 + 4 \cdot 1 = 20$
  - : $6 \cdot 0 + 2 \cdot 2 + 4 \cdot 1 + 4 \cdot 1 = 12$
  - : $6 \cdot 1 + 2 \cdot 1 + 4 \cdot 2 + 4 \cdot 0 = 16$
  - : $6 \cdot 1 + 2 \cdot 1 + 4 \cdot 0 + 4 \cdot 2 = 16$
  Where do these numbers come from?
  For example, to determine the number of after 2 rounds, we look at the number of L’s of each orientation after round 1 (2, 0, 1, 1) and ask how many each of these produces at the next level. Since the four types each produce 2, 0, 1, and 1 , then the total number of after 2 rounds equals $2 \cdot 2 + 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 1$ which equals 6.
  As a second example, to determine the number of after 3 rounds, we note that after 2 rounds the number of L’s of the four different orientations are 6, 2, 4, 4 and that each L of each of the four types produces 0, 2, 1, 1 . This means that the total number of after 3 rounds is $6 \cdot 0 + 2 \cdot 2 + 4 \cdot 1 + 4 \cdot 1 = 12$.
  Putting all of this together, the number of L’s of the smallest size in the same orientation as the original L is 20.
3. In (b), we determined the number of L’s of the smallest size in each orientation after 1, 2 and 3 rounds.
  We continue to determine the number of L’s of the smallest size after 4 rounds.
  After 4 rounds, the number of L’s of each orientation are as follows:
  - : $20 \cdot 2 + 12 \cdot 0 + 16 \cdot 1 + 16 \cdot 1 = 72$
  - : $20 \cdot 0 + 12 \cdot 2 + 16 \cdot 1 + 16 \cdot 1 = 56$
  - : $20 \cdot 1 + 12 \cdot 1 + 16 \cdot 2 + 16 \cdot 0 = 64$
  - : $20 \cdot 1 + 12 \cdot 1 + 16 \cdot 0 + 16 \cdot 2 = 64$
  This gives us the following tables of the numbers of L’s of the smallest size in each orientation after 1, 2, 3, and 4 rounds:
  
  After Round
  
  1 2 0 1 1
  
  2 6 2 4 4
  
  3 20 12 16 16
  
  4 72 56 64 64
  
  We re-write these numbers in the third row as $16 + 4, 16 - 4, 16, 16$ and the numbers in the fourth row as $64 + 8, 64 - 8, 64, 64$.
  Based on this, we might guess that the numbers of L’s of the smallest size in each orientation after $n$ rounds are $4^{n-1}+2^{n-1}$, $4^{n-1}-2^{n-1}$, $4^{n-1}$, $4^{n-1}$.
  If this guess is correct, then, after 2020 rounds, the number of L’s of the smallest size in the same orientation as the original L is $4^{2019} + 2^{2019}$.
  We prove that these guesses are right by using an inductive process.
  First, we note that the table above shows that our guess is correct when $n=1, 2, 3, 4$.
  Next, if we can show that our guess being correct after a given number of rounds implies that it is correct after the next round, then it will be correct after every round. This is because being correct after 4 rounds will mean that it is correct after 5 rounds, being correct after 5 rounds will mean that it is correct after 6 rounds, and so on to be correct after any number of rounds.
  Suppose, then, that after $k$ rounds the numbers of L’s of the smallest size in each orientation are $4^{k-1}+2^{k-1}$, $4^{k-1}-2^{k-1}$, $4^{k-1}$, $4^{k-1}$.
  After $k+1$ rounds (that is, after the next round), the number of L’s of each orientation is:
  - : $(4^{k-1}+2^{k-1}) \cdot 2 + (4^{k-1}-2^{k-1}) \cdot 0 + 4^{k-1} \cdot 1 + 4^{k-1} \cdot 1 = 4\cdot 4^{k-1} + 2\cdot 2^{k-1} = 4^k + 2^k$
  - : $(4^{k-1}+2^{k-1}) \cdot 0 + (4^{k-1}-2^{k-1}) \cdot 2 + 4^{k-1} \cdot 1 + 4^{k-1} \cdot 1 = 4\cdot 4^{k-1} - 2\cdot 2^{k-1} = 4^k - 2^k$
  - : $(4^{k-1}+2^{k-1}) \cdot 1 + (4^{k-1}-2^{k-1}) \cdot 1 + 4^{k-1} \cdot 2 + 4^{k-1} \cdot 0 = 4 \cdot 4^{k-1} = 4^k$
  - : $(4^{k-1}+2^{k-1}) \cdot 1 + (4^{k-1}-2^{k-1}) \cdot 1 + 4^{k-1} \cdot 0 + 4^{k-1} \cdot 2 = 4 \cdot 4^{k-1} = 4^k$
  Since $k = (k+1) - 1$, these expressions match our guess. This means that our guess is correct after every number of rounds.
  Therefore, after 2020 rounds, the number of L’s of the smallest size in the same orientation as the original L is $4^{2019} + 2^{2019}$.
1. Here, the pairwise sums of the numbers $a_1 \leq a_2 \leq a_3 \leq a_4$ are $s_1 \leq s_2 \leq s_3 \leq s_4 \leq s_5 \leq s_6$.
  The six pairwise sums of the numbers in the list can be expressed as \[a_1 + a_2, a_1+a_3, a_1+a_4, a_2+a_3, a_2+a_4, a_3+a_4\] Since $a_1 \leq a_2 \leq a_3 \leq a_4$, then the smallest sum must be the sum of the two smallest numbers. Thus, $s_1 = a_1 + a_2$.
  Similarly, the largest sum must be the sum of the two largest numbers, and so $s_6 = a_3 + a_4$.
  Since $a_1 \leq a_2 \leq a_3 \leq a_4$, then the second smallest sum is $a_1 + a_3$. This is because $a_1 + a_3$ is no greater than each of the four sums $a_1+a_4$, $a_2+a_3$, $a_2+a_4$, and $a_3+a_4$:
  
  Since $a_3 \leq a_4$, then $a_1 + a_3 \leq a_1 + a_4$.
  Since $a_1 \leq a_2$, then $a_1 + a_3 \leq a_2 + a_3$.
  Since $a_1 \leq a_2$ and $a_3 \leq a_4$, then $a_1 + a_3 \leq a_2 + a_4$.
  Since $a_1 \leq a_4$, then $a_1 + a_3 \leq a_3 + a_4$.
  
  Thus, $s_2 = a_1 + a_3$.
  Using a similar argument, $s_5 = a_2 + a_4$.
  So far, we have $s_1 = a_1 + a_2$ and $s_2 = a_1 + a_3$ and $s_5 = a_2 + a_4$ and $s_6 = a_3 + a_4$.
  This means that $s_3$ and $s_4$ equal $a_1 + a_4$ and $a_2 + a_3$ in some order.
  It turns out that either order is possible.
  Case 1: $s_3 = a_1 + a_4$ and $s_4 = a_2 + a_3$
  Here, $a_1 + a_2 = 8$ and $a_1 + a_3 = 104$ and $a_2 + a_3 = 110$.
  Adding these three equations gives \[(a_1 + a_2) + (a_1 + a_3) + (a_2 + a_3) = 8 + 104 + 110\] and so $2a_1+2a_2+2a_3 = 222$ or $a_1+a_2+a_3 = 111$.
  Since $a_2 + a_3 = 110$, then $a_1 = (a_1+a_2+a_3) - (a_2+a_3) = 111 - 110 = 1$.
  Since $a_1=1$ and $a_1 + a_2 = 8$, then $a_2 = 7$.
  Since $a_1=1$ and $a_1 + a_3 = 104$, then $a_3 = 103$.
  Since $a_3=103$ and $a_3 + a_4 = 208$, then $a_4 = 105$.
  Thus, $(a_1,a_2,a_3,a_4) = (1,7,103,105)$.
  Case 2: $s_3 = a_2 + a_3$ and $s_4 = a_1 + a_4$
  Here, $a_1 + a_2 = 8$ and $a_1 + a_3 = 104$ and $a_2 + a_3 = 106$.
  Using the same process, $a_1+a_2+a_3=109$.
  From this, we obtain $(a_1,a_2,a_3,a_4)=(3,5,101,107)$.
  Therefore, Kerry’s two possible lists are $1, 7, 103, 105$ and $3, 5, 101, 107$.
2. Suppose that the values of $s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8,s_9,s_{10}$ are fixed, but unknown.
  In terms of the numbers $a_1 \leq a_2 \leq a_3 \leq a_4 \leq a_5$, the ten pairwise sums are \[a_1+a_2, a_1+a_3, a_1+a_4, a_1+a_5, a_2+a_3, a_2+a_4, a_2+a_5, a_3+a_4, a_3+a_5, a_4+a_5\] These will equal $s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8,s_9,s_{10}$ in some order.
  Using a similar analysis to that in (a), the smallest sum is $a_1+a_2$ and the largest sum is $a_4+a_5$. Thus, $s_1 = a_1+a_2$ and $s_{10} = s_4+s_5$.
  Also, the second smallest sum will be $s_2 = a_1 + a_3$ and the second largest sum will be $s_9 = a_3 + a_5$.
  We let \[S = s_1+s_2+s_3+s_4+s_5+s_6+s_7+s_8+s_9+s_{10}\] Note that $S$ has a fixed, but unknown, value.
  Even though we do not know the order in which these pairwise sums are assigned to $s_1$ through $s_{10}$, the value of $S$ will equal the sum of these ten pairwise expressions.
  In other words, $S = 4a_1+4a_2+4a_3+4a_4+4a_5$, since each of the numbers in the list occurs in four sums.
  Thus, $a_1 + a_2 + a_3 + a_4 + a_5 = \frac{1}{4}S$ and so $(a_1 + a_2) + a_3 + (a_4 + a_5) = \frac{1}{4}S$.
  This means that $s_1 + a_3 + s_{10} = \frac{1}{4}S$ and so $a_3 = \frac{1}{4}S - s_1 - s_{10}$.
  Since the values of $s_1$, $s_{10}$ and $S$ are fixed, then we are able to determine the value of $a_3$ from the list of sums $s_1$ through $s_{10}$.
  Using the value of $a_3$, the facts that $s_2 = a_1 + a_3$ and $s_9 = a_3 + a_5$, and that $s_2$ and $s_9$ are known, we can determine $a_1$ and $a_5$.
  Finally, using $s_1 = a_1 + a_2$ and $s_{10} = a_4 + a_5$ and the values of $a_1$ and $a_5$, we can determine $a_2$ and $a_4$.
  Therefore, given the ten sums $s_1$ through $s_{10}$, we can determine the values of $a_3$, $a_1$, $a_5$, $a_2$, $a_4$ and so there is only one possibility for the list $a_1,a_2,a_3,a_4,a_5$. (Can you write out expressions for each of $a_1$ through $a_5$ in terms of $s_1$ through $s_{10}$ only?)
3. Suppose that the lists $a_1$, $a_2$, $a_3$, $a_4$ and $b_1$, $b_2$, $b_3$, $b_4$ produce the same list of sums $s_1$, $s_2$, $s_3$, $s_4$, $s_5$, $s_6$. (Examples of such lists can be found in (a).)
  Let $x$ be a positive integer. Consider the following list with 8 entries: \[a_1,a_2,a_3,a_4, b_1+x,b_2+x,b_3+x,b_4+x\] From this list, there are three categories of pairwise sums:
  1. $a_i + a_j$, $1 \leq i < j \leq 4$: these give the sums $s_1$ through $s_6$
  2. $(b_i + x)+(b_j+x)$, $1 \leq i < j \leq 4$: each of these is $2x$ greater than the six sums $s_1$ through $s_6$ because the pairwise sums $b_i + b_j$ give the six sums $s_1$ through $s_6$
  3. $a_i + (b_j + x)$, $1 \leq i \leq 4$ and $1 \leq j \leq 4$
  Consider also the list with 8 entries: \[a_1+x,a_2+x,a_3+x,a_4+x, b_1,b_2,b_3,b_4\] From this list, there are again three categories of pairwise sums:
  1. $b_i + b_j$, $1 \leq i < j \leq 4$: these give the sums $s_1$ through $s_6$
  2. $(a_i + x)+(a_j+x)$, $1 \leq i < j \leq 4$: each of these is $2x$ greater than the six sums $s_1$ through $s_6$ because the pairwise sums $a_i + a_j$ give the six sums $s_1$ through $s_6$
  3. $(a_i + x) + b_j$, $1 \leq i \leq 4$ and $1 \leq j \leq 4$
  Thus, the 28 pairwise sums in each case are the same. In each case, there are 6 sums in (i), 6 sums in (ii), and 16 sums in (iii).
  If we choose the initial lists to have the same pairwise sums and choose the value of $x$ to be large enough so that $a_i + x$ is not equal to any $b_j$ and $b_i+x$ is not equal to any $a_j$, we obtain two different lists of 8 numbers that each produce the same list of 28 sums.
  For example, if we choose $a_1,a_2,a_3,a_4$ to be $1,7,103,105$ and $b_1,b_2,b_3,b_4$ to be $3,5,101,107$ and $x=10\,000$, we get the lists \[1,7,103,105,10\,003, 10\,005, 10\,101, 10\,107\] and \[3,5,101,107,10\,001, 10\,007, 10\,103, 10\,105\] Using a similar analysis to that above, if the lists $a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$, $a_7$, $a_8$ and $b_1$, $b_2$, $b_3$, $b_4$, $b_5$, $b_6$, $b_7$, $b_8$ have the same set of pairwise sums, then the lists \[a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,b_1+y,b_2+y,b_3+y,b_4+y,b_5+y,b_6+y,b_7+y,b_8+y\] and \[a_1+y,a_2+y,a_3+y,a_4+y,a_5+y,a_6+y,a_7+y,a_8+y,b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8\] will also have the same pairwise sums.
  Therefore, setting $y=1\,000\,000$, we see that the lists \[1,7,103,105,10\,003, 10\,005, 10\,101, 10\,107, 1\,000\,003,1\,000\,005,1\,000\,101,1\,000\,107,\] \[1\,010\,001, 1\,010\,007, 1\,010\,103, 1\,010\,105\] and \[3,5,101,107,10\,001, 10\,007, 10\,103, 10\,105, 1\,000\,001,1\,000\,007,1\,000\,103,1\,000\,105,\] \[1\,010\,003, 1\,010\,005, 1\,010\,101, 1\,010\,107\] have the same list of sums $s_1,s_2,\ldots,s_{120}$, as required.

	\(\boldsymbol{x}\)	\(\boldsymbol{y}\)
Before Step 1	24	3
After Step 1	27	3
After Step 2	81	3
After Step 3	81	4

After Round
1	2	0	1	1
2	6	2	4	4
3	20	12	16	16
4	72	56	64	64

2020 Euclid Contest Solutions

2020 Euclid Contest
Solutions