Problem 10 of the 2011 Euclid Math Contest (remix)

April 14, 2011

I wrote the Euclid contest this year two days ago, on tuesday. There were 10 problems, and the tenth problem was a nice geometry problem. Three subproblems with a nice neat triangle on the right, with the subproblems getting progressively harder and harder. As I proceeded with the problem, I couldn’t help but imagine it as a Project Euler problem — instead of finding one such integer triangle, it would ask you to find the sum of the perimeters of all such integer triangles with perimeter less than 10^12 or some large number.

A modified problem

In the above diagram, \angle CAK = 2 \angle KAB and \angle ABC = 2 \angle KAB. Let a = CB, b = AC, c = AB, d = AK, and x = KB. Write an algorithm to find triangles satisfying these conditions where a, b, c are all integers.

Similar triangles

It is difficult to try to find integer triangles with such strange requirements as these. It seems that the line AK is completely unnecessary, but if we take it out, there doesn’t seem to be any way to relate the angle ratios to integer side lengths.

We can prove that \triangle CAK is similar to \triangle ABC. Being an exterior angle, CKA = 3 \theta, and also \angle CAB = 3 \theta. Both of the triangles have an angle of measure 2 \theta and another angle of measure 3 \theta, thus they are similar.

From the similar triangles ratio

\frac{b}{d} = \frac{a}{c}

We can write d in terms of the three sides of the triangle:

d = \frac{bc}{a}

Similarly, the side CK can be written as a-x. Then we have the ratio

\frac{a}{b} = \frac{b}{a-x}

Solving for x allows us to express it in terms of the three sides of the triangle, again:

x = \frac{a^2 - b^2}{a}

Constructing another similar triangle

Our goal here is to relate the lengths a, b, c with a simple equation, which then the problem turns into a number theory problem. Since we can write the lengths d and x in terms of a, b, and c, we can also relate any of a, b, c, d, x in an equation.

Again, there doesn’t seem to be a way to relate all of the variables together, in a way that any solution implies the original angle ratio required — unless we make a construction.

Here we extend AB to F, so that KB = BF and \triangle KBF is an isosceles triangle.

Again, since the exterior angle here is 2 \theta, both \angle BKF = \angle BFK = \theta. Also with this construction, \triangle AKF \sim \triangle KBF, and is also isosceles, hence d = AK = KF.

With this construction, we can write the ratio

\frac{x}{d} = \frac{d}{c+x}

Perfect! Cross multiplying and then substituting in the original sides of the triangles gives

(\frac{a^2-b^2}{a})(c+\frac{a^2-b^2}{a}) = (\frac{bc}{a})^2

Simplifying this gives

(a^2 - b^2) (a^2 - b^2 + ac) = b^2 c^2

Number theory magic

Now that we have an equation relating the three side lengths — it’s easy to verify that any three integers satisfying the triangle inequality gives a triangle with the required conditions — we can use number theory to try to generate integers that fit the equation.

If we expand the equation, we get

a^4+a^3 c-2 a^2 b^2-a b^2 c+b^4-b^2 c^2 = 0

It makes sense to solve for c, which can be done using just the quadratic formula:

c = \frac{a^3 - ab^2 \pm \sqrt{(ab^2-a^3)^2 + 4b^2(b^4 + a^4 - 2a^2 b^2)}}{2b^2}

We need the discriminant D — the expression inside the square root — to be a perfect square, where we are allowed to have integer values for a and b. If we can get D to be a perfect square, then c will turn out to be a rational number. Then multiplying all three variables by a constant gives integer values for all three.

So we defined D:

D = (ab^2-a^3)^2 + 4b^2(b^4 + a^4 - 2a^2 b^2)

Expanding this gives

D = a^6 - 7a^2 b^4 + 2 a^4 b^2 + 4b^6

Fortunately, this expression has an interesting factorization:

D = (a^2+4b^2) (a+b)^2 (a-b)^2

Or we can also write

\sqrt{D} = (a+b) (a-b) \sqrt{a^2 + 4b^2}

We’ve simplified this problem to finding values where a^2 + 4b^2 is a perfect square, that is:

a^2 + (2b)^2 = k^2

This is just finding Pythagorean triples where one of the two sides are even! For instance, in the triple (3,4,5), we have a=3 and b=2. However, substituting a=3, b=2 into the quadratic formula gives c=5. This is almost a solution, only that the sides have to satisfy the triangle inequality (two sides have to add up to more than the third side).

The next Pythagorean triple (5,12,13) gives a=5 and b=6. Substituting this in gives c=11/9, which does satisfy the triangle inequality. Multiplying everything by 9 gives a=45, b=54, c=11 as the smallest working combination.

With this method, it is possible to quickly find arbitrarily many such triples, using Pythagorean triples as a starting point (which can be generated quickly with known methods).


2010 Euclid Contest

April 13, 2010

Today quite a few people from my school took the Euclid contest, again from the University of Waterloo.

This contest is really meant for grade 12 students, and it’s probably the most important of the contests, as it can be used to apply for universities and scholarships.

While most people took the contest last wednesday (April 7), my school took it on April 12.

Surprisingly I haven’t found anybody uploading the full solutions, or even all the questions of the euclid. Having took the contest, I’ll do so now. On to the first question!

Question 1

1. a) 3^x = 27, find 3^{x+2}.

Solving for x, we get x=3. So x+2 = 5, and 3^5 = 243.

b) 2^5 \cdot 3^{13} \cdot 5^9 x = 2^7 \cdot 3^{14} \cdot 5^9, find x

Solve for x:

\begin{array}{rcl} x &=& \frac{2^7 \cdot 3^{14} \cdot 5^9}{2^5 \cdot 3^{13} \cdot 5^9} \\ &=& 2^2 \cdot 3 \\ &=& 12 \end{array}

The value for x is 12.

c)

Hosted by imgur.com

The equation of line AB is y=x+2, and the equation of BC is -\frac{1}{2}x+2. Determine the area of \triangle ABC.

Because A and C are on the x axis and B is on the y axis, it’s fairly simple to figure out the coordinates of all three points. They are:

\begin{array}{l} A = (-2,0) \\ B=(0,2) \\ C=(4,0) \end{array}

We have a base and a height, so the area can be calculated to be 6.

Question 2

2. a) Maria has a red, blue, and green package.

The sum of the masses of all three packages, is 60kg, of the red and green packages is 25kg, and of the green and blue packages is 50kg.

What is the mass of the green package?

Using R, G, and B for the masses of the red, green, and blue packages respectively, we can put together this system of equations:

\begin{array}{rrrrrcl} R&+&G&+&B&=&60 \\ R&+&G&&&=&25 \\ &&G&+&B&=&50 \end{array}

Solve this by elimination and you should get (R,G,B) = (10,15,35). So the weight of the green package is 15 kg.

b) A palindrome is a positive integer reading the same forwards and backwards (151, for example). What is the largest palindrome less than 200 that can be written as the sum of three consecutive integers?

Any number that can be written as a sum of three consecutive integers must be divisible by 3, because if n is an integer then the sum is n + (n+1) + (n+2) or 3n + 3.

Palindromes less than 200 are 191, 181, 171, etc. The first one in the sequence that’s divisible by 3 is 171.

c) If (x+1) (x-1) = 8, determine the value of (x^2+x) (x^2-x).

Solving the first quadratic for x:

\begin{array}{l} (x+1)(x-1)=8 \\ x^2-1=8 \\ x^2-9=0 \\ (x+3)(x-3) = 0 \\ x = \pm3 \end{array}

Substituting either of the two roots into the second expression gives the value as 72.

Question 3

Hosted by imgur.com
3. a) Bea (a bee) starts from H (the hive), flies south for 1 hour to F (field), spends 30 minutes at F, flies 45 minutes to G (garden), spends 1 hour at G, then flies back to H. She flies at a constant speed in a straight line. What is the total time (in minutes) that she’s away from her hive?

All the times are given, except for the hypotenuse HG, which can easily be calculated using the pythagorean theorem:

Hosted by imgur.com

The sum of the amount of times spent in each segment is 270 minutes.

Hosted by imgur.com

b) \triangle OPB is right angled. Determine all possible values of p.

Since \triangle OPB is right angled, P is on a circle with OB as diameter (Thales’ theorem). We can let M be the center of the circle at (5,0):

Hosted by imgur.com

The y coordinate of P is 4, so the equation is y=4, intersecting with the circle at two points given by this system of equations:

\begin{array}{l} y=4 \\ (x-5)^2 + y^2 = 25 \end{array}

Substituting and solving the quadratic:

\begin{array}{rcl} (x-5)^2 + 16 = 25 \\ (x-5)^2 = 9 \\ x-5 = \pm 3 \\ x = 5 \pm 3 \end{array}

So the possible values of x, or p, are 2 and 8.

Question 4

