Project Euler 299: Three similar triangles

Being the last Project Euler problem before the summer break, Problem 299 is quite an interesting problem. Solving it involves both geometry and number theory.

Points A, B, C, D are represented on a coordinate plane as (a,0), (b,0), (0,c), and (0,d) respectively, all of which have integer coordinates.

P is a point on AC with integer coordinates such that triangles DCP, DBP, and PAB are similar.

It can be shown that in order for the triangles to be similar, a=c.

For b+d < 100,000,000, how many triples (a,b,d) exist such that point P exists?

Initial observations

Before we can start coding, there is some geometry work to be done.

It is given that it must be necessary for a=c. Why is this? Suppose that a \neq c. Then \angle OAC \neq \angle OCA. Next, \angle DCP \neq \angle PAB. It is obvious that triangles DCP and PAB cannot be similar if \angle DCP \neq \angle PAB.

Since \angle COA is a right angle and \triangle COA is isosceles, it follows that \angle OCA = \angle OAC = 45^\circ. So \angle DCP = \angle PAB = 135^\circ and also \angle DPB = 135^\circ.

Working backwards, we know that triangles DCP, DPB, and PAB are all similar, Then \angle CDP = \angle PDB and \angle DBP = \angle PBA; lines DP and PB are angular bisectors of \triangle DOB, thus P is the incenter of \triangle DOB.

So the distance from P to the three sides OB, OD, and DB are equal. This also means P can be represented as (i,i) since its x and y coordinates are equal.

We should note at this point that there is an additional case, where \angle CDP = \angle DBP and \angle ABP = \angle BDP. Then \angle DPC = \angle BDP, so lines AC and BD are parallel. However, in this case P is no longer the incenter.

We shall consider the two as separate cases, and refer to them as the incenter and parallel case respectively.

Incenter case

We first consider the incenter case. Note that in this case, a is uniquely determined by b and d. For any pair (b,d), there is only one possible AC passing through the incenter.

We need to find pairs of (b,d) such that there exists a point (i,i) where the distance from the point (i,i) to BD is i (and that i is integral).

Line BD can be expressed by the equation

y = -\frac{d}{b}x + d ,

or in standard form,

dx + by - bd = 0 .

Recall the distance from point to line formula giving the distance between a point (m,n) to line Ax + By + C = 0:

d = \frac{|Am+Bn+C|}{\sqrt{A^2 + B^2}} .

By substitution, we have

i = \frac{|di+bi-bd|}{\sqrt{b^2 + d^2}} .

Simplifying:

i^2 (b^2 + d^2) = (di+bi-bd)^2 .

It is necessary and sufficient for b^2+d^2 to be a perfect square, as then i will be uniquely determined and will be an integer.

Thus the incenter case reduces to finding all pairs (b,d) for b+d < 100,000,000 where b^2 + d^2 is a perfect square.

Parallel case

Now we consider the case when AC || BD.

Let X be the circumcenter of \triangle DPB:

Notice that here there are actually two possible places for P. We can ignore this fact for now.

Let T be a point (not shown) such that DPBC is cyclic. Then \angle DTB = 45^\circ because \angle DPB = 135^\circ, therefore \angle DXB = 90^\circ.

As a consequence of the parallelism of AC and BD, b and d must be equal. Since \angle X is a right angle, it follows that the coordinates of X is (b,b), and that DOBX is a square.

The circle around X is centered at (b,b) and has a radius of b, thus its equation is

(x-b)^2 + (y-b)^2 = b^2 .

The line AC has an equation of

y=c-x .

By substitution into the circle equation:

(x-b)^2 + (c-x-b)^2 = b^2 ,

Or,

2x^2 + (-2c)x + (b^2+c^2-2bc)=0 ;

Applying the quadratic formula and dividing by 2 gives

x = \frac{c \pm \sqrt{c^2 - 2(b-c)^2}}{2} .

Here it is sufficient for c^2 - 2(b-c)^2 to be a perfect square, as then x will be an integer.

We prove this by using a parity argument: if c is odd, then c^2 is odd as well, and the expression inside the radical is odd; Supposing that it is a perfect square, the square root of that is odd, and when added to c, makes an even number. A similar argument applies if c is even.

We can substitute f for b-c giving the perfect square

c^2 - 2f^2.

If we let q^2 be the perfect square, we get

q^2 + 2f^2 = c^2.

Essentially the problem reduces down to finding integral solutions to the above equation, with the limit set to

2(c+f) < 100,000,000.

Writing the code

We are now ready to write a program to enumerate integer pairs to satisfy our equations.

We will start with the incenter case, which is somewhat more basic and easier to deal with.

Recall that we have derived this equation (replacing the variables with x, y, z):

x^2 + y^2 = z^2 ,

with the limit being on the sum of x+y. Obviously, this is a pythagorean triple. Enumerating pythagorean triples can be done very efficiently.

If m and n are coprime integers with an odd sum, and with m<n, then the primitive pythagorean triples can be parameterized by the formulas:

x = n^2 - m^2

y = 2mn

z = n^2 + m^2

Just by using this formula and little else, primitive pythagorean triples triples can be enumerated very quickly.

It is not very difficult to enumerate the non-primitive triples, either. Suppose we have generated the triple (3,4,5). To count the number of similar triples with x+y < 100000, sum the x and y values of the triple, which is in this case 7. Then divide the limit by 7, which in this case is \frac{100,000}{7}, so we have 14285 such triangles.

A nearly identical approach can be used to enumerate pairs for the parallel case. Here we have

x^2 + 2y^2 = z^2 ,

which is nearly identical to the previous equation and can be parameterized as:

x = n^2 - 2m^2

y = 2mn

z = n^2 + 2m^2

