Problem 10 of the 2011 Euclid Math Contest (remix)

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

A modified problem

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

Similar triangles

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

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

From the similar triangles ratio

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

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

d = \frac{bc}{a}

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

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

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

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

Constructing another similar triangle

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

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

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

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

With this construction, we can write the ratio

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

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

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

Simplifying this gives

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

Number theory magic

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

If we expand the equation, we get

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

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

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

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

So we defined D:

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

Expanding this gives

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

Fortunately, this expression has an interesting factorization:

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

Or we can also write

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

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

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

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

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

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

Rotating a Hyperbola

The equation of a hyperbola gives it some very interesting properties under a series of stretches. Consider the hyperbola xy=1:

If we stretch the hyperbola horizontally by a factor of 2 about the x axis — replacing x in the equation xy=1 with \frac{x}{2}, we have the equation xy=2.

Now, if we compress the resulting hyperbola vertically by a factor of 2 — replacing y in the equation xy=2 with 2y and simplifying, we get the original hyperbola, xy=1. So by a horizontal stretch followed by a vertical compression, we get the original hyperbola.

However, consider a point on the hyperbola xy=1, say (x,y). Stretching the hyperbola horizontally by a factor of 2, this point gets transformed to (2x,\frac{y}{2}). Even though each point has a different image point, however, the graph as a whole remains identical.

More generally, if we stretch by a factor of k instead of 2, where k is any positive number, we still obtain the original hyperbola after the two stretches. The point (x,y) gets transformed to the point (kx,\frac{y}{k}). We call this combinations of transformations a hyperbolic rotation. Intuitively, the points on the hyperbola are ‘rotated’ downwards.

There are some interesting things about the hyperbolic rotation. For one, by choosing the right k for the transformation, it is possible to transform any point on the hyperbola into any other point on the same arm of the hyperbola (by allowing k to be smaller than 1). Also, since the hyperbolic rotation is composed of two simple stretches, parallel lines as well as ratios of a line segments are preserved. The area of a figure is also preserved since one stretch reduces the area, while the other multiplies the area by the same amount.

With these facts, we can prove things about the hyperbola itself:

Theorem: Let P be a point on the hyperbola xy=1. Let l be the line passing through P tangent to the hyperbola. Let X be the intersection of l and the x-axis, and Y be the intersection of l with the y-axis. Prove that P is the midpoint of XY.

The proof is very simple with the hyperbolic rotation. Consider when P = (1,1). The theorem obviously holds here, because of symmetry. But by applying a hyperbolic rotation, we can transform the point (1,1) into any other point on the hyperbola. Since ratios between line segments don’t change with a hyperbolic rotation, P is always the midpoint, and we are done.

Calculus magic

You have probably seen some version of this curve at some time or another:

The blue lines are drawn by putting n evenly spaced points in the interval [0,1] for both the horizontal and vertical axis and connecting them.

As n approaches infinity, the question is, what is the area occupied by the blue lines? The area is clearly finite since the entire shape is bounded by a 1×1 square, but how much of that square is occupied?

Intuitively it might seem that the blue curve is a circle, however that intuition is wrong. In the above diagram, the red curve is the actual circle, and clearly the blue curve is outside the circle. But fortunately the area can be found with some calculus.

If we choose some point (a,0) on the x-axis, then obviously that point is connected to point (0,1-a) on the y-axis. The slope of this line is \frac{a-1}{a} and the equation of this line is y=\frac{a-1}{a}x+1-a. More conveniently, we can this expression as g(a,x), intuitively the line formed when we choose a as our x-axis point.

Let f(x) be the bounding curve for the blue lines. To find f(x), we want to choose the value a, given x, so that g(a,x) is maximized. To do this, we take the partial derivative \frac{\partial y}{\partial a}:

\frac{\partial y}{\partial a} = x(\frac{a-a+1}{a^2})-1=\frac{x}{a^2}-1

The optimal value of a is the one for which \frac{\partial y}{\partial a}=0, so solving for a we get a=\sqrt{x}. Then we have

f(x) = g(\sqrt{x},x) = x \frac{\sqrt{x}-1}{\sqrt{x}}+1-\sqrt{x}

f(x)= 1+x-2\sqrt{x}

Integrating f(x) from 0 to 1 gives us the answer:

\displaystyle \int_0^1 (1+x-2\sqrt{x}) dx = \frac{1}{6}

One year of math blogging

One year ago on February 11, 2010, I created this blog. In one year, this blog has had:

  • 68 posts
  • 741 spam comments
  • 111 actual comments
  • 30,000 hits