4. a) Toy goats cost $19 each and toy helicopters $17 each. Thurka spent $201 on integral amounts of goats and helicopters. How many of each did she buy?

Because 201 \equiv 14 \; (\textrm{mod} \; 17) and 19 \equiv 2 \; (\textrm{mod} \; 17), 201 – 7*19 is divisible by 17. Thus the only solution is 7 goats and 4 helicopters.

b) Determine all values of x where (x+8)^4 = (2x+16)^2

Rewrite the equation as (x+8)^4 = 4(x+8)^2 and let t=(x+8)^2:

\begin{array}{l} t^2 = 4t \\ t^2 - 4t = 0 \\ t (t-4) = 0 \\ t=0, t=4 \end{array}

Substituting the values of t and solving for x:

\begin{array}{l} (x+8)^2 = 0 \rightarrow x = -8 \\ (x+8)^2 = 4 \rightarrow x+8 = \pm 2 \rightarrow x = -8 \pm 2 \end{array}

So the possible values for x are -10, -8, and -6.

Question 5

5. a) If f(x) = 2x+1 and g(f(x)) = 4x^2+1, determine an expression for g(x).

g(x) must be a quadratic function in the form ax^2 + bx + c. We know f(x), so we can express g(f(x)) as such:

\begin{array}{rcl} g(f(x)) &=& g(2x+1) \\ &=& a(2x+1)^2 + b(2x+1) + c \\ &=& (4a)x^2 + (4a+2b)x + (a+b+c) \end{array}

In g(f(x)), a=4, b=0, and c=1. Thus we can solve this system of equations:

\begin{array}{l} 4a=4 \\ 4a+2b=0 \\ a+b+c=1 \end{array}

The solution is (a,b,c) = (1,-2,2), so g(x) = x^2-2x+2.

b) A geometric sequence has 20 terms. The sum of the first two terms is 40, of the first three is 76, and of the first four is 130. Determine how many terms are integers.

Because the difference between the sum of the first three and the sum of the first two is known, the forth term is 54 by subtraction.

Similarly, the third term is 36. We can calculate the ratio between terms to be \frac{54}{36} = \frac{3}{2}.

Then the second term can be interpolated by multiplying the third term by \frac{2}{3}, and it is 24. The first term is 16. So the sequence goes like this:

16, 24, 36, 54, 81, \cdots

Notice that in each term the number of 2-factors decreases by 1. For example the first term, 16, is divisible by 2^4, and the second term is divisible by 2^3, and so on.

So 81 is divisible by 2^0, and the next term and all following terms are not integers. The sequence contains 5 terms.

Question 6

Hosted by imgur.com

6. a) AB is 1cm, find AH.

The ratio of AB to AC is \cos 30 or \frac{\sqrt{3}}{2}. Or AC = \frac{2}{\sqrt{3}} \cdot AB.

The ratio of AD to AC is the same, and so is the ratio of AE to AD, all because of similar triangles.

AH is just the ratio applied six times. It’s (\frac{2}{\sqrt{3}})^6 or 64/27.

Hosted by imgur.com
b) AF=4 and DF=2. Determine the area of BCEF.

All the triangles: \triangle AFB, \triangle AFD, and \triangle DFE are similar because they are all right triangles, all having a right angle plus another angle shared.

The ratio of the longer side to the shorter side is 4:2 or 2:1, so BF=8 and FE=1. The area of AFB is 16, the area of AFD is 4, and the area of DFE is 1:

Hosted by imgur.com

The area of ABD is 20, which is equal to BCD. Since DFE=1, BCEF must be 19.

Question 7

7. a) Determine all solutions for this equation:

3^{x-1} \cdot 9^{\frac{3}{2x^2}} = 27

Using some logarithms, it’s not too difficult to solve:

\begin{array}{rcl} 3^{x-1} \cdot 3^{2 \cdot \frac{3}{2x^2}} &=& 3^3 \\ (x-1) + \frac{3}{x^2} &=& 3 \\ x + 4 + \frac{3}{x^2}&=& 0 \\ x^3 - 4x^2 + 3 &=& 0 \\(x-1) (x^2-3x-3) &=& 0 \end{array}

Using the quadratic formula we can get the solutions for the second factor. The solutions for x are 1 and 3±√21/2.

b) Determine all solutions (x,y) for these equations:

\begin{array}{rcl} y &=& \log_{10} (x^4) \\ y &=& (\log_{10} x)^3 \end{array}

This first equation can be written like this:

y = 4 \log_{10} x

Substitute g for \log{10}x and combine the two equations:

\begin{array}{rcl} 4g &=& g^3 \\ g^3 - 4g &=& 0 \\ g (g+2) (g-2) &=& 0 \end{array}

The solutions for g are 0, -2, and 2. Because x=10^g, replace the g values with their respective x values to get 100, 1, and \frac{1}{100}.

Now calculate the y values by substituting back the x values, and the solutions are (1,0), (100,8), and (1/100, -8).

Question 8

8. a) Oi-Lam tosses 3 coins, and removes those that come up heads (if any). He then tosses the remaining coins (if any). Determine the probability he tosses exactly one head (on the second toss).

Using the pascal triangle, there is a \frac{1}{8} chance of having no coins to toss on the second round, \frac{3}{8} chance of one coin, \frac{3}{8} chance of having two coins, and \frac{1}{8} chance of having no coins.

Hosted by imgur.com

For each case the probability of coming up with exactly one head is given by the first diagonal:
Hosted by imgur.com

Namely the probability of having exactly one head when tossing 3 coins is 3 divided by the sum of the row, giving \frac{3}{8}.

So adding it up, we have this expression:

\begin{array}{l} \frac{1}{8} \cdot (1 \cdot 0 + 3 \cdot \frac{1}{2} + 3 \cdot \frac{1}{2} + 1 \cdot \frac{3}{8}) \\ = \frac{27}{64} \end{array}

The total probability is 27/64.

This fraction is the same as the answer to 6a, reversed. Coincidence?

Hosted by imgur.com

b) Here P is the center of the larger circle with AC as diameter; Q is the center of the smaller circle with BD as diameter. \angle PRQ is 40. Determine \angle ARD.

It’s best to solve this problem by first drawing a few additional lines:

Hosted by imgur.com

We also give the variables a, b, c, and d to several of the angles as shown above.

Because of isosceles triangles, \angle RAP = \angle ARP = a+b. Similarly, \angle RBQ = \angle BRQ = b+40. The two must be equal so a+b = b+40.

From that, a=20. With the exact same logic, d=20. AC is a diameter so ARC is a right angle. We know d so ARD = 110°.

Question 9

9. a) i) Prove that:

\cot \theta - \cot 2\theta = \frac{1}{\sin 2\theta}

If you know the trigonometric identities, this question shouldn’t be too difficult:

\begin{array}{l} \cot \theta - \cot 2 \theta \\ = \frac{\cos \theta}{\sin \theta} - \frac{\cos 2 \theta}{\sin 2 \theta} \\ = \frac{\cos \theta}{\sin \theta} - \frac{\cos^2 \theta - \sin^2 \theta}{2 \sin \theta \cos \theta} \\ = \frac{2 \cos^2 \theta - \cos^2 \theta + \sin^2 \theta}{2 \sin \theta \cos \theta} \\ = \frac{1}{2 \sin \theta \cos \theta} \\ = \frac{1}{\sin 2 \theta} \end{array}

ii) S is given by this formula:

S = \frac{1}{\sin 8^\circ} + \frac{1}{\sin 16^\circ} + \cdots + \frac{1}{\sin 4096^\circ} + \frac{1}{\sin 8192^\circ}

Determine, without a calculator, the value of \alpha:

S = \frac{1}{\sin \alpha}

It’s important to know to use the formula given in part (i) to solve this problem. Other than that, it’s not too hard:

\begin{array}{l}\frac{1}{\sin 8} + \frac{1}{\sin 16} + \cdots +  \frac{1}{\sin 4096} + \frac{1}{\sin 8192} \\ = \cot 4 - \cot 8 + \cot 8 - \cdots + \cot 4096 - \cot 8192 \\ = \cot 4 - \cot 8192 \\ = \cot 4 - \cot 92 \\ = \frac{\cos 4}{ \sin 4} - \frac{\cos 92}{\sin 92} \\ = \frac{\cos 4}{\sin 4} + \frac{\sin 2}{\cos 2} \\ = \frac{\cos 4 \cos 2 + \sin 4 \sin 2}{\sin 4 \cos 2} \\ = \frac{\cos (4-2)}{\sin 4 \cos 2} \\ = \frac{1}{\sin 4} \end{array}

So the value of \alpha is .

b) In \triangle ABC, a < \frac{1}{2} (b+c) (where a would be the side opposite of angle A). Prove that \angle A < \frac{1}{2} (\angle B + \angle C).

The Sine law states the following:

\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C} = k

From this we can multiply to find the relationship between sides, their angles, and an unknown constant k:

