The CENTRE for EDUCATION

in MATHEMATICS and COMPUTING

cemc.uwaterloo.ca

2019 Euclid Contest

Wednesday, April 3, 2019

(in North America and South America)

Thursday, April 4, 2019

(outside of North America and South America)

Solutions

©2019 University of Waterloo

2019 Euclid Contest Solutions Page 3

1. (a) Solution 1
Since 34 of a jar has a volume of 300 mL, then 1
4
of a jar has a volume of (300 mL) ÷ 3 or
100 mL.

Solution 2
Since 34 of a jar has a volume of 300 mL, then the volume of the entire jar is 34 (300 mL)
or 400 mL.
In this case, the volume of 14 of the jar is (400 mL) ÷ 4 = 100 mL.
24
(b) We note that since > 3 > 0, then a is positive.
a
24 24
Since 3 < and a > 0, then a < = 8.
a 3
24 24
Since < 4 and a > 0, then a > = 6.
a 4
Since 6 < a < 8 and a is an integer, then a = 7.
24
Note that it is indeed true that 3 < < 4.
7
(c) Since x and x2 appear in the denominators of the equation, then x 6= 0.
Multiplying by x2 and manipulating, we obtain successively
1 1
2
− =2
x x
1 − x = 2x2
0 = 2x2 + x − 1
0 = (2x − 1)(x + 1)
1
and so x = or x = −1.
2
Checking in the original equation we obtain,
1 1 1 1
2
− = − =4−2=2
(1/2) 1/2 1/4 1/2
and
1 1 1
2
− = +1=2
(−1) −1 1
1
and so the solutions to the equation are x = and x = −1.
2

2. (a) Since the radius of the large circle is 2, its area is π · 22 = 4π.
Since the radius of each small circle is 1, the area of each small circle is π · 12 = π.
Since the two small circles are tangent to each other and to the large circle, then their
areas do not overlap and are contained entirely within the large circle.
Since the shaded region consists of the part of the large circle that is outside the two small
circles, then the shaded area is 4π − π − π = 2π.
(b) Mo starts at 10:00 a.m. and finishes at 11:00 a.m. and so runs for 1 hour.
Mo runs at 6 km/h, and so runs 6 km in 1 hour.
Thus, Kari also runs 6 km.
6 km 3
Since Kari runs at 8 km/h, then Kari runs for = h which is 45 minutes.
8 km/h 4
Since Kari finishes at 11:00 a.m., then Kari started at 10:15 a.m.
2019 Euclid Contest Solutions Page 4

(c) The equation x + 3y = 7 can be rearranged to 3y = −x + 7 and y = − 31 x + 37 .

Therefore, the line with this equation has slope − 31 .
Since the two lines are parallel and the line with equation y = mx + b has slope m, then
m = − 31 .
Thus, the equation of the second line can be re-written as y = − 31 x + b.
Since (9, 2) lies on this line, then 2 = − 31 · 9 + b and so 2 = −3 + b, which gives b = 5.

3. (a) Michelle’s list consists of 8 numbers and so its average is

5 + 10 + 15 + 16 + 24 + 28 + 33 + 37 168
= = 21
8 8
Daphne’s list thus consists of 7 numbers (one fewer than in Michelle’s list) with an average
of 20 (1 less than that of Michelle).
The sum of 7 numbers whose average is 20 is 7 · 20 = 140.
Since the sum of Michelle’s numbers was 168, then Daphne removed the number equal to
168 − 140 which is 28.
(b) Since 16 = 24 and 32 = 25 , then the given equation is equivalent to the following equations

(24 )15/x = (25 )4/3

260/x = 220/3

60 20 60
This means that = = and so x = 9.
x 3 9
(c) Using exponent laws, the following equations are equivalent:

22022 + 2a
= 72
22019
2022−2019
2 + 2a−2019 = 72
23 + 2a−2019 = 72
8 + 2a−2019 = 72
2a−2019 = 64
2a−2019 = 26

which means that a − 2019 = 6 and so a = 2025.