A few months ago I installed the live traffic feed (visible on the right of the page), and for about two weeks afterwards I collected different countries that visit the blog (inspired by a post by Brian Bi) and I got 110 of them before I got bored:
Algeria
Argentina
Armenia
Australia
Austria
Azerbaijan
Bahrain
Bangladesh
Belarus
Belgium
Belize
Bolivia
Bosnia and Herzegovina
Botswana
Brazil
Brunei
Bulgaria
Cambodia
Canada
Chile
China
Columbia
Costa Rica
Croatia
Cyprus
Czech Republic
Denmark
Dominican Republic
El Salvador
Eritrea
Estonia
Ethiopia
Fiji
Finland
France
Georgia
Germany
Ghana
Greece
Guadeloupe
Guatemala
Hong Kong
Hungary
Iceland
India
Iran
Ireland
Israel
Italy
Jamaica
Japan
Kazakhstan
Kenya
Kuwait
Latvia
Lebanon
Lithuania
Luxembourg
Macedonia
Malawi
Malaysia
Malta
Martinique
Mauritius
Moldova
Mongolia
Montenegro
Morocco
Namibia
Nepal
Netherlands
New Zealand
Nigeria
Norway
Pakistan
Peru
Philippines
Poland
Portugal
Puerto Rico
Qatar
Romania
Russia
Saudi Arabia
Serbia
Singapore
Slovakia
Slovenia
South Africa
South Korea
Spain
Sri Lanka
Sudan
Sweden
Switzerland
Syria
Taiwan
Tajikstan
Thailand
Trinidad and Tobago
Turkey
U.K
U.S.A
US Virgin Islands
Uganda
Ukraine
United Arab Emirates
Venezuela
Vietnam
Zimbabwe

Obviously there is some geographical diversity among visitors.

I’m not much of a statistics person, but I like looking at a few graphs of pageviews over time:

Apparently there’s a slight decrease of pageviews as I write less the past few months, but I seem to get around 3000 to 4000 hits a month. Yay.

CMOQR 2011

Here I’m going to go over some of my solutions to the CMOQR (Canadian Math Olympiad Qualifying Repechage) — the qualifying contest for the CMO. Of the 8 questions, I managed to solve the first six but I didn’t manage to get the last two. My solutions here are going to be rather concise.

Problem 1

We know angle BOC so we know angle BAC. Use the cosine law on BOC to get BC=\sqrt{21}. Next use the cosine law again on BAC, but set x = AB and x+1 = AC. Solving for x, we get x=4.

Problem 2

No two of the sums are equal. Therefore no two of a,b,c,d,e are equal, so a<b<c<d<e. (letting abc mean a+b+c to avoid too many plus symbols) in set {a,b,c,d}, we have abc<abd<acd<bcd and similarly bcd<bce<bde<cde, therefore abc<abd<acd<bcd<bce<bde<cde. But we don’t have abe, ace, ade yet so abc<abd<abe<ace<ade<bde<cde.

In either case, abc is the smallest, abd is the second smallest, etc. Then abc=0, abd+3, bde=14, and cde=19. Thus we know d=c+3, b=c-5, e=a+11, so we have {a,b,c,d,e} = {a,c-5,c,c+3,a+11}.

As abc=0, we write everything in terms of c: a=5-2c and e=16-2c. Now we have {5-2c,c-5,c,c+3,16-c}. By substitution, acd=8 and bce=11. Since acd=8, abe=4 (not by deduction, rather it’s the only choice).

From a+b+e=4, we can solve for c and get c=4. It follows that the five numbers are {-3.-1,4,7,8}.

Problem 3

Adding the two equations and factoring gives (x+y+3)(x+y)=18. Solving the quadratic for x+y, we have x+y = -6 or x+y=3. Suppose x+y=-6: substituting back into the original two equations gives x=y=-3. Suppose that x+y=3. Substituting back gives x=0, y=3 or x=3,y=0.

Problem 4

Alphonse can always win. It turns out that he has a ‘strategy stealing’ strategy: first split into 2^{2011} and 5^{2011}. Beryl has to make some move now affecting one of the two piles (never both), and Alphonse can simply make the symmetrical move for the other pile. Obviously Beryl runs out of moves first.

Problem 5

It suffices to prove that for any 6 vertices of a 11-gon, there exists at least one pair of congruent triangles (either there are 6 black vertices, or there are 6 gold vertices). Enumerating all possible congruent triangles in a 11-gon is the same as enumerating all sets of integers adding to 11 — that is, {1,1,9}, {2,2,7} and so on. There are 10 such sets, so any 11 triangles must contain a pair of congruent ones.

Given 6 vertices we can form \binom{6}{3} = 20 triangles, so one pair must be congruent.

Problem 6

