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, 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. 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.

-- 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 ﬁnite 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. 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: 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: 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. 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) 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): 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. $\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) 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 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: The sum of the amount of times spent in each segment is 270 minutes. 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): 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

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.

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:

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.

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

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?

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:

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}