4. (a) Solution 1
Since 4CDB is right-angled at B, then ∠DCB = 90◦ − ∠CDB = 30◦ .
This means that 4CDB is a 30◦ -60◦ -90◦ triangle.
Using the ratios of side lengths in a 30◦ -60◦ -90◦ triangle, CD : DB = 2 : 1.
Since DB = 10, then CD = 20.
Since ∠CDB = 60◦ , then ∠ADC = 180◦ − ∠CDB = 120◦ .
Since the angles in 4ADC add to 180◦ , then ∠DAC = 180◦ − ∠ADC − ∠ACD = 30◦ .
This means that 4ADC is isosceles with AD = CD.
Therefore, AD = CD = 20.
2019 Euclid Contest Solutions Page 5

Solution 2
Since 4CDB is right-angled at B, then ∠DCB = 90◦ − ∠CDB = 30◦ .
Since 4ACB is right-angled at B, then ∠CAB = 90◦ − ∠ACB = 90◦ − (30◦ + 30◦ ) = 30◦ .
This means that each of 4CDB and 4ACB is a 30◦ -60◦ -90◦ triangle.√
Using the ratios of side lengths√in a 30◦ -60◦ -90◦ triangle, CB : DB = 3 : 1.
Since DB = 10, then CB √ = 10 3.
Similarly, AB :√CB = 3 : 1. √ √
Since CB = 10 3, then AB = 3 · 10 3 = 30.
Finally, this means that AD = AB − DB = 30 − 10 = 20.
(b) Since the points A(d, −d) and B(−d + 12, 2d − 6) lie on the same circle centered at the
origin, O, then OA = OB.
Since distances are always non-negative, the following equations are equivalent:
p p
(d − 0)2 + (−d − 0)2 = ((−d + 12) − 0)2 + ((2d − 6) − 0)2
d2 + (−d)2 = (−d + 12)2 + (2d − 6)2
d2 + d2 = d2 − 24d + 144 + 4d2 − 24d + 36
2d2 = 5d2 − 48d + 180
0 = 3d2 − 48d + 180
0 = d2 − 16d + 60
0 = (d − 10)(d − 6)

and so d = 10 or d = 6. √
We can check that the points A(10, −10) and B(2, 14) are both of√distance 200 from the
origin and the points A(6, −6) and B(6, 6) are both of distance 72 from the origin.

√ √
5. (a) First, we note that √50 = √ 5 2. √ √ √ √
Next, we note that 2 + 4 2 = 5 √2 and √ 2 2 +
√ 3 2 = 5 2.
From the first of these, we obtain 2√+ 32 √ = 50. √
From the second of these, we obtain 8 + 18 = 50.
Thus, (a, b) = (2, 32) and (a, b) = (8, 18) are solutions to the original equation.
(We are not asked to justify why these are the only two solutions.)
(b) From the second equation, we note that d 6= 0.
Rearranging this second equation, we obtain c = kd.
Substituting into the first equation, we obtain kd + d = 2000 or (k + 1)d = 2000.
Since k ≥ 0, note that k + 1 ≥ 1.
This means that if (c, d) is a solution, then k + 1 is a divisor of 2000.
Also, if k + 1 is a divisor of 2000, then the equation (k + 1)d = 2000 gives us an integer
value of d (which is non-zero) from which we can find an integer value of c using the first
equation.
Therefore, the values of k that we want to count correspond to the positive divisors of
2000.
Since 2000 = 10 · 10 · 20 = 24 · 53 , then 2000 has (4 + 1)(3 + 1) = 20 positive divisors.
This comes from the fact that if p and q are distinct prime numbers then the positive
integer pa · q b has (a + 1)(b + 1) positive divisors.
We could list these divisors as

1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 125, 200, 250, 400, 500, 1000, 2000
2019 Euclid Contest Solutions Page 6

if we did not know the earlier formula.

Since 2000 has 20 positive divisors, then there are 20 values of k for which the system of
equations has at least one integer solution.
c
For example, if k + 1 = 8, then k = 7. This gives the system c + d = 2000 and = 7
d
which has solution (c, d) = (1750, 250).