Let us write b for angle FBE and a for angle EBD. Obviously triangles ABF and EBF are congruent, so b = \frac{90-a}{2}. We want to prove that 30<a<45 or 22.5<b<30. To prove this we show that for a=30, b=30 then x>y, and then for a=45, b=22.5 then x<y, because then the value for which x=y must exist in that range.

The first case is simple, as if a=b=30 then we have 3 congruent triangles, and x=2y. The second case, EB=ED and (assuming the radius is 1), the area of BED is \frac{1}{2}. The area in the circle is \frac{ \pi}{8} so y = \frac{1}{2} - \frac{\pi}{8}. On the other hand x is twice of FBE minus \frac{\pi}{8} and using some trigonometry we get x = \tan 22.5 - \frac{\pi}{8}. To prove x<y for this case, it is sufficient to prove \tan 22.5 < \frac{1}{2}, which can be done using half angle formulas.

Is 2011 a special number?

Today is the first day of the year 2011. 2011 is a prime number. Not only that, but according to numerous math bloggers and twitterers on the internet, 2011 is the sum of 11 consecutive primes — that is, 2011 = 157 + 163 + 167 + 173 + 179 + 181 + 191 + 193 + 197 + 199 + 211. Furthermore (as I already said), 2011 is prime.

Naturally I wonder, how rare are these numbers — numbers that are prime but also a sum of a bunch of consecutive primes? This seems like a problem easily solved with some programming.

Let us write P(n,k) as the number of primes less than or equal to n that can be written as a sum of at least k consecutive primes. How big is P(2011,k) compared to \pi(2011) = 305, the number of primes less than or equal 2011?

My method for computing P(n,k) is pretty simple. First we start with a list of prime numbers, then write the cumulative sums for the prime numbers (these images were taken with my laptop camera off a whiteboard):

Next take every pair from the bottom list, and find their differences:

Because of the way I arranged the numbers, we can see that the bottom diagonal are all the numbers that can be written as a sum of 1 prime (obviously, the prime numbers), then the next row are all numbers that can be written as a sum of 2 primes, and so on. If we want to compute P(n,k) we simply list enough prime numbers to complete this table, take everything above a diagonal, and filter out all the duplicates.

Here’s my hopefully correct implementation:

import java.util.*;
import java.lang.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int LIM = 2011;
		int NCONSEC = 3;
		boolean[] sieve = new boolean[LIM+1];
		Arrays.fill(sieve, true);
		for(int i=2; i<=LIM; i++){
			if(!sieve[i]) continue;
			for(int j=2; j*i<=LIM; j++)
				sieve[i*j] = false;
		}

		List<Integer> primes = new ArrayList<Integer>();
		for(int i=2; i<=LIM; i++)
			if(sieve[i]) primes.add(i);

		List<Integer> cuml = new ArrayList<Integer>();
		cuml.add(0);
		int cum = 0;
		for(int p : primes){
			cum += p;
			cuml.add(cum);
		}

		Set<Integer> consums = new TreeSet<Integer>();
		for(int i=1; i<cuml.size(); i++){
			for(int j=0; j<=i-NCONSEC; j++)
				consums.add(cuml.get(i) - cuml.get(j));
		}

		int p = 0;
		for(int i : consums){
			if(i > LIM) break;
			if(!sieve[i]) continue;
			//System.out.println(i);
			p++;
		}

		System.out.println(p);
	}
}

It turns out that P(2011,3) = 147 and since there are 305 primes less or equal to 2011, roughly half of all primes under 2011 can be written as a sum of at least 3 consecutive primes. Hardly a special number at all! Even if we insist on a list of 11 consecutive primes, there are still 56 primes less than or equal to 2011 that can be written as a sum of 11 consecutive primes, about 1 in every 5 primes.

Happy New Year!

Solving Mathematical Problems (TOT 2010 Senior, P2)

Often, when looking through solutions of difficult olympiad problems, one would wonder, how are you supposed to come up with something like that? The steps are numerous and each one seems to be the work of a wizard…

One book that I like is Solving Mathematical Problems – A Personal Perspective by Terrence Tao. It’s a problem book, but one that’s slightly different from the others. Instead of merely giving a solution to its problems, it gives some insight on the mathematician’s thoughts as he solves the olympiad problem, such that the steps seem reasonable and logical

Here I’m going to attempt dissecting a recent contest problem I encountered (from the Tournament of Towns contest a few weeks ago) in the style of Tao.

The Problem

On a circular track, 2n cyclists start in the same direction at the same time, all at different but constant speeds. No three cyclists meet at the same time. If two cyclists are at the same position on the track, we say they meet. Prove that by the time every pair of cyclists have met at least once, each cyclist has had at least n^2 meetings.