This case is slightly different from the previous case, in the sense that we no longer require x to be positive, so we do not need the restriction that m<n. Additionally, we need to divide by y+z, instead of x+y as we did before.

This is easy to implement in Java:


public class Main{
  final static long L = 100000000;

  static long gcd(long m, long n) {
    if (m < n) { long t = m; m = n; n = t; }
    long r = m % n;
    if (r == 0) return n;
    else return gcd(n, r); }

  static long incenterCase(){
    long count = 0;
    for(long n = 1; n < L/2; n++)
      for(long m = 1; m < n; m++){
        if((m+n) % 2 == 0) continue;
        if(gcd(m,n)!=1) continue;
        long b = n*n - m*m;
        long d = 2*n*m;
        long sum = b+d;
        if(sum >= L) break;
        if(b == d) count += L/sum;
        else count += 2*(L/sum); }
    return count; }

  static long parallelCase(){
    long count = 0;
    for(long n = 1; n < L; n+=2)
      for(long m = 1; m < L; m++){
        if(gcd(m,n)!=1) continue;
        long g = 2*n*m;
        long a = n*n + 2*m*m;
        long b = g+a;
        if(b > L/2) break;
        count += (L-1)/(2*b); }
    return count; }

  public static void main(String[] args) {
    System.out.println(incenterCase() + parallelCase()); }
}

This code generates the correct answer in about 25 seconds on my machine.

SPOJ: Absurd Prices (6803)

Just writing on a SPOJ problem I worked on recently. It’s called Absurd Prices, code name ABSURD.

In this problem, when given an integer representing an item’s price in cents, our program has to determine whether the price is absurd or not.

There is an algorithm to calculate the absurdity of an integer: the higher the absurdity, the more absurd it is. An integer c is considered absurd when within the range [0.95c,1.05c] there is an integer with a lower absurdity.

To find the absurdity of a price:

  1. Remove all the trailing 0’s from it
  2. Count the length of the remaining number
  3. The absurdity is twice the length
  4. If the number (with trailing zeroes removed) ends with 5, subtract 1 from the absurdity

As a result of these rules, prices with a lot of trailing zeroes, like 3500000, would have a very low absurdity, while those without trailing zeroes, like 7999999, would have a much higher absurdity.

A brute force approach seemed at first to be the way to go. This is because the range, [0.95c,1.05c] isn’t too big and it isn’t a big deal to simply calculate the absurdity of all of them, and mark it as absurd when any of the integers in the range has a lower absurdity.

However, the time limit is very strict for this problem. Even when my program only checked 50 random numbers in the range, the system returned with TLE (Time Limit Exceeded)!

Fortunately there is a better way of solving the problem.

Given a range, it is easy to find the least absurd number in the range. For example, if our minimum and maximum bounds are 6655 and 7799 respectively, it’s easy to see that the least absurd number in that range is 7000, simply because it has the most trailing zeroes.

The algorithm that we can use to find the least absurd number in a range (defined by two integers) is follows:

  1. In their decimal expansions, compare the first characters, then the second characters, etc, until the n^{th} character is different.
  2. The minimum absurdity is 2n.
  3. If the n^{th} character of the smaller number is less than 5, and the n^{th} character of the larger number is five or greater, subtract 1 from the minimum absurdity.

Here’s my implementation in Haskell:

-- Integer with trailing zeroes removed
removeZeroes x = head . filter (\n -> n `mod` 10 > 0) $
  iterate (\n -> n `div` 10) x

-- Calculuate the absurdity of a price
absurdity x = let
  r = removeZeroes x
  d = fromIntegral . length $ show r
  l = r `mod` 10
  in if l == 5 then 2*d-1 else 2*d

-- The minimum possible absurdity in a given range
minabsd a b | a == b = absurdity a
minabsd a b = let
  c = show a; d = show b
  sm = fromIntegral . length . takeWhile (uncurry (==)) $ zip c d
  lst = (c!!sm,d!!sm)
  offset = if fst lst < '5' && snd lst >= '5' then 1 else 0
  in minimum [absurdity a, (2 * (sm + 1) - offset), absurdity b]

absurd x = let
  r1 = ceiling $ 0.95*(realToFrac x)
  r2 = floor $ 1.05*(realToFrac x)
  absx = absurdity x
  in absx > minabsd r1 r2

main = interact run where
  as s = let k = read s in if absurd k then "absurd" else "not absurd"
  run = unlines . map as . tail . lines

IMO 2010: Problem 5

Problem 5 of the IMO was definitely the most interesting problem in the contest, although one of the harder ones. A mere 37 people out of 511 managed to solve it completely.

What made it so different was that it did not require any particular knowledge on olympiad math theorems, indeed such knowledge would be useless for this problem. It required only creative insight, and quite a bit of it. Technically it’s a combinatorics problem, but no specific combinatorics experience is needed to solve the problem.

Also this problem was the target for a mini-polymath project organized by Terry Tao, which took about two and a half hours to get from start to solving the problem. The solution I’ll give is mostly based on the polymath solution, although I came up with my own finishing steps which I think is less awkward.

Problem

In each of six boxes B_1,B_2,B_3,B_4,B_5,B_6 there is initially one coin. There are two types of operation allowed:

Type 1: Choose a nonempty box B_j with 1 \leq j \leq 5. Remove one coin from B_j and add two coins to B_{j+1}.

Type 2: Choose a nonempty box B_k with 1 \leq k \leq 4. Remove one coin from B_k and exchange the contents of (possibly empty) boxes B_{k+1} and B_{k+2}.

Determine whether there is a finite sequence of such operations that results in boxes B_1,B_2,B_3,B_4,B_5 being empty and box B_6 containing exactly 2010^{2010^{2010}} coins. (Note that a^{b^c}= a^{(b^c)}.)