6. (a) Solution 1
The angles in a polygon with n sides have a sum of (n − 2) · 180◦ .
This means that the angles in a pentagon have a sum of 3 · 180◦ or 540◦ , which means that
1
each interior angle in a regular pentagon equals · 540◦ or 108◦ .
5
n−2
Also, each interior angle in a regular polygon with n sides equals · 180◦ . (This is
n
the general version of the statement in the previous sentence.)
Consider the portion of the regular polygon with n sides that lies outside the pentagon and
join the points from which the angles that measure a◦ and b◦ emanate to form a hexagon.

a°
c°

b°

This polygon has 6 sides, and so the sum of its 6 angles is 4 · 180◦ .
Four of its angles are the original angles from the n-sided polygon, so each equals
n−2
· 180◦ .
n
The remaining two angles have measures a◦ + c◦ and b◦ + d◦ .
We are told that a◦ + b◦ = 88◦ .
Also, the angles that measure c◦ and d◦ are two angles in a triangle whose third angle is
108◦ .
Thus, c◦ + d◦ = 180◦ − 108◦ = 72◦ .
Therefore,
n−2
4· · 180◦ + 88◦ + 72◦ = 4 · 180◦
n  
◦ 4(n − 2)
160 = 4 − · 180◦
n
4n − (4n − 8)
160◦ = · 180◦
n
160◦ 8
=
180◦ n
8 8
=
9 n
and so the value of n is 9.
2019 Euclid Contest Solutions Page 7

Solution 2
The angles in a polygon with n sides have a sum of (n − 2) · 180◦ .
This means that the angles in a pentagon have a sum of 3 · 180◦ or 540◦ , which means that
1
each interior angle in a regular pentagon equals · 540◦ or 108◦ .
5
n−2
Also, each interior angle in a regular polygon with n sides equals · 180◦ . (This is
n
the general version of the statement in the previous sentence.)
Consider the portion of the regular polygon with n sides that lies outside the pentagon.

a°

b°

This polygon has 7 sides, and so the sum of its 7 angles is 5 · 180◦ .
Four of its angles are the original angles from the n-sided polygon, so each equals
n−2
· 180◦ .
n
Two of its angles are the angles equal to a◦ and b◦ , whose sum is 88◦ .
Its seventh angle is the reflex angle corresponding to the pentagon’s angle of 108◦ , which
equals 360◦ − 108◦ or 252◦ .
Therefore,
n−2
4· · 180◦ + 88◦ + 252◦ = 5 · 180◦
n  
◦ 4(n − 2)
340 = 5 − · 180◦
n
5n − (4n − 8)
340◦ = · 180◦
n
340◦ n+8
=
180◦ n
17 n+8
=
9 n
17n = 9(n + 8)
17n = 9n + 72
8n = 72

and so the value of n is 9.

2019 Euclid Contest Solutions Page 8

(b) Since the lengths of AD, AB and BC form a geometric sequence, we suppose that these
lengths are a, ar and ar2 , respectively, for some real numbers a > 0 and r > 0.
Since the angles at A and B are both right angles, we assign coordinates to the diagram,
putting B at the origin (0, 0), C on the positive x-axis at (ar2 , 0), A on the positive y-axis
at (0, ar), and D at (a, ar).
y

A (0, ar) D (a, ar)

x
B (0, 0) C (ar 2, 0)
ar − 0
Therefore, the slope of the line segment joining B(0, 0) and D(a, ar) is = r.
a−0
ar − 0 1
Also, the slope of the line segment joining A(0, ar) and C(ar2 , 0) is 2
=− .
0 − ar r
Since the product of the slopes of these two line segments is −1, then the segments are
perpendicular, as required.

7. (a) Using logarithm and exponent laws, we obtain the following equivalent equations:

2 log2 (x − 1) = 1 − log2 (x + 2)
2 log2 (x − 1) + log2 (x + 2) = 1
log2 (x − 1)2 + log2 (x + 2) = 1

log2 (x − 1)2 (x + 2) = 1

(x − 1)2 (x + 2) = 21
(x2 − 2x + 1)(x + 2) = 2
x3 − 3x + 2 = 2
x3 − 3x = 0
x(x2 − 3) = 0