The problem seems confusing, with so much seemingly unrelated information. We can always start by drawing a picture:

This doesn’t seem to help that much. A circle suggests that the formula for the circumference – C = \pi d might come into play, but looking at the rest of the problem, this seems unlikely, because the problem (especially the result we try to prove) is combinatorial, not geometric.

Let’s go back and look at what we’re given. First, all of the cyclists have constant velocity. So we can write the constant velocities of each of the 2n cyclists as v_1, v_2, \cdots, v_{2n}. We are also given that all of the velocities are different. Then why not simplify things for ourselves by ordering the cyclists in order of increasing velocity, that is, v_1 < v_2 < \cdots < v_{2n}? At the same time, we’ll label the cyclists according to their velocities, so we have C_1, C_2, \cdots, C_{2n}.

What else are we given? The number of cyclists is even, and no three cyclists meet at the same time. As there doesn’t seem to be much we can do to make use of these conditions, we can leave them aside for now.

Now if the length of the track is d, then each cyclist goes around the track every \frac{d}{v} units of time. The event only really ends when every pair of cyclists have met at least once – when does this happen? If we look at any two cyclists – C_i and C_j with C_j being the faster cyclist – the two have a velocity difference of v_j - v_i. Therefore cyclists C_i and C_j will meet every \frac{d}{v_j-v_i} units of time.

But it isn’t over until this happens for every pair of cyclists – \frac{d}{v_j-v_i} might be very large; in other words v_j - v_i could be very small. Since we ordered v_1, v_2, \cdots, v_{2n} in increasing velocity, the smallest value for v_j-v_i should be between two adjacent cyclists. If we let ube the smallest v_j - v_i, then

u = \mathrm{min} \{ v_2-v_1, v_3-v_2, \cdots, v_{2n} - v_{2n-1} \}

Furthermore, we can now say that the event ends at time \frac{d}{u} (from the start).

It seems that we are getting somewhere. But we haven’t really touched the point we’re trying to prove, that each cyclist has had n^2 meetings at this point. Let’s look at pairs of adjacent cyclists. If C_i and C_j are adjacent, then we know by definition that they must meet at least once in the time \frac{d}{u}.

But what about non-adjacent cyclists? If C_i and C_j are separated by exactly one cyclist, C_m, then v_m - v_i \geq u and v_j - v_m \geq u. Adding the two together gives v_j - v_i \geq 2u, so they meet at least once every \frac{d}{2u} units of time. Equivalently, they meet at least twice in the time \frac{d}{u}.

It follows that any pair of cyclists C_i and C_j meet at least every \frac{d}{u(j-i)} units of time, so they meet at least u(j-i) times in the course of the event.

We’re on home stretch here. How can use this new information to show that every cyclist has had n^2 meetings? Let’s look at any arbitrary cyclist, C_i. In the event, he meets at least i-1 times with C_1, at least i-2 times with C_2, at least 2n-i times with C_{2n}, and so on.

So the total number of times he meets is

\frac{i(i-1) + (2n-i)(2n-i+1)}{2}

All we have to do now is simplify:

\frac{i^2 - i + 4n^2 - 2ni + 2n - 2ni + i^2 - i}{2} \\= i^2 - i + 2n^2 - 2ni + n \\ = n^2 + (n-i)^2 + n - i \\ = n^2 + (n-i)(n-i+1) \geq n^2

since n-i and n-i+1 are consecutive integers and their product must be positive. This concludes the proof.

AHSMC 2010 Part I

The first math contest of this year! The AHSMC, has 16 multiple choice problems. 20 free marks, then 5 marks for every correct answer, 2 marks for every blank answer, and 0 for every wrong answer, so possible scores range from 20 to 100. The contest is written in 80 minutes, without a calculator.

The answers I got were: bacb bedd ccbe acbe. I’ll post my solutions here.

Problem 1

The number of positive integers n such that 4n has 2 digits is

(a) 21; (b) 22; (c) 23; (d) 24; (e) 25

As 4n is between 10 and 99, 3 \leq n \leq 24, giving 22 values. The answer is (b).

Problem 2

A 4×6 plot of land is divided into 1×1 lots by fences parallel to the edges (with fences along the edges too). The total length of the fences is

(a) 58; (b) 62; (c) 68; (d) 72; (e) 96

Count the vertical fences separately from the horizontal fences. So let’s suppose the grid is 4 columns and 6 rows, then we have 5 vertical fences and 7 horizontal fences; each vertical fence is 6 units long and each horizontal fence 4 units long.

Therefore the total length is 5 \times 6 + 7 \times 4 or 58. The answer is (a).