\begin{array}{l} a = k \sin A \\ b = k \sin B \\ c = k \sin C \end{array}

We now substitute and simplify:

\begin{array}{rcl} k \sin A &<& \frac{1}{2} (k \sin B + k \sin C) \\ \sin A &<& \frac{1}{2} (\sin B + \sin C) \\ \sin A &<& \frac{1}{2} (2 \sin \frac{B+C}{2} \cos \frac{B-C}{2}) \\ \sin A &<& \sin \frac{B+C}{2} \cos \frac{B-C}{2}\end{array}

It’s obvious that \cos \frac{B-C}{2} \leq 1. So if we divide both sides of the equation by \cos \frac{B-C}{2}, the right hand side is what we desire, and the left hand side is smaller. Thus,

\begin{array}{rcl} \sin A &<& \sin \frac{B+C}{2} \\ A &<& \frac{1}{2} (B+C) \end{array}

This is what we set out to prove.

Question 10

10. Let T(n) be the number of triangles with integer sides and perimeter n (where n is a positive integer). For example T(6) = 1 because only (2,2,2) has a perimeter of 6 and nothing else.

a) Determine T(10), T(11), and T(12).

Triangles with perimeter 10 are (2,4,4) and (3,3,4). So T(10) is 2. Triangles with perimeter 11 are (1,5,5), (2,4,5), (3,3,5), and (3,4,4). So T(11) is 4. Triangles with perimeter 12 are (2,5,5), (3,4,5), and (4,4,4). So T(12) is 3.

The answers are 2, 4, and 3 respectively.

b) If m is a positive integer and m \geq 3, prove that T(2m) = T(2m-3).

Let a, b, and c be the sides of the triangle so that a \leq b \leq c. Let U be the triangle with perimeter 2m, and V be the triangle with perimeter 2m-3.

In order for the triangle to be non-degenerate, a+b > c. Because otherwise the ‘triangle’ would be a line, or something (I’m going to refer to it as a degenerate triangle).

For every triangle V, there must be at least one triangle U. If we represent the sides of V by (a,b,c), we can add one to each side giving (a+1,b+1,c+1). This triangle can’t be degenerate.

So T(2m) \geq T(2m-3).

Now we want to prove that the converse is true: for any triangle U with side lengths (a,b,c), a triangle V with side lengths (a-1,b-1,c-1) is also non-degenerate.

The only case where this might not be true is when c is exactly one more than a+b, in which case the resulting triangle would be degenerate. In this case, a+b = c+1. But this cannot be true.

The perimeter of U has to be even, so a+b+c is even. But in the equation, if a+b is even then c is odd, and if a+b is odd then c is even. Therefore it’s impossible for a+b+c to be even and at the same time for the equation a+b = c+1 to be true. Thus (a-1,b-1,c-1) is never degenerate.

For every triangle U, there must be at least one triangle V, so T(2m-3) \geq T(2m).

But we’ve already proved that T(2m) \geq T(2m-3). Combined with the other inequality, T(2m) = T(2m-3) which is what we need.

c) Determine the smallest n where T(n) > 2010.

The formula for T(n) is fairly well known. It’s given by:

\begin{array}{rcll} T(n) &=& round(\frac{n^2}{48}) & \textrm{when n is even} \\ && round(\frac{(n+3)^2}{48}) & \textrm{when n is odd} \end{array}

Let’s use the even one just because. Solving the inequality \frac{n^2}{48} > 2010, we get n > 310.6.

Since the equation is only relevant for even integers, the first even integer greater than 310.6 is 312. But since we proved that T(n) = T(n-3) for even integers n, T(309) = T(312).

There is no smaller n meeting the requirements, so n is 309.

This solution uses an external formula and would probably not be considered correct. I don’t know how to do it without this formula.

Notes

Because I took the contest several days later than everyone else, I had a considerable and unfair advantage because some of the questions were available already. So I was able to research the questions and figure out how to solve them before writing it.

Nevertheless I wasn’t able to solve all of the questions before the contest. But perhaps this unfair advantage balances my lack of experience (this contest is for grade 12 students).

This blog post itself may be useful to anyone taking the euclid after today. Notice that ‘today’ in this blog post is inconsistent because I wrote this blog post over the course of two days.

\frac{\cost \theta}{\sin \theta} – \frac{\cos^2 \theta – \sin^2 \theta}{2 \sin \theta \cos \theta}

Follow

Get every new post delivered to your Inbox.

Join 72 other followers