√ √
and so x = 0 or x = 3 or x = − 3.
Note that if x = 0,√then x − 1 = −1 <√0 and so log2 (x − 1) is not defined. Thus, x 6= 0.
√ if x = − 3, then x − 1 = − 3 − 1 < 0 and so log2 (x − 1) is not defined. Thus,
Note that
x 6= − √3.
If x = 3, we can verify that both logarithms in the original equation are defined and
that the original equation is true. We could convince ourselves of this with a calculator
or we could algebraically verify that raising 2 to the power of both sides gives the same
number, so the √expressions must actually be equal.
Therefore, x = 3 is the only solution.
2019 Euclid Contest Solutions Page 9

(b) Let a = f (f (x)).

Thus, the equation f (f (f (x))) = 3 is equivalent to f (a) = 3.
Since f (a) = a2 − 2a, then we obtain the equation a2 − 2a = 3 which gives a2 − 2a − 3 = 0
and (a − 3)(a + 1) = 0.
Thus, a = 3 or a = −1 which means that f (f (x)) = 3 or f (f (x)) = −1.
Let b = f (x).
Thus, the equations f (f (x)) = 3 and f (f (x)) = −1 become f (b) = 3 and f (b) = −1.
If f (b) = 3, then b = f (x) = 3 or b = f (x) = −1 using similar reasoning to above when
f (a) = 3.
If f (b) = −1, then b2 − 2b = −1 and so b2 − 2b + 1 = 0 or (b − 1)2 = 0 which means that
b = f (x) = 1.
Thus, f (x) = 3 or f (x) = −1 or f (x) = 1.
If f (x) = 3, then x = 3 or x = −1 as above.
If f (x) = −1, then x = 1 as above.
If f (x) = 1, then x2 − 2x = 1 and so x2 − 2x − 1 = 0.
By the quadratic formula,
√
√
p
−(−2) ± (−2)2 − 4(1)(−1) 2± 8
x= = =1± 2
2(1) 2
√ √
Therefore, the solutions to the equation f (f (f (x))) = 3 are x = 3, 1, −1, 1 + 2, 1 − 2.

8. (a) Since ∠AOB = ∠BOC = ∠COD = ∠DOA and these angles form a complete circle
around O, then ∠AOB = ∠BOC = ∠COD = ∠DOA = 14 · 360◦ = 90◦ .
Join point O to P , B, Q, C, S, D, T , and A.
P B Q
A

C
T
D S

Since P , Q, S, and T are points of tangency, then the radii meet the sides of ABCD at
right angles at these points.
◦
Since AO
√ = 3 and OT √ = 1 √and ∠OT A = 90 , then by the Pythagorean Theorem,
AT = AO2 − OT 2 = 8 = 2 2.
Since 4OT A is right-angled at T , then ∠T AO + ∠AOT = 90◦ .
Since ∠DOA = 90◦ , then ∠AOT + ∠DOT = 90◦ .
Thus, ∠T AO = ∠DOT .
This means that 4AT O is similar to 4OT D.
DT OT OT 2 1
Thus, = and so DT = = √ .
OT AT AT 2 2
1
Since DS and DT are tangents to the circle from the same point, then DS = DT = √ .
2 2
2019 Euclid Contest Solutions Page 10
π
(b) Since 0 < x < , then 0 < cos x < 1 and 0 < sin x < 1.
2
3 3 3 3 3 π
This means that 0 < cos x < and 0 < sin x < . Since 3 < π, then 0 < cos x <
2 2 2 2 2 2
3 π
and 0 < sin x < .
2 2
π π
If Y and Z are angles with 0 < Y < and 0 < Z < , then cos Y = sin Z exactly when
2 2
π
Y + Z = . To see this, we could picture points R and S on the unit circle corresponding
2
to the angles Y and Z; the x-coordinate of R is equal to the y-coordinate of S exactly
when the angles Y and Z are complementary.
Therefore, the following equations are equivalent:
   