Problem 3

The GCD of two positive numbers is 1, and the LCM is 10. If neither of them are 10, their sum is

(a) 3; (b) 6; (c) 7; (d) 11; (e) none of these

Obviously the numbers are 2 and 5, as no other two coprime numbers both divide into 10. So their sum is 7. The answer is (c).

Problem 4

How many non-negative solutions (x,y) are there to the equation 3x+2y=27?

(a) 4; (b) 5; (c) 8; (d) 9; (e) 10

Solving for x, we get x = \frac{27-2y}{3} or x = 9 - \frac{2y}{3} . So in order for x to be non-negative, both 3 | 2y and \frac{2y}{3} \leq 9, so then y \leq 13. Of the numbers y between 0 and 13 inclusive, 5 of them are divisible by 3. The answer is (b).

Problem 5

The sequence 1,2,3,4,6,7,8,9,… is obtained by deleting multiples of 5 from the positive integers. What is the 2010th term?

(a) 2511; (b) 2512; (c) 2513; (d) 2514; (e) none of these

Notice that the 4th term is 4, the 5th term is 9, the 12th term is 14, and so on. So the pattern is that the 4n \mathrm{th} term is 5n-1.

Therefore term 2008 would be 5(502) - 1 = 2509; then term 2009 is 2511 (skipping 2510) and term 2010 is 2512. The answer is (b).

Problem 6

5 people in a building are on floors 1, 2, 3, 21, and 40. In order to minimize their total travel distance, what floor should they get together on?

(a) 18; (b) 19; (c) 20; (d) 21; (e) none of these

Suppose we choose floor 19. Then the total distance is 18+17+16+2+21 or 74. If we choose 17, the total distance is 17+16+15+3+22 or 73, which is smaller.

In fact we can repeat this several times: at floor 3, the total is 2+1+0+18+37 or only 58 floors in total. The answer is (e).

Problem 7

9 holes are arranged in a 3×3 configuration. Two pigeons each choose a hole at random (possible the same one). The probability that they choose two holes on the opposite side of an interior wall is

(a) \frac{1}{18}; (b) \frac{1}{9}; (c) \frac{4}{27}; (d) \frac{8}{27}; (e) \frac{1}{3}

Let the first pigeon choose a random hole. Then we split the problem into 3 cases:

  • If it’s in one of the 4 corners, then the next pigeon has a \frac{2}{9} chance of landing in the correct spot, so the probability here is \frac{4}{9} \times \frac{2}{9} .
  • If it’s in one of the 4 edges, then the next pigeon has a \frac{3}{9} chance of landing in the correct spot. This is a probability of \frac{4}{9} \times \frac{3}{9} .
  • If it’s in the center hole, then the next pigeon may land in 4 possible places, so the probability here is \frac{1}{9} \times \frac{4}{9} .

The total is \frac{4}{9} \times \frac{2}{9} + \frac{4}{9} \times \frac{3}{9} + \frac{1}{9} \times \frac{4}{9} which is equal to \frac{8}{27} . The answer is (d).

Problem 8

The set of real x where \frac{1}{x} \leq -3 \leq x is:

(a) \{x \leq - \frac{1}{3}\}; (b) \{-3 \leq x \leq - \frac{1}{3}\}; (c) \{ -3 \leq x < 0 \}; (d) \{ - \frac{1}{3} \leq x < 0 \}; (e) none of these

I solved this graphically:

The answer is (d).

Problem 9

In quadrilateral ABCD, AB || DC, DC = 2AB, \angle ADC = 30^\circ, BCD = 50^\circ. M is the midpoint of CD. The measure of \angle AMB is

(a) 80; (b) 90; (c) 100; (d) 110; (e) 120

Because DC || AB and DM = AB = MC, both ABMD and ABCM are parallelograms. Opposite angles in parallelograms are equal, so \angle MAB = 50^\circ, \angle MBA = 30^\circ. Thus \angle AMB = 100^\circ. The answer is (c).

Problem 10

We construct isosceles but non-equilateral triangles with integer side lengths between 1 and 9 inclusive. The number of such non-congruent triangles is

(a) 16; (b) 36; (c) 52; (d) 61; (e) none of these

Let the sides be a, b, c with a \geq b \geq c. There are 2 cases, one where a=b and the other when b=c.

First, the case a=b. If c=1, a can be from 2 to 9; if c=2 then a can be from 3 to 9, and so on. So the possibilities are 8+7+6+…+1 = 36.

Next, the case b=c. We have a > 2b so for a=9 we have b = 1, 2, 3, 4, and if a=8 then b = 1, 2, 3, and so on. Then the possibilities are 4+3+3+2+2+1+1 or 16.