Initial observations

It is not entirely obvious how this problem should be approached; thus we will begin by playing with it and jotting down any interesting observations.

We begin with one coin in each box. For convenience, I will express this as

(1,1,1,1,1,1) .

We need to have

(0,0,0,0,0,2010^{2010^{2010}})

Again for convenience, let us substitute

D = 2010^{2010^{2010}}.

Now we can express the two types of moves in our new notation. First, Type 1 moves (we shall call it Move 1):

(a,b) \to (a-1,b+2).

Next, Type 2 moves:

(a,b,c) \to (a-1,c,b).

Notice how applying Move 1 adds one coin to the system as a whole, while Move 2 takes away one coin.

By applying Move 2 over and over, it is easy to remove arbitrarily large amounts of coins from the system (as long as the coins are in the first four boxes).

On the other hand, it isn’t so clear how do add large amounts of coins to the system.

Applying Move 1 adds a coin to the system, so logically adding coins should be done by repeated usage of Move 1.

Given (a,b), applying Move 1 results in (a-1,b+2); applying it again results in (a-2,b+4). We can repeat this as many times as we like, or until the first box is depleted.

This creates a compound move for a pair, executed by applying Move 1 repeatedly:

(a,b) \to (0,b+2a).

What if we apply this on all six boxes? We first get

(0,3,1,1,1,1)

Next we have

(0,0,7,1,1,1);

A few more iterations and we will have:

(0,0,0,0,0,63).

We are far from our target: we have 63 coins and we’re stuck. There doesn’t seem to be any other way to introduce any more coins into the system.

The problem seems hopeless.

Building up a repository of compound moves

We first need a way of getting a large amount of coins into the system. From there is is easy to reduce the coins.

The compound move explained in the previous section is a first step. Let’s call it Compound Move 1:

(a,b) \to (0,b+2a).

The next compound move is less obvious. Suppose that we start with

(a,0,0).

Applying Move 1 gives us

(a-1,2,0)

which, using Compound Move 1, can be used to get

(a-1,0,4).

Now we apply Move 2. Using up a coin to switch the two boxes, we have

(a-2,4,0)

Or equivalently,

(a-2,0,8).

We can repeat this: switching, doubling, switching again, and so on, until the first box is depleted. This gives us

(0,2^a,0).

So here we have Compound Move 2:

(a,0,0) \to (0,2^a,0).

This is a lot better than what we had before. However, it’s still a while towards our goal.

With Compound Move 1, each additional coin in the left most box adds 2 coins to the next box.

But with Compound Move 2, each additional coin doubles the result in the next box.

Now this problem has a Towers of Hanoi feel to it. It turns out that we can take this one step further, which, when examined closely, looks remarkably similar to the previous case.

Suppose we have

(a,0,0,0).

in four consecutive boxes. Applying Move 1:

(a-1,2,0,0).

Applying Compound Move 2 using the last three boxes, we get

(a-1,0,2^2,0).

Now we apply Move 2 and switch the boxes:

(a-2,2^2,0,0).

If we do this again, we get

(a-3,2^{2^2},0,0).

So, repeating this many times until the left box is empty gives us

(0,2^{\cdot^{\cdot^2}},0,0).

No doubt the number we have is sufficiently big now. We will call this move Compound Move 3, which can only be expressed reasonably with Knuth’s up-arrow notation:

(a,0,0,0) \to (0, 2 \uparrow \uparrow a,0,0).

Putting it together

The configuration we want is

(0,0,0,0,0,D)

which is equivalent to

(0,0,0,\frac{D}{4},0,0).

It’s relatively easy to get most of the boxes empty except for the third. From the starting position, Move 1 gives us

(1,1,1,1,0,3)

Applying Move 2 three times gives us

(1,0,3,0,0,0);

Move 1 then gives

(0,0,7,0,0,0).

We invoke Compound Move 3, getting

(0,0,0,2 \uparrow \uparrow 7,0,0).

Finally we can waste coins by consecutively executing Move 2 until we have

(0,0,0,\frac{D}{4},0,0)

And we’re done.

An additional note

It is easy to show, albeit informally, that 2 \uparrow \uparrow 7 > \frac{D}{4}. If we take the binary log (I’ll write it as \log x) of both sides, we have

2 \uparrow \uparrow 6 > 2010^{2010} \cdot \log 2010 - 2.

It’s okay to ‘throw away’ the 2, considering the magnitude of the numbers. Taking the log again:

2 \uparrow \uparrow 5 > 2010 \cdot \log (2010 \cdot \log 2010).

Considering that 2 \uparrow \uparrow 5 = 2^{65536}, and the right hand side evaluates to just a few thousand, it’s fairly safe to say which is bigger.

IMO 2010: Problem 2

In this year’s IMO, there were two geometry problems. Problem 4 is generally considered the easier one of the two. Problem 2 is the other problem, being a bit harder. Of the 517 contestants, 366 of them received a full mark on problem 4; only 162 students got a full mark for problem 2.

The Problem

Let I be the incentre of triangle ABC and let \Gamma be its circumcircle. Let the line AI intersect \Gamma again at D. Let E be a point on the arc \widehat{BDC} and F a point on the side BC such that

\angle BAF = \angle CAE < \frac{1}{2} \angle BAC .

Finally, let G be the midpoint of the segment IF. Prove that the lines DG and EI intersect on \Gamma.

Solution

It turns out that several solutions exist. Several of the solutions use Menelaus’s theorem, which I’ve never even heard of; others rely on properties of excircles. I’ll give the solution that I think is the most elegant (although it doesn’t seem to be the standard solution).

We start by working backwards.

Let us denote K to be the point of intersection between DG and EI; we wish to prove that K lies on \Gamma. If K lies on \Gamma, then quadrilateral AKDE is cyclic, and \triangle IKD \sim \triangle IAE.