3 3
cos cos x = sin sin x
2 2
3 3 π
cos x + sin x =
2 2 2
π
cos x + sin x =
3
2
π
(sin x + cos x)2 =
9
π2
sin2 x + 2 sin x cos x + cos2 x =
9
2
π
2 sin x cos x + (sin2 x + cos2 x) =
9
π2
sin 2x + 1 =
9
π2 − 9
sin 2x =
9
π2 − 9
Therefore, the only possible value of sin 2x is .
9
2019 Euclid Contest Solutions Page 11
2 5 1 2·2+5·5+1 4 + 25 + 1 30
9. (a) By definition, f (2, 5) = + + = = = = 3.
5 2 2·5 2·5 10 10
a a 1 1
(b) By definition, f (a, a) = + + 2 = 2 + 2 .
a a a a
1 1
For 2 + 2 to be an integer, it must be the case that 2 is an integer.
a a
1 2 2
For 2 to be an integer and since a is an integer, a needs to be a divisor of 1.
a
Since a2 is positive, then a2 = 1.
Since a is a positive integer, then a = 1.
Thus, the only positive integer a for which f (a, a) is an integer is a = 1.
(c) Suppose that a and b are positive integers for which f (a, b) is an integer.
Assume that k = f (a, b) is not a multiple of 3.
We will show that there must be a contradiction, which will lead to the conclusion that k
must be a multiple of 3.
a b 1
By definition, k = f (a, b) = + + .
b a ab
Multiplying by ab, we obtain kab = a2 +b2 +1, which we re-write as a2 −(kb)a+(b2 +1) = 0.
We treat this as a quadratic equation in a with coefficients in terms of the variables b and k.
Solving for a in terms of b and k using the quadratic formula, we obtain
p √
kb ± (−kb)2 − 4(1)(b2 + 1) kb ± k 2 b2 − 4b2 − 4
a= =
2 2
Since a is an integer, then the discriminant k 2 b2 − 4b2 − 4 must be a perfect square.
Re-writing the discriminant, we obtain

k 2 b2 − 4b2 − 4 = b2 (k 2 − 4) − 4 = b2 (k − 2)(k + 2) − 4

Since k is not a multiple of 3, then it is either 1 more than a multiple of 3 or it is 2 more

than a multiple of 3.
If k is 1 more than a multiple of 3, then k + 2 is a multiple of 3.
If k is 2 more than a multiple of 3, then k − 2 is a multiple of 3.
In either case, (k − 2)(k + 2) is a multiple of 3, say (k − 2)(k + 2) = 3m for some integer m.
This means that the discriminant can be re-written again as

b2 (3m) − 4 = 3(b2 m − 2) + 2

In other words, the discriminant is itself 2 more than a multiple of 3.

However, every perfect square is either a multiple of 3 or one more than a multiple of 3:
Suppose that r is an integer and consider r2 .
The integer r can be written as one of 3q, 3q + 1, 3q + 2, for some integer q.
These three cases give

(3q)2 = 9q 2 = 3(3q 2 )
(3q + 1)2 = 9q 2 + 6q + 1 = 3(3q 2 + 2q) + 1
(3q + 2)2 = 9q 2 + 12q + 4 = 3(3q 2 + 4q + 1) + 1

and so r2 is either a multiple of 3 or 1 more than a multiple of 3.

2019 Euclid Contest Solutions Page 12

We have determined that the discriminant is a perfect square and is 2 more than a multiple
of 3. This is a contradiction.
This means that our initial assumption must be incorrect, and so k = f (a, b) must be a
multiple of 3.
(d) Solution 1
We find additional pairs of positive integers (a, b) with f (a, b) = 3.
Suppose that f (a, b) = 3.
a b 1
This is equivalent to the equations + + = 3 and a2 + b2 − 3ab + 1 = 0.
b a ab
Then
b 3b − a 1
f (b, 3b − a) − 3 = + + −3
3b − a b b(3b − a)
b2 + (3b − a)2 + 1 − 3b(3b − a)
=
b(3b − a)
2
b + (3b − a)(3b − a) + 1 − 3b(3b − a)
=
b(3b − a)
2
b − a(3b − a) + 1
=
b(3b − a)
b + a2 − 3ab + 1
2
=
b(3b − a)
=0

Therefore, if f (a, b) = 3, then f (b, 3b − a) = 3.

The equation f (1, 2) = 3 gives f (2, 3(2) − 1) = f (2, 5) = 3.
The equation f (2, 5) = 3 gives f (5, 3(5) − 2) = f (5, 13) = 3.
The equation f (5, 13) = 3 gives f (13, 3(13) − 5) = f (13, 34) = 3.
The equation f (13, 34) = 3 gives f (34, 3(34) − 13) = f (34, 89) = 3.
The equation f (34, 89) = 3 gives f (89, 3(89) − 34) = f (89, 233) = 3.
Thus, the pairs (a, b) = (5, 13), (13, 34), (34, 89), (89, 233) satisfy the requirements.

Solution 2
From (a), we know that f (2, 5) = 3.
Since the function f (a, b) is symmetric in a and b (that is, a and b can be switched without
changing the value of the function), then f (5, 2) = 3.
Consider the equation f (5, b) = 3. We know that b = 2 is a solution, but is there another
solution?
5 b 1
By definition, f (5, b) = + + .
b 5 5b
Thus, f (5, b) = 3 gives the following equivalent equations:
5 b 1
+ + =3
b 5 5b
25 + b2 + 1 = 15b
b2 − 15b + 26 = 0
(b − 2)(b − 13) = 0

and so b = 2 or b = 13. This means that f (5, 13) = 3 and so (a, b) = (5, 13) has the
property that f (a, b) is an integer.
2019 Euclid Contest Solutions Page 13

From f (5, 13) = 3, we get f (13, 5) = 3.

As above, we consider the equation f (13, b) = 3, for which b = 5 is a solution.
We obtain the equivalent equations
13 b 1
+ + =3
b 13 13b
169 + b2 + 1 = 39b
b2 − 39b + 170 = 0
(b − 5)(b − 34) = 0
and so b = 5 or b = 34. This means that f (13, 34) = 3 and so (a, b) = (13, 34) has the
property that f (a, b) is an integer.
Continuing in a similar manner, we can also find that f (34, 89) and f (89, 233) are both
integers.
Thus, the pairs (a, b) = (5, 13), (13, 34), (34, 89), (89, 233) satisfy the requirements.

Solution 3
Note that
5 13 1 52 + 132 + 1 195
f (5, 13) = + + = = =3
13 5 5 · 13 65 65
13 34 1 132 + 342 + 1 1326
f (13, 34) = + + = = =3
34 13 13 · 34 442 442
34 89 1 342 + 892 + 1 9078
f (34, 89) = + + = = =3
89 34 34 · 89 3026 3026
89 233 1 892 + 2332 + 1 62 211
f (89, 233) = + + = = =3
233 89 89 · 233 20737 20 737
and so the pairs (a, b) = (5, 13), (13, 34), (34, 89), (89, 233) satisfy the requirements.
Where do these pairs come from?
We define the Fibonacci sequence F1 , F2 , F3 , F4 , . . . by F1 = F2 = 1 and Fn = Fn−1 + Fn−2
when n ≥ 3.
Thus, the Fibonacci sequence begins 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . ..
The pairs (a, b) found above are of the form (F2k−1 , F2k+1 ) for integers k ≥ 3.
We note that
F2k−1 F2k+1 1
f (F2k−1 , F2k+1 ) = + +
F2k+1 F2k−1 F2k−1 F2k+1
(F2k−1 )2 + (F2k+1 )2 + 1
=
F2k−1 F2k+1
(F2k−1 )2 + (F2k + F2k−1 )2 + 1
=
F2k−1 (F2k + F2k−1 )
2(F2k−1 )2 + 2F2k F2k−1 + (F2k )2 + 1
=
(F2k−1 )2 + F2k F2k−1
2(F2k−1 )2 + 2F2k F2k−1 (F2k )2 + 1
= +
(F2k−1 )2 + F2k F2k−1 (F2k−1 )2 + F2k F2k−1
2
(F2k ) + 1
=2+
F2k−1 F2k+1
2019 Euclid Contest Solutions Page 14

(F2k )2 + 1
This means that f (F2k−1 , F2k+1 ) = 3 if and only if = 1, or equivalently if and
F2k−1 F2k+1
only if (F2k )2 + 1 = F2k−1 F2k+1 , or (F2k )2 − F2k−1 F2k+1 = −1.
We note that (F2 )2 − F1 F3 = 12 − 1 · 2 = −1 and (F4 )2 − F3 F5 = 32 − 2 · 5 = −1 so this is
true when k = 1 and k = 2.
Furthermore, we note that

(F2k+2 )2 − F2k+1 F2k+3 = (F2k+2 )2 − F2k+1 (F2k+2 + F2k+1 )

= (F2k+2 )2 − F2k+1 F2k+2 − (F2k+1 )2
= F2k+2 (F2k+2 − F2k+1 ) − (F2k+1 )2
= F2k+2 F2k − (F2k+1 )2
= (F2k+1 + F2k )F2k − (F2k+1 )2
= (F2k )2 + F2k+1 F2k − (F2k+1 )2
= (F2k )2 + F2k+1 (F2k − F2k+1 )
= (F2k )2 + F2k+1 (−F2k−1 )
= (F2k )2 − F2k+1 F2k−1

which means that since (F4 )2 − F3 F5 = −1, then (F6 )2 − F5 F7 = −1, which means that
(F8 )2 − F7 F9 = −1, and so on.
Continuing in this way, (F2k )2 − F2k−1 F2k+1 = −1 for all positive integers k ≥ 1, which in
turn means that f (F2k−1 , F2k+1 ) = 3, as required.
2019 Euclid Contest Solutions Page 15

10. (a) On her first two turns, Brigitte either chooses two cards of the same colour or two cards
of different colours. If she chooses two cards of different colours, then on her third turn,
she must choose a card that matches one of the cards that she already has.
Therefore, the game ends on or before Brigitte’s third turn.
Thus, if Amir wins, he wins on his second turn or on his third turn. (He cannot win on
his first turn.)
For Amir to win on his second turn, the second card he chooses must match the first card
that he chooses.
On this second turn, there will be 5 cards in his hand, of which 1 matches the colour of
the first card that he chose.
Therefore, the probability that Amir wins on his second turn is 15 .
Note that there is no restriction on the first card that he chooses or the first card that
Brigitte chooses.
For Amir to win on his third turn, the following conditions must be true: (i) the colour
of the second card that he chooses is different from the colour of the first card that he
chooses, (ii) the colour of the second card that Brigitte chooses is different from the colour
of the first card that she chooses, and (iii) the colour of the third card that Amir chooses
matches the colour of one of the first two cards.
The probability of (i) is 54 , since he must choose any card other than the one that matches
the first one.
The probability of (ii) is 32 , since Brigitte must choose either of the cards that does not
match her first card.
The probability of (iii) is 42 , since Amir can choose either of the 2 cards that matches one
of the first two cards that he chose.
Again, the cards that Amir and Brigitte choose on their first turns do not matter.
Thus, the probability that Amir wins on his third turn is 45 · 23 · 24 which equals 15
4
.
1 4 7
Finally, the probabilty that Amir wins the game is thus 5
+ 15
which equals 15
.
2019 Euclid Contest Solutions Page 16

(b) Suppose that, after flipping the first 13 coins, the probability that there is an even number
of heads is p.
Then the probability that there is an odd number of heads is 1 − p.
When the 14th coin is flipped, the probability of heads is h14 and the probability of not
heads is 1 − h14 .
After the 14th coin is flipped, there can be an even number of heads if the first 13 include
an even number of heads and the 14th is not heads, or if the first 13 include an odd number
of heads and the 14th is heads.
The probability of this is p(1 − h14 ) + (1 − p)h14 .
Therefore,

p(1 − h14 ) + (1 − p)h14 = 12

2p − 2ph14 + 2h14 − 2ph14 = 1
0 = 4ph14 − 2p − 2h14 + 1
0 = 2p(2h14 − 1) − (2h14 − 1)
0 = (2p − 1)(2h14 − 1)

Therefore, either h14 = 12 or p = 21 .

If h14 = 12 , we have proven the result.
If h14 6= 21 , then p = 12 .
This would mean that the probability of getting an even number of heads when the first
13 coins are flipped is 12 .
We could repeat the argument above to conclude that either h13 = 12 or the probability of
obtaining an even number of heads when the first 12 coins are flipped is 12 .
Continuing in this way, either one of h14 , h13 , . . . , h3 , h2 will equal 21 , or the probability of
obtaining an even number of heads when 1 coin is flipped is 12 .
This last statement is equivalent to saying that the probability of obtaining a head with
the first coin is 12 (that is, h1 = 12 ).
Therefore, at least one of h1 , h2 , . . . , h13 , h14 must equal 12 .
2019 Euclid Contest Solutions Page 17

(c) For the sum of the two digits printed to be 2, each digit must equal 1.
Thus, S(2) = p1 q1 .
For the sum of the two digits printed to be 12, each digit must equal 6.
Thus, S(12) = p6 q6 .
For the sum of the two digits printed to be 7, the digits must be 1 and 6, or 2 and 5, or 3
and 4, or 4 and 3, or 5 and 2, or 6 and 1.
Thus, S(7) = p1 q6 + p2 q5 + p3 q4 + p4 q3 + p5 q2 + p6 q1 .
Since S(2) = S(12), then p1 q1 = p6 q6 .
Since S(2) > 0 and S(12) > 0, then p1 , q1 , p6 , q6 > 0.
If p1 = p6 , then we can divide both sides of p1 q1 = p6 q6 by p1 = p6 to obtain q1 = q6 .
If q1 = q6 , then we can divide both sides of p1 q1 = p6 q6 by q1 = q6 to obtain p1 = p6 .
Therefore, if we can show that either p1 = p6 or q1 = q6 , our result will be true.
Suppose that p1 6= p6 and q1 6= q6 .
Since S(2) = 12 S(7) and S(12) = 12 S(7), then

S(7) − 12 S(7) − 12 S(7) = 0

S(7) − S(2) − S(12) = 0
p1 q6 + p2 q5 + p3 q4 + p4 q3 + p5 q 2 + p6 q 1 − p1 q1 − p6 q6 = 0
p1 q6 + p6 q1 − p1 q1 − p6 q6 + (p2 q5 + p3 q4 + p4 q3 + p5 q2 ) = 0
(p1 − p6 )(q6 − q1 ) + (p2 q5 + p3 q4 + p4 q3 + p5 q2 ) = 0
p2 q5 + p3 q4 + p4 q3 + p5 q2 = −(p1 − p6 )(q6 − q1 )
p2 q5 + p3 q4 + p4 q3 + p5 q2 = (p1 − p6 )(q1 − q6 )

Since p2 , p3 , p4 , p5 , q2 , q3 , q4 , q5 ≥ 0, then p2 q5 + p3 q4 + p4 q3 + p5 q2 ≥ 0.
From this, (p1 − p6 )(q1 − q6 ) ≥ 0.
Since p1 6= p6 , then either p1 > p6 or p1 < p6 .
If p1 > p6 , then p1 − p6 > 0 and so (p1 − p6 )(q1 − q6 ) ≥ 0 tells us that q1 − q6 > 0 which
means q1 > q6 .
But we know that p1 q1 = p6 q6 and p1 , q1 , p6 , q6 > 0 so we cannot have p1 > p6 and q1 > q6 .
If p1 < p6 , then p1 − p6 < 0 and so (p1 − p6 )(q1 − q6 ) ≥ 0 tells us that q1 − q6 < 0 which
means q1 < q6 .
But we know that p1 q1 = p6 q6 and p1 , q1 , p6 , q6 > 0 so we cannot have p1 < p6 and q1 < q6 .
This is a contradiction.
Therefore, since we cannot have p1 > p6 or p1 < p6 , it must be the case that p1 = p6 which
means that q1 = q6 , as required.