The combined possibilities are 36+16 = 52. The answer is (c).

Problem 11

Which of the following is the largest?

(a) 2^{2^{2^{2^3}}} ; (b) 2^{2^{2^{3^2}}} ; (c) 2^{2^{3^{2^2}}} ; (d) 2^{3^{2^{2^2}}} ; (e) 3^{2^{2^{2^2}}}

Immediately we know that B>A because 3^2 > 2^3. Next, B>C because 512 > 81. Comparing B and D, we compare 2^{512} with 3^{16}. Obviously B is bigger.

Finally we compare B with E. B=2^{2^{512}} and E = 3^{2^{16}}. But B can be written as 4^{2^{511}} which is obviously bigger. The answer is (b).

Problem 12

A gold number is one expressible in the form ab + a + b for positive integers a and b. The number of gold numbers between 1 and 20 inclusive is

(a) 8; (b) 9; (c) 10; (d) 11; (e) 12

Write ab + a + b as a(b+1) + b. Take this modulo b+1, so n \equiv b \mod b+1. Then n+1 \equiv 0 \mod b+1 or b+1 | n+1, with b+1 > 1. Now if n+1 is composite this is possible, but if n+1 is prime then this is impossible (if b=n then a=0, a contradiction). Therefore a gold number is any number that’s not one less than a prime.

Below 20, the primes are 2, 3, 5, 7, 11, 13, 17, 19, so 8 numbers between 1 and 20 are not gold numbers. Then 12 are gold numbers. The answer is (e).

Problem 13

In tetrahedron ABCD, edges DA, DB, DC are perpendicular. If DA=1, DB=DC=2, then the radius of a sphere passing through A, B, C, D is:

(a) \frac{3}{2} ; (b) \frac{\sqrt{5}+1}{2} ; (c) \sqrt{3}; (d) \sqrt{2} +\frac{1}{2}; (e) none of these

Put the tetrahedron on a 3D cartesian grid with D being at (0,0,0), A at (1,0,0), B at (0,2,0), and C at (0,0,2). The equation of a sphere is (x-a)^2 + (y-b)^2 + (z-c)^2 = r^2, and since we know four points on the sphere, we can get four equations:

a^2 + b^2 + c^2 = r^2

(1-a)^2 + b^2 + c^2 = r^2

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

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

Solving for a, b, c, we get a = \frac{1}{2}, b = 1, c = 1. So the radius, or distance from origin is \sqrt{(\frac{1}{2})^2 + 1^2 + 1^2} or \frac{3}{2}. The answer is (a).

Problem 14

Let f(x) = x^2, g(x) = x^4. We apply f and g alternatively: f(x), g(f(x)), f(g(f(x))), etc. When we apply f 50 times and g 49 times, the answer is x^n where n is

(a) 148; (b) 296; (c) 2^{148}; (d) 2^{296}; (e) none of these

Rather than looking at the numbers themselves, we look at the exponents. Then f(x) multiplies the exponent by 2 and g(x) multiplies the exponent by 4. Applying f 50 times and g 49 times gives an exponent of 2^{50} \cdot 4^{49} or 2^{148}. The answer is (c).

Problem 15

Triangle ABC has area 1. X and Y are on AB such that XY = 2AX, and Z is a point on AC such that XZ || YC and YZ || BC. The area of XYZ is

(a) \frac{1}{27}; (b) \frac{2}{27}; (c) \frac{1}{9}; (d) \frac{2}{9}; (e) \frac{1}{3}

As XZ || YC, it follows that triangles AXZ and AYC are similar, and AY : AX = 3:1 so AC:AZ = 3:1 and AB:AY = 3:1.

The area of ABC is 1, so AYC is \frac{1}{3} and AYZ is \frac{1}{9}, and XYC is \frac{2}{27}. The answer is (b).

Problem 16

The number of integers n for which 2n+1 | n^3 -3n + 2 is

(a) 3; (b) 4; (c) 5; (d) 6; (e) 8

Notice the left side is always odd, and the right side is always even. Therefore, it is equivalent to count solutions to 2n+1 | 8(n^3 - 3n + 2).

Now 8(n^2 - 3n + 2) = 8 n^3 - 24n + 16 and by long division we have 2n+1 | (2n+1) (4n^2 - 2n + 11) + 27, or 2n + 1 | 27.

27 has 4 positive factors (1, 3, 9, 27) and 4 negative factors, all odd. Thus there are 8 solutions. The answer is (e).

Notes on Mercator’s Projection

The following work is my math essay assignment (an essay on any topic related to the Math 30 curriculum). I found it interesting enough that I’ll post it here on my math blog. Yay.