Obviously \angle KID = \angle AIE. If we can show that \angle GDI = \angle AEI, then triangles IKD and IAE are similar and our result follows.

Let M be the midpoint of AI.

We will prove that \angle GDI = \angle AEI by proving that \triangle MGD and \triangle AIE are similar (these are the triangles highlighted in red).

It is given that \angle CAE = \angle BAF, so angles \angle DAE and \angle DAF are also equal (since AD passes through the incenter I and thus bisects \angle A).

It is also given that FG = GI; now IM = MA by definition so triangles IFA and IGM are similar. Then \angle GMD = \angle IAE.

All that remains to prove the similarity of \triangle MGD and \triangle AIE (and thus the result) is to prove that

\frac{MG}{MD} = \frac{AI}{AE}

or equivalently

MG \cdot AE = AI \cdot MD .

As \triangle IFA \sim \triangle IGM, and IG = \frac{1}{2}IF, it follows that MG = \frac{1}{2}AF. By substitution,

\frac{1}{2}AF \cdot AE = AI \cdot MD .

It can be shown that the product AF \cdot AE is constant no matter where E is on the circle:

Draw the line EC; the triangle formed, \triangle ACE, is similar to \triangle AFB since \angle CAE = \angle CAF and \angle ABF and \angle AEC subtend the same arc.

Then

\frac{AF}{AB} = \frac{AC}{AE}

or

AE \cdot AF = AB \cdot AC .

Since AB \cdot AC is constant with respect to E (and F), so is AE \cdot AF.

Consequentially we can prove that \frac{1}{2}AE \cdot AF = AI \cdot MD for all values of E and F by proving it for one value of E and F, since \frac{1}{2} AE \cdot AF is constant and obviously AI \cdot MD is constant.

We prove the case for \angle CAE = 0, or in other words when E coincides with C and F coincides with B:

So here we need to prove that

\frac{1}{2} AB \cdot AC = AI \cdot MD .

This is equivalent to proving that K lies on \Gamma in this instance, as that would prove the above equation too for this instance.

Obviously \angle ACK = \angle ADK, also \angle BCK = \angle BDK. As \angle ACK = \angle BCK since CK passes through the incircle and is an angle bisector, it follows that \angle ADK = \angle BDK.

Given BG=GI, this is sufficient to prove \triangle BDI to be isosceles.

So \angle BDG = \angle GDI, and DG meets \Gamma at the midpoint of minor ark \widehat{AB}. Obviously CI meets \Gamma at the same point, and we are done. QED.

Checking the solution

Just to make sure, we can trace out steps back to get from the equation \frac{1}{2} AE \cdot AF = AI \cdot MD to our result that K lies on \Gamma. I’m going to go through it very briefly:

From the equation we get \frac{MG}{MD} = \frac{AI}{AE}, proving triangles MGD and AIE to be similar.

Then \angle GDI = \angle AEI and triangles KDI and AEI are similar. Finally AKDE is cyclic, leading to the result.

It is also valid to, starting with the result, arrive at the equation, which is what we implicitly did near the end of the solution.

IMO 2010: Problem 4

The International Olympiad of Mathematics took place on July 8 and 9, and the six questions were made available the second day. This was a two day contest, three questions per day, and four and a half hours per day, giving a total of nine hours for the six questions. The international contest included questions on geometry, algebra, combinatorics, and number theory.

Contest questions may be downloaded here.

This year, it seems that problems 1 and 4 were the easiest (by comparison). I’ve only looked at problem 4 in detail (probably because it’s geometry).

Problem

Let P be a point inside the triangle ABC. The lines AP, BP and CP intersect the circumcircle \Gamma of triangle ABC again at the points K, L and M respectively. The tangent to \Gamma at C intersects the line AB at S. Suppose that SC = SP. Prove that MK = ML.

Solution

As often with geometry problems, a variety of different solutions are possible. Some are simple, while others rely on homothetic transformations and inversions. I’m going to go with the method I came up with (albeit with a few peeks at the Art of Problem Solving forums).

From the Power of a Point theorem, we have

SC^2 = SA \cdot SB

But it’s given that SP = SC, so

SP^2 = SA \cdot SB

Or,

\frac{SP}{SA} = \frac{SB}{SP}

This is enough to show that triangles SAP and SPB are similar, since they also share an angle.

Therefore,

\frac{SA}{AP} = \frac{SP}{BP}

Or,

\frac{AP}{BP} = \frac{SA}{SP}

Since SP = SC,

\frac{AP}{BP} = \frac{SA}{SC} \; \; \; (1)

Triangles SCA and SBC are similar, since they share an angle and \angle SCA = \angle ABC. Thus,

\frac{SA}{AC} = \frac{SC}{BC}

Or,

\frac{SA}{SC} = \frac{AC}{BC}

From (1),

\frac{AP}{BP} = \frac{AC}{BC}

Or equivalently,

\frac{AC}{AP} = \frac{BC}{BP} \; \; \; (2)

Notice that triangles APC and MPK are similar (\angle CMK and \angle CAK subtending the same arc); so,

\frac{AC}{AP} = \frac{MK}{MP}

Similarly, triangles MPL and BPC are also similar, giving

\frac{BC}{BP} = \frac{ML}{MP}

From (2),

\frac{MK}{MP} = \frac{ML}{MP}

This shows that MK = ML, as desired. QED.

On some number-theoretic properties of right triangles (Project Euler 218)

The two hundred and eighteenth problem of Project Euler is quite interesting, but different. It resembles more closely a mathematics olympiad problem than a programming challenge. Its answer is somewhat surprising, too.

Original problem

The problem can be stated as follows:

A right triangle is considered perfect if (1): it is primitive (GCD of the three sides is 1) and (2): its hypotenuse is a perfect square.

A perfect triangle is considered superperfect if its area is divisible by the perfect numbers 6 and 28.

How many perfect triangles are there with hypotenuse below 10^{16} that are not also superperfect?

Answer

It turns out that every perfect triangle is also superperfect, meaning that for any limit there are no perfect triangles that are not superperfect.

Looking on the forums, it seems that a large group of solvers counted the triangles for a smaller limit, like 10^{9} or 10^{12} , and getting 0, assumed the answer applied for 10^{16} .

In this article I will attempt to prove, mathematically, that it is indeed impossible for a perfect triangle not to be superperfect.

Proof

Let’s rephrase this problem a bit: Prove that if a primitive right triangle has a hypotenuse that is a perfect square then its area must be a multiple of 6 and 28.

If the area is a multiple of 6 and 28, then it is a multiple of \mathrm{LCM}(6,28) = 84 . If we let p, q, and c be the sides of the right triangle (with c as the hypotenuse), then the area is \frac{pq}{2} .

Since 84 | \frac{pq}{2} , it follows that 168 | pq . As c is a perfect square, we write c as r^2 and since \mathrm{GCD}(p,q,c)=1 , it also follows that \mathrm{GCD}(p,q,r)=1 . This is what we shall now prove.

Lemma 1

For positive integers p, q, r where p^2 + q^2 = r^4 and \mathrm{GCD}(p,q,r)=1 , then 168|pq .

From the Euclid theorem of Pythagorean triples, the sides of a primitive right triangle with sides a, b, and c can be represented as:

a = u^2 - v^2

b = 2uv

c = u^2 + v^2

.. where u>v and u and v are of opposite parity.

Thus by applying the theorem to our triple:

p = u^2 - v^2

q = 2uv

r^2 = u^2 + v^2

Notice here that the third equation here itself represents a pythagorean triple. We then apply the same formula again, this time using m and n for the integers:

u = m^2 - n^2

v = 2mn

r = m^2 + n^2

Substituting for p, q, r:

\begin{array}{rcl} p &=& u^2 - v^2 \\ &=& (m^2-n^2) - (2mn)^2 \\ &=& m^4 - 2m^2n^2 + n^4 - 4m^2n^2 \\&=& m^4 + n^4 - 6m^2 n^2 \\ \\ q &=& 2uv \\ &=& 2(m^2-n^2)(2mn) \\ &=& 4mn(m^2-n^2) \\ \\ r &=& m^2 + n^2 \end{array}

Then,

pq = 4mn(m^2-n^2)(m^4+n^4-6m^2n^2)

.. which we will prove to be divisible by 168. Since 168=8*3*7, the expression must be proved to be divisible by 8, by 3, and by 7.

Lemma 2

8 | 4mn(m^2-n^2)(m^4+n^4-6m^2n^2)

Proof of Lemma 2

The proof is almost trivial. In order for the triple to primitive, m and n must be of opposite parity, meaning mn is even.

Because 2|mn and 4 is already a factor of the expression, it follows that 8|pq .

Lemma 3

3 | mn(m^2-n^2)

Proof of Lemma 3

Rewrite the expression as

mn(m+n)(m-n) .

If 3|m or 3|n , then 3|mn .

If m \equiv n \mod 3 , then m-n \equiv 0 \mod 3 .

The only other scenario is when m \not \equiv n \mod 3 , then either m \equiv 1 \mod 3 and n \equiv 2 \mod 3 or vice versa. Either way, m+n \equiv 0 \mod 3 .

Lemma 4

If 7 \nmid m , then m^2 \equiv 1,2,4 \mod 7 .

Proof of Lemma 4

We construct a table. The first column of this table is m \mod 7 while the second column is m^2 \mod 7:

1 1
2 4
3 2
4 2
5 4
6 1

The only possible values are 1, 2, and 4.

Lemma 5

If 7 \nmid m^2 - n^2 , then either m^2 \equiv 2n^2 \mod 7 or n^2 \equiv 2m^2 \mod 7 .

Proof of Lemma 5

Because 7 \nmid m^2 - n^2 , m^2 \not\equiv n^2 \mod 7 . Then, not counting reflective cases, there are three cases we need to consider:

Case 1: m^2 \equiv 1, n^2 \equiv 2 . Then n^2 \equiv 2m^2 \mod 7 .

Case 2: m^2 \equiv 1, n^2 \equiv 4 . Then m^2 \equiv 2n^2 \mod 7 .

Case 3: m^2 \equiv 2, n^2 \equiv 4 . Then n^2 \equiv 2m^2 \mod 7 .

One of these (or their reflection) apply for whatever value of m and n.

Lemma 6

7 | m^4 + n^4 - 6m^2n^2

Proof of Lemma 6

Without loss of generality, rewrite the expression as a congruence mod 7, in terms of m. Since m^2 \equiv 2n^2 \mod 7,

\begin{array}{rcl} m^4 + n^4 - 6m^2n^2 &=& m^4 + (2m^2)^2 - 6m^2(2m^2) \\ &=& m^4 + 4m^4 - 12m^4 \\ &=& -7m^4 \end{array}

The result follows.

Q.E.D.

Random Math Problems (3)

School finished yesterday. After one exam next week (for math), I’m done grade 10. I’ll probably have more time to write blog posts in the summer.

Problem 1

(from Geometry Revisited)

Prove that in this triangle (a being m+n), that

a(p^2+mn) = b^2m + c^2n

This seems like a really weird thing to prove, but apparently it’s known as Stewart’s theorem and is useful in some places.

Solution

Recall the Law of Cosines:

\cos C = \frac{a^2+b^2-c^2}{2ab}

We can apply the Law of Cosines twice to \angle AXB and \angle AXC:

\cos \angle AXB = \frac{p^2+m^2-c^2}{2mp}

\cos \angle AXC = \frac{p^2+n^2-b^2}{2np}

Adding the two together,

\cos \angle AXB + \cos \angle AXC = \frac{p^2+m^2-c^2}{2mp} + \frac{p^2+n^2-b^2}{2np}

Notice that because \cos(\theta) = \cos(180-\theta), the sum of cosines of supplementary angles is 0. Therefore,

\begin{array}{rcl} 0 &=& \frac{p^2+m^2-c^2}{2mp} + \frac{p^2 + n^2 - b^2}{2np} \\ &=& n(p^2+m^2-c^2) + m(p^2 + n^2 - b^2) \\ &=& np^2 + nm^2 - nc^2 + mp^2 + mn^2 - mb^2 \end{array}

Moving the two negative terms to the left hand side and factoring,

\begin{array}{rcl} b^2m + c^2n &=& np^2 + nm^2 + mp^2 + mn^2 \\ &=& n(p^2) + m(p^2) + n(mn) + m(mn) \\ &=& (m+n)(p^2+mn) \end{array}

The result follows:

b^2m + c^2n = a(p^2+mn)

Problem 2

(from the 2010 UVM contest)

How many ways are there to arrange the letters of the word NOODLES, so that the consonants (NDLS) appear in alphabetical order (although not necessarily consecutively)?

Solution

The four consonants must appear in the order of D, L, N, S. The three vowels, OOE, must appear somewhere in the five spaces between the consonants:

Thus the answer to the problem is the same as the number of ways to pack OOE into five boxes, a box being able to hold an arbitrary amount of letters, and permutations of letters within a box being counted as distinct.

This is half of the number of ways to pack ABC into five boxes, since there are two O’s in OOE. We will now calculate how many ways there are to pack ABC into five boxes.

We can split up this problem into several cases:

Case 1: All three letters ABC are in the same box. For any box there are 3! = 6 ways to permute ABC, while there are five boxes. The total for this case is 6*5 = 30.

Case 2: The three letters all go in three different boxes. This is simply P(5,3) which is 60.

Case 3: Two of the letters go in a box, while the third letter goes in a different box. This is a little bit tricky, so we break it in a few parts.

First of all we choose the two boxes of the five we use. The number of ways to do this is \binom{5}{2} which is 10. Secondly, if the two boxes are labelled Box 1 and Box 2, we can either put two letters in Box 1 and one in Box 2, or the other way around, giving an additional two ways.

Finally there are 3! or 6 ways to permute the three letters. The final count for case 3 is 10 * 2 * 6 or 120.

The number of ways to pack ABC into five boxes is the sum of the three cases, or 210. The answer to the problem is half of that, 105.

Problem 3

(again from the same UVM contest)

Point P is inside rectangle ABCD. If the distance from P to three corners of the rectangle are 5, 10, and 14, find the distance from P to the forth corner.

Solution

We first draw perpendicular lines from P to the four sides of the rectangle and label them a, b, c, and d, like this:

From pythagorean, we find that

b^2 + c^2 = 5^2

b^2 + d^2 = 10^2

a^2 + d^2 = 14^2

As we are looking for the length of DP, we can manipulate the three equations to get a value for a^2 + c^2:

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

Finally we can now substitute in real values to find a^2 + c^2:

a^2+c^2 = 5^2 + 14^2 - 10^2 = 121

The line DP can be found by taking a square root, it is 11.

General formula

When three of the four diagonals of a rectangle are known, the forth one can be calculated. Suppose we know m, n, and o. The formula for x is given by:

x = \sqrt{m^2 + n^2 - o^2}

Problem 4

This problem is from the Number Theory chapter of The Art and Craft of Problem Solving.

Prove that

\frac{n^3 + 2n}{n^4 + 3n^2 + 1}

is in lowest terms for all positive integers n.

Solution

Another way of saying this problem is that

\textrm{GCD}(n^3 + 2n,n^4 + 3n^2 + 1) = 1

for all positive integers n.

Then there does not exist any integer c, where c > 1, c | n^3+2n and c | n^4+3n^2+1. Supposing c exists, and it divides n^3+2n, we can prove by contradiction that c cannot simultaneously divide n^4+3n^2+1.

If c divides n^3+2n or n(n^2+2), then either c | n or c | n^2+2.

We can rewrite n^4 + 3n^2 + 1:

n^3 + 3n^2 + 1 = n^2(n^2+3) + 1

This way it can be seen that n \perp n^2(n^2+3) , as two consecutive integers are relatively prime.

To show that n^2+2 is also relatively prime, we rewrite it this way:

n^3 + 3n^2 + 1 = (n^2+1)(n^2+2)-1

This shows that, n^2+2 \perp (n^2+1)(n^2+2)-1.

As both n and n^2+2 are relatively prime to n^4 + 3n^2 + 1, it follows that c \perp n^4 + 3n^2 + 1, which is what needs to be shown.

Random Math Problems (2)

Okay, these problems are not really random, they’re from the same section of a textbook:

This book is called Geometry Revisited (by Coxeter and Greitzer). It’s often recommended as a olympiad level geometry textbook. I would recommend this book too (although I haven’t gone through the entire book yet).

Section 1.1 of this book proves a theorem referred to as the Extended Law of Sines:

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

where R is the circumradius of triangle ABC.

The extended Law of Sines is often given in a truncated form, without mention to the circumradius.

After the proof the book gives four exercises, which I shall rephrase and solve here.

Problem 1

Show that in any triangle \triangle ABC,

a = b \cos C + c \cos B

From this, deduce the ‘addition formula’ for sines:

\sin (B+C) = \sin B \cos C + \sin C \cos B

Solution

From the Law of Cosines:

\begin{array}{rcl} c^2 &=& a^2 + b^2 - 2ab \cos C \\ b^2 &=& a^2 + c^2 - 2ac \cos B \end{array}

Adding the two:

\begin{array}{rcl} c^2 + b^2 &=& 2a^2 + c^2 + b^2 - 2ab \cos C - 2ac \cos B \\ 2a^2 &=& 2ab \cos C + 2ac \cos B \\ a &=& b \cos C + c \cos B \end{array}

as desired.

We now prove the addition formula. From the law of sines:

\begin{array}{rcl} \frac{a}{\sin A} &=& 2R \\ a &=& 2R \sin A \end{array}

Similarly:

\begin{array}{rcl} b &=& 2R \sin B \\ c &=& 2R \sin C \end{array}

Substituting into our previous equation:

\begin{array}{rcl} a &=& b \cos C + c \cos B \\ 2R \sin A &=& 2R \sin B \cos C + 2R \sin C \cos B \\ \sin A &=& \sin B \cos C + \sin C \cos B \end{array}

Since \triangle ABC is a triangle, A+B+C = 180. Thus, A = 180 - (B+C).

Note that \sin \theta = \sin (180 - \theta). Thus,

\sin (B+C) = \sin A = \sin B \cos C + \sin C \cos B

as desired.

Problem 2

Show that in any triangle \triangle ABC,

a (\sin B - \sin C) + b (\sin C - \sin A) + c(\sin A -\sin B) = 0

Solution

Using the law of sines again:

\begin{array}{rcl} \frac{a}{\sin A} &=& \frac{b}{\sin B} \\ a \sin B &=& b \sin A \\ a \sin B - b \sin A &=& 0 \end{array}

Similarly,

\begin{array}{rcl} b \sin C - c \sin B &=& 0 \\ c \sin A - a \sin C &=& 0 \end{array}

Adding the three equations:

\begin{array}{rcl} a \sin B - b \sin A + b \sin C - c \sin B + c \sin A - a \sin C &=& 0 \\ a (\sin B - \sin C) + b(\sin C - \sin A) + c(\sin A - \sin B) &=& 0 \end{array}

as desired.

Problem 3

Show that in any triangle \triangle ABC,

[ABC] = \frac{abc}{4R}

(although the book uses (ABC), I’ve accustomed to writing [ABC] on my blog to denote area of \triangle ABC)

Solution

Let h be the height of \triangle ABC (from A perpendicular to BC), so that [ABC] = \frac{1}{2} ah:

Using trigonometry,

h = b \sin C

so we can write the area as

[ABC] = \frac{1}{2} ab \sin C

From the extended Law of Sines,

\begin{array}{rcl} \frac{c}{\sin C} &=& 2R \\ \sin C &=& \frac{c}{2R} \end{array}

Now we can rewrite the area again:

\begin{array}{rcl} [ABC] &=& \frac{1}{2}ab \frac{c}{2R} \\ &=& \frac{abc}{4R} \end{array}

as desired.

Problem 4

For a triangle \triangle ABC, let p be the radius of a circle going through A and tangent to BC at B. Let q be the radius of a circle going through A and tangent to BC at C.

Show that:

pq = R^2

Solution

Let M be the center of the circle with radius p, and N be the center of the circle with radius q. Also K and L are two points on circles M and N respectively:

Using the law of sines on circle N and M, we have:

\begin{array}{rcl} \frac{b}{\sin L} &=& 2q \\ \frac{c}{\sin K} &=& 2p \end{array}

Because BC is tangent to the two circles, \angle L = \angle C and \angle K = \angle B.

Thus,

\begin{array}{rcl} \frac{b}{\sin C} = 2q  & \Rightarrow & b = 2q \sin C \\ \frac{c}{\sin B} = 2p & \Rightarrow & c = 2p \sin B \end{array}

Now applying the Law of Sines again in \triangle ABC:

\begin{array}{rcl} \frac{b}{\sin B} = 2R & \Rightarrow & \sin B = \frac{b}{2R} \\ \frac{c}{\sin C} = 2R & \Rightarrow & \sin C = \frac{c}{2R} \end{array}

Substituting these values back into the previous equation:

\begin{array}{rcl} b = 2q \frac{c}{2R} = \frac{qc}{R} & \Rightarrow & q = \frac{bR}{c} \\ c = 2p \frac{b}{2R} = \frac{pb}{R} & \Rightarrow & p = \frac{cR}{b}\end{array}

By multiplication,

pq = \frac{bR}{c} \frac{cR}{b} = R^2

as desired.

Random Math Problems (1)

Probably any of these problems would be too small to include in a blog post on their own, so it might be more efficient (?) to put several of them together into one post.

The problems are not mine, and the solutions are not mine. They are just interesting problems I’ve come across when studying for math olympiads.

I hope to publish more collections of these random math problems in the future. That’s why I’m appending (1) to this post.

Problem 1

(From the 2010 Fermat contest)

Spheres can be stacked together into a tetrahedron (triangular pyramid). Here’s a visual (not created by me, from Wikipedia):

Each of the spheres in the tetrahedron has a number written on it. The top sphere is 1, and the number of any sphere is the sum of the numbers on the spheres in the layer above.

An internal sphere is defined as a sphere that is not on the outside, or in other words, touching exactly three spheres in the layer above.

In a tetrahedron with 13 layers, what is the sum of the numbers on all of the internal spheres?

Solution

Let’s draw out a few layers of the tetrahedron.
Hosted by imgur.com

Look for patterns.

There’s a few things that can be noticed-

  1. The numbers at the three corners of a layer are 1
  2. Any layer is highly symmetrical: in the last diagram the sequence (1 4 6 4 1) appears in the bottom row, as well as the left and right diagonals. We can rotate the tetrahedron and the numbers would still be the same.
  3. The numbers on the outside form Pascal’s triangle. The sequence (1 3 3 1) is the 4th row of Pascal’s triangle; (1 4 6 4 1) is the 5th, and so on.

The most important thing to look for is the fact that Pascal’s triangle appears in the tetrahedron.

Each row of Pascal’s triangle is one longer than the previous row. To calculate a row, overlap the previous row with the new row, like this:
Hosted by imgur.com

Here the number in a purple box is the number to the top-right of it plus the number to the top-left of it:
Hosted by imgur.com

Simple.

Notice that each number in the top gets added into exactly two boxes at the bottom.

Therefore the sum of the numbers in the bottom is twice the sum of the numbers in the top. 1 + 3 + 3 + 1 = 8, and 1 + 4 + 6 + 4 + 1 = 16.

This applies to any two rows. The sum of any row is twice the sum of the previous row.

Since the sum of the first row is 1, the sum of the second is 2, the sum of the third 4, and so on. We can even express this as a formula. The sum of the nth row is:

2^{n-1}

A similar idea applies to the layers of the tetrahedron.

In Pascal’s triangle, each number gets added to two places in the next row.

The tetrahedron is like Pascal’s triangle, in three dimensions. Each sphere in the tetrahedron sits on top of three spheres in the layer under it. So each number gets added to three different numbers in the next row.

Thus the sum of the numbers in any layer of the tetrahedron is 3 times the sum of numbers in the previous layer.

A formula for the sum of the nth layer of the tetrahedron:

3^{n-1}

What we really want is a formula for the middle numbers, or internal spheres. The internal spheres are the spheres that are not on the outer layer.

We know the formula for the sum of the whole layer, and we know the formula for any of the three ‘sides’ of a layer.

Hosted by imgur.com

The internal numbers would be the sum of the entire layer minus three times the sum of a side. To cover up for the three 1’s we’ve counted more than once, we add 3 to the result.

The formula for the sum of the internal numbers on the nth layer:

3^{n-1} - 3 \cdot 2^{n-1} + 3

The problem asks for the sum of the first to the thirteenth layer. Well, the first three layers don’t have any internal spheres so we start from the forth:

\begin{array}{l} \displaystyle\sum_{n=4}^{13} 3^{n-1} - 2^{n-1} + 3 \\ = (3^3 + 3^4 + \cdots + 3^{12}) \\ \quad - 3(2^3 + 2^4 + \cdots + 2^{12}) + 3 \cdot 10 \end{array}

We can use the sum of geometric series formula, or more easily calculate it by brute force. The answer would be 772626.

Problem 2

(From the 2008 Canadian Math Olympiad)
Hosted by imgur.com

In quadrilateral ABCD, CM splits the quadrilateral into two parts of equal area. AN also splits the quadrilateral into two parts of equal area. AB is the longest side of the quadrilateral.

Prove that MN bisects DB.

Solution

I’m going to use the equal sign to mean two figures with equal areas, not two figures that are congruent.

The triangles \triangle ANB and \triangle MCB are both half of ABCD, so their areas are equal. Then \triangle ANB = \triangle MCB.

\triangle ANB can be split into \triangle ANM + \triangle MNB, and similarly \triangle MCB can be split into \triangle MCN + \triangle MNB.

We know that \triangle ANB = \triangle MCB. By subtraction, \triangle AMN = \triangle MCN.

The triangles \triangle AMN and \triangle MCN share a common base, MN. Because their areas are equal, the perpendicular from A to MN is equal to the perpendicular from C to MN. Therefore AC || MN.

Now we draw a line through D, parallel to AC and MN. We extend AB and BC to meet this line (and we draw a couple of additional lines):
Hosted by imgur.com

Because XY || AC, \triangle ADC = \triangle AXC = \triangle AYC.

Here \triangle MCB = ADCM.

We can write ADCM as \triangle ADC + \triangle ACM. Since \triangle ADC = \triangle AXC, ADCN = \triangle XCM.

It follows that \triangle MCB = \triangle XCM, and XM = MB.

Similarly, ADCN = \triangle AYN. Then \triangle ANB = ADCN = \triangle AYN, and YN = NB.

Because XM = MB and YN = NB, the result follows that DK = KB.

Problem 3

(From the 2010 USAMO)

This problem actually appears in both the junior and senior USAMO taken about a week ago from time of writing. It’s problem 4 in the senior and problem 6 in the junior.

Hosted by imgur.com

\triangle ABC is a right triangle. BD bisects \angle ABC, and EC bisects \angle ACB.

Prove that the lines [AB, AC, BI, ID, CI, IE] cannot all have integer lengths.

Solution

I was really surprised at how short and simple the solution can be for this problem.

Because \angle BAC = 90, \angle ABC + \angle ACB = 90 and \angle IBC + \angle ICB = 45 because of the angle bisectors.

Then \angle BIC = 180-45 = 135.

First we apply the pythagorean theorem:

BC^2 = AB^2 + AC^2

We then apply the Law of Cosines:

BC^2 = IB^2 + IC^2 - 2 \cdot IB \cdot IC \cdot \cos 135

Combining the two, and substituting -\frac{1}{\sqrt{2}} for \cos 135:

\begin{array}{c} AB^2 + AC^2 = IB^2 + IC^2 + 2 \cdot IB \cdot IC \cdot \frac{1}{\sqrt{2}} \\ \frac{2 \cdot IB \cdot IC}{AB^2 + AC^2 - IB^2 - IC^2} = \sqrt{2} \end{array}

This is absurd, if AB, AC, IB, and IC are all integers and nonzero.

2010 Euclid Contest

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}