Introduction

How do you make a world map? We find world maps everywhere — but the making of world maps is more complicated than most people realize. The earth is round, and a map is flat. How should one represent the surface of the earth, a sphere, on a flat sheet of paper?

The problem of displaying the surface of a sphere on a map has concerned cartographers, or map makers, for centuries. Over the years, cartographers have come up with a multitude of map projections, or systematic methods of transferring the surface of the earth onto flat paper.

There are many types of map projections, but one of the most common types is the cylindrical projection. Imagine a semi-transparent, hollow globe with a light inside of it. Now wrap a piece of blank map paper around it, like a cylinder:

Let the earth be represented as a unit sphere. The longitude (east-west location) shall be denoted as \lambda, and the latitude (north-south location) as \theta. A is the center of the earth, and B a point on the equator.

Now a light source is placed at point A; a point D on the surface of the globe will be projected in a straight line to point C on the cylinder such that points A, D, and C are collinear. Using some trigonometry, we have \tan \theta = \frac{BC}{AB}; since AB=1, the length of BC is \tan \theta.

After repeating this procedure for every point on the sphere, the cylinder is unrolled into a flat sheet. The result is the following map:

Here, if a point on the earth is known (we know its latitude and longitude), we know its position on the map. The position coordinates of the map, (x,y) can be described in terms of \lambda and \theta in the following equations:

x = \lambda

y = \tan \theta

This projection has several major drawbacks: most notably, as the latitude \theta increases toward 90^\circ, the slope of \tan(\theta) becomes increasingly steep, and the y-coordinates of the point of the map increases towards infinity. At high latitudes, the map is very distorted.

The map is not equal-area — in an equal-area map, shapes of equal area on the sphere have equal area on the projection. Looking at the map we created, this is clearly not the case. Neither is the map conformal, or shape preserving. In a conformal map, the angle between any two lines must be the same as their counterparts on the map.

Mercator’s Projection

One of the most well known cylindrical map projections is Mercator’s projection. Invented by Belgian cartographer Gerardus Mercator in 1569, Mercator addresses some of the problems in older cylindrical projections. Unlike our projection, Mercator’s projection is conformal, and it has been used for navigation for centuries:

However, the equations for Mercator’s projection are rather complicated. The position on Mercator’s projection, when given the latitude and longitude, is:

x = \lambda

y = \ln ( \sec \theta + \tan \theta )

This is a strange and seemingly random formula. But when we use this formula, we get a conformal map. How does this work?

Deriving Mercator’s Projection

Before deriving the formula for Mercator’s Projection, we take a step back and ask ourselves — what was the projection for in the first place?

Unlike most maps today which are used to decorate walls, Mercator’s map was more than that — it was used for nautical navigation. Suppose you were to travel by ship from Vancouver to Honolulu, equipped with nothing more than a compass. Which direction should you travel?

Now if you have a copy of Mercator’s map, this becomes simple. You draw a straight line from Vancouver to Honolulu, and with a protractor you find that the direction is 40^\circ south to the parallel. With a compass, it would be easy for you to maintain this constant heading for the entire duration of the trip.

(Footnote — The straight line on Mercator’s map is not straight on the Earth — it is actually a curved line, called a rhumb line. That is, after taking an initial bearing, one proceeds along the same bearing (relative to the north pole) for the duration of the trip. In the example, you would have to adjust your heading intermittently so that you are always heading at the direction 40^\circ south to the parallel.)

This technique is possible because it relies on one crucial property of Mercator’s map: that it is conformal. It would fail if we tried the same technique on the cylindrical projection given in the introduction.

However, notice that on Mercator’s map, all parallels have the same length: a parallel is simply a line across the width of the entire map. But on Earth, a sphere, parallels are longer when they are closer to the equator and shorter when near the poles:

Let the Earth be a unit sphere with center A. D is a point on the surface of the Earth and B is its corresponding point on the equator. Let C be a point such that CD is parallel to AB and AC is perpendicular to AB. As AB = 1, the circumference of the Earth at the equator is 2 \pi. But the circumference at latitude \theta is only 2\pi \cos \theta.

It is easy to see why: as AB || CD in the diagram, it follows that angles \angle DAB and \angle ADC are equal. Next, \cos \angle ADC = \frac{CD}{AD} = \frac{CD}{1} = CD, therefore CD = \cos \theta. The result follows.

On the map, the length of the equator and the parallel at latitude \theta are equal. But on Earth, the parallel at latitude \theta is smaller than the equator by a factor of \cos \theta; in the projection any line at latitude \theta ends up being stretched horizontally by a factor of \frac{1}{\cos \theta} or \sec \theta.

Finally, in order to satisfy the property of conformality, any part of the map stretched horizontally by some factor, say k, must be stretched vertically by the same factor k. Doing so preserves the angles of that part of the map:

Imagine a very small piece of land at latitude \theta. When it is represented on the map, it is stretched horizontally by \sec \theta. Hence to preserve conformity, it must also be stretched vertically by \sec \theta.

But this can only work if the piece of land has no area. But as all pieces of land, no matter how small, has some area, the latitude of the piece of land is not \theta, but goes from \theta to \theta + \Delta \theta for some small number \Delta \theta. Similarly, the space this piece of land occupies on the map is not just y, but goes from y + \Delta y for some small number \Delta y. Now as \Delta \theta approaches 0, the ratio of \Delta y to \Delta \theta approaches \sec \theta:

\lim_{\Delta \theta \to 0} \frac{\Delta y}{\Delta \theta} = \sec \theta

Or equivalently,

\frac{dy}{d \theta} = \sec \theta

Solving for dy and integrating both sides gives:

\begin{array}{rl}y & = \int \sec \theta \, d \theta \\ & = \int \left( \sec \theta \cdot \frac{\sec \theta + \tan \theta}{\sec \theta + \tan \theta} \right) d \theta \\ & = \int \frac{\sec^2 \theta + \sec \theta \tan \theta}{\sec \theta + \tan \theta} \, d \theta\end{array}

If we let u be the denominator, u = \sec \theta + \tan \theta, it turns out that the numerator is the derivative of u, or du = \sec^2 \theta + \sec \theta \tan \theta. Thus we can substitute u into the integral:

\begin{array}{rl} y & = \int \frac{du}{u} \\ & = \ln |u| + C \\ & = \ln | \sec \theta + \tan \theta | + C \end{array}

We defined the map so that the equator lies on the x-axis, therefore when \theta = 0, y=0. Substituting and solving for C, we find that C=0. Also, since \sec \theta + \tan \theta > 0 for -\frac{\pi}{2} < \theta < \frac{\pi}{2}, we can remove the absolute value brackets. Therefore,

y = \ln ( \sec \theta + \tan \theta )

This is what is desired.

An Alternative Map Projection

Mercator’s Projection is merely a conformal map, not a perfect map. It has several drawbacks — the scale varies greatly from place to place: as the latitude increases, the map gets stretched more and more. This severely distorts larger figures, especially areas near the poles. At a latitude greater than about 70^\circ, the map is practically unusable.

The Gall-Peters Projection is an alternative cylindrical projection:

When a map is used in navigation, it is important that angles are preserved in the map. But when a map is used to present statistical data, it’s often more important to preserve areas in the map: otherwise one may be deceived into thinking one country is bigger than another when they are actually the same size.

The Gall-Peters projection does this, trading conformity for equal-area — two countries of the same area will have the same area on the map, no matter where they are on the map. This map projection is produced by the following equations:

x = \lambda \cos 45^\circ = \frac{\lambda}{\sqrt{2}}

y = \frac{\sin \theta}{\cos 45^\circ} = \sqrt{2} \sin \theta

A discussion on why this set of equations produces an equal-area map is beyond the scope of this essay.

Conclusion

It is a tricky matter to accurately depict the surface of the earth on a flat sheet of paper. The method of cylindrical projection produces several considerably different maps.

The first map we considered uses only simple trigonometry, but the map produced is not very useful. The second map we investigate, Mercator’s Projection, preserves angles on the map. The last map we consider, the Gall-Peters projection, preserves areas on the map.

Each of these map projections are both similar and very different. They are similar in that they are all produced in some way by wrapping a cylinder around a spherical Earth. But the mathematics needed to produce them differ.

The hockey stick theorem: an animated proof

An interesting theorem related to Pascal’s triangle is the hockey stick theorem or the christmas stocking theorem. This theorem states that the sum of a diagonal in Pascal’s triangle is the element perpendicularly under it (image from Wolfram Mathworld):

So here the sum of the blue numbers , 1+4+10+20+35+56, is equal to the red number, 126. It is easy to see why it’s called the hockey stick theorem – the shape looks like a hockey stick!

An alternative, algebraic formulation of the hockey stick theorem is follows:

\displaystyle\sum_{i=0}^{k} \binom{n+1}{i} = \binom{n+k+1}{k}

But this works in two ways, considering the symmetry of Pascal’s triangle. The flipped version would be:

\displaystyle\sum_{i=0}^{k} \binom{n+1}{n} = \binom{n+k+1}{n+1}

Using Pascal’s identity, it is fairly trivial to prove either identity by induction. Instead I present an intuitive, animated version of the proof: