Probabilities of a slightly altered dice

In art class a few months ago, I made a dice out of clay. This dice isn’t quite your typical dice. Its structure is tampered with ever so slightly, so that just \frac{1}{64} of the material is removed.

Let us model this crude, imperfect dice as a hypothetical, perfect dice. Suppose this dice is represented as a cube, composed of 64 smaller ‘cubelets’ (imagine the cubelets as 1x1x1 and the dice as 4x4x4). Furthermore, we imagine four ‘layers’ of cubelets, such that each layer is a 4×4 square.

In this dice, we remove one of the 16 cubelets from the second layer, like this:

(keep in mind that this is still a solid cube)

Assuming that the cube is made out of uniform density material (and that the missing cubelet has no mass), what is the probability of landing on each of the six sides when the cube is thrown?

A mathematical interpretation

I will solve a problem which may or may not be equivalent to throwing a dice. Instead of throwing the dice, we place the dice on a table with a random orientation, and let go. We then observe which side the dice lands on.

This appears to be a legit and identical interpretation, but there is a flaw. With an uneven dice, it is not guaranteed that each orientation would appear with uniform likelihood. Nevertheless, for our purposes we ignore this and we assume that this is an identical problem.

Which side will it land on? The center of gravity of the dice must be directly on one of the six sides; this side is the side that the dice will fall onto.

Consider a sphere of some radius, centered at the cube’s center of gravity and entirely contained in the cube:

Lines are drawn from the center of gravity to the eight vertices of the cube, essentially dividing the sphere into six pyramid-like parts.

The chance of landing on a side of the cube is proportional to the side’s surface area when ‘projected’ onto the surface of the sphere. This is because the side can be divided into infinitely many small ‘pyramids’, each one of which corresponds to the dice landing on that side when left to drop at that specific angle.

Such a portion of the surface area is called a solid angle, which is measured in steradians (sr). Whereas the entire circle is denoted as 2 \pi radians, the entire sphere is denoted by 4 \pi sr. Likewise, one hemisphere would be 2 \pi sr, and so on.

There is an efficient formula for calculating the solid angle of a tetrahedral projection onto a sphere, given by Oosterom and Strackee. If \vec{a}, \vec{b}, \vec{c} are vectors of three vertices of a tetrahedron (in relationship to the fourth), then the subtended solid angle is given by:

\tan(\frac{1}{2} \Omega) = \frac{|\vec{a} \vec{b} \vec{c}|}{abc + c(\vec{a} \cdot \vec{b}) + b(\vec{a} \cdot \vec{c}) + a(\vec{b} \cdot \vec{c})}

Here a, b, c are magnitudes of the vectors, the dot represents a dot product, and |\vec{a} \vec{b} \vec{c}| is the determinant of the scalar product of the vectors.

The magnitude of the 3-D euclidean distance:

a = \sqrt{a_x^2 + a_y^2 + a_z^2}

The dot product of two vectors is:

\vec{a} \cdot \vec{b} = a_x b_x + a_y b_y + a_z b_x

Finally,

|\vec{a} \vec{b} \vec{c}| = |a_x b_y c_z + b_x c_y a_z + c_x a_y b_z - a_x b_z c_y - b_x c_z a_y - c_x a_z b_y|

Calculating the probability

Let us position the cube on a 3D coordinate, such that the corners are the origin and (4,4,4). The empty cube is the cube with center (2.5,2.5,2.5).

To find the center of gravity, we just take the averages of the centroids of all the smaller cubes (the missing cube contributing 0 to the sum). This turns out to be (k,k,k) with k= \frac{251}{126} or about 1.9921.

We have k = \frac{251}{126}; now we let k' = 4-k. To facilitate vector manipulations, we will now transpose the cube such that the center of gravity is at (0,0,0):

Because of symmetry, it is obvious that three of the six sides should have one equal probability, and the other three sides to have a different, but again equal, probability. Thus it is not strictly necessary to go through the calculations for all six sides; we only need to do them for two of the sides.

A face forms a solid angle for a square pyramid, not a tetrahedron (for which we have a formula for). To solve this, we note that a square pyramid can be divided into two tetrahedrons, and the solid angle for it is simply the sum of solid angles for the two tetrahedrons.

Now by doing these calculations, we get a probability of 16.740% of landing on each of the three heavier sides, and 16.594% on each of the three lighter sides (sides closer to the missing cubelet).

By comparison, the probability of landing on any side on a fair dice is 16.667%. As only \frac{1}{64} of the dice’s mass is removed, the resulting difference is slightly less than 1%.

Point in a polygon

An important, yet basic problem in computational geometry is the following task: given a polygon (a sequence of points) and a point, determine if the point is inside, or outside the polygon.

To a human eye, this problem is trivial. After all, it seems obvious that point A is outside the polygon, whereas point B is inside it.

Computers, on the other hand, lack this simple intuition. It is not entirely obvious how to go about creating an algorithm that correctly determines this.

Triangles containing the origin

Let us first focus on an easier version of the problem. Instead of any arbitrary polygon, let our polygon be limited to three points, that is, a triangle. Instead of any point in space, let us determine if the triangle contains the origin.

We observe that we can draw a ray from our point outwards. Any direction will do. If the point is inside the triangle, then the ray will eventually hit a side of it.

On the other hand, if the point is outside the triangle, the ray may hit two sides of the triangle, or it may hit none. However, it will never hit exactly one side:

Aha; this is the approach. Now we can transpose our diagram to a Cartesian plane. For simplicity, let our ray be a line directly upwards from the origin, that is, the entire y-axis above the origin.

Our algorithm now takes the three line segments of the triangle, and counts how many of them intersect the y-axis above the origin.

There are three cases. In the first case, the triangle doesn’t intersect the y-intercept at all above the origin, thus the triangle doesn’t contain the origin:

In the second scenario, the triangle intersects the y-axis twice above the origin, in which case the triangle still does not contain the origin:

In the last case, the triangle intersects the y-axis once above the origin, in which case the origin is in the triangle:

So the algorithm is, for every line segment (pair of coordinates) in the triangle:

  1. Calculate the y-intercept, say, b
  2. If b<0 this line segment doesn’t cross the y-axis above the origin so throw it away. Otherwise, continue.
  3. Make sure that the line segment actually crosses the y-axis at all. Or, check that the two points are on opposite sides of the y-axis.

Here’s my implementation of the algorithm in C++:


// Slope of a line
double slope(double x1, double y1, double x2, double y2){
  return (y1-y2) / (x1-x2);
}

// Y intercept given slope and point
double yint(double px, double py, double m){
  return py - m*px;
}

// Determine if a line crosses the y axis
bool cyax(double ax, double bx){
  if(ax<0 && bx>0) return true;
  if(bx<0 && ax>0) return true;
  return false;
}

// Contains origin, or not?
// Input is (A_x, A_y, B_x, B_y, C_x, C_y).
bool cto(double ax, double ay, double bx, double by, double cx, double cy){

  // Find slopes
  double mAB = slope(ax,ay,bx,by);
  double mBC = slope(bx,by,cx,cy);
  double mAC = slope(ax,ay,cx,cy);

  // Find y intercepts
  double yAB = yint(ax,ay,mAB);
  double yBC = yint(bx,by,mBC);
  double yAC = yint(cx,cy,mAC);

  // How many times it crosses the y intercept above 0
  int c = 0;

  if(yAB>0 && cyax(ax,bx)) c++;
  if(yBC>0 && cyax(bx,cx)) c++;
  if(yAC>0 && cyax(ax,cx)) c++;

  return c==1;
}

Generalizing the algorithm

We can proceed to generalize the algorithm to not only triangles containing the origin. First, for the problem of determining if an arbitrary point is in a triangle, we can create a bijection:

Translate all the points so that the test point lies on the origin. The position of this point relative to the triangle is exactly the same, so we can proceed with the y-intercept algorithm.

For a polygon with more than 3 points, the same algorithm applies. Sort of. With more complicated polygons, we may encounter this edge case:

Here the ray crosses the polygon three times.

There’s an easy fix to this problem, however. It turns out that if the ray crosses the polygon an odd number of times, then the point is inside the polygon.

Project Euler 299: Three similar triangles

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

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

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

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

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

Initial observations

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

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

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

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

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

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

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

Incenter case

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

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

Line BD can be expressed by the equation

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

or in standard form,

dx + by - bd = 0 .

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

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

By substitution, we have

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

Simplifying:

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

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

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

Parallel case

Now we consider the case when AC || BD.

Let X be the circumcenter of \triangle DPB:

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

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

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

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

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

The line AC has an equation of

y=c-x .

By substitution into the circle equation:

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

Or,

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

Applying the quadratic formula and dividing by 2 gives

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

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

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

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

c^2 - 2f^2.

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

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

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

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

Writing the code

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

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

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

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

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

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

x = n^2 - m^2

y = 2mn

z = n^2 + m^2

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

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

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

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

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

x = n^2 - 2m^2

y = 2mn

z = n^2 + 2m^2

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

This is easy to implement in Java:


public class Main{
  final static long L = 100000000;

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

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

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

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

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

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.

The Proggit Bacon Challenge: a probabilistic and functional approach

A few days ago I saw an interesting programming challenge on Proggit (more commonly known as /r/programming, or the programming subreddit). The problem is found here.

This is how the problem goes:

You are given a rectangular grid, with houses scattered across it:

The objective is to place bacon dispensers (I’ll call them bacons from now on) at various places so the people in the houses can get the bacon.

I have no clue why they chose bacon, out of all objects to choose from. Alas, that is not the point.

So given a limited number of bacons, you must distribute them effectively among the houses by putting them on empty squares. In the example, you have three bacons to place.

For each house, the score is the distance to the nearest bacon (using the Manhattan, not Euclidean metric). Your total score is the sum of the scores for each house. Thus, you are trying to minimize your total score.

Optimal solutions

Here is the optimal solution for the problem:

If you add them up, you can see that the total score for this configuration is 10.

Question is, how do you arrive at this configuration?

It turns out that this isn’t as easy as it looks. This problem is NP-Hard, meaning there is no algorithm that can solve it both quickly and optimally. By “quickly”, it’s understood to mean polynomial or non-exponential complexity; if this is impossible then the best algorithm is not significantly better than just brute force.

In order to solve the problem in a reasonable amount of time, we have to trade optimality for speed and rely on less than optimal, probabilistic approaches.

Introducing the k-means algorithm

We will now transform the problem into a data clustering problem.

If we have k bacons to place, then we must find k distinct clusters. After this, we can place the bacons in the centroid of each cluster to achieve the optimal score. In other words, we are finding clusters such that the distance from a point to the center of a cluster is minimized.

The best known algorithm for this problem is Lloyd’s algorithm, more commonly referred to as the k-means algorithm. Let’s try an example to demonstrate this algorithm.

Suppose we want to find two clusters in these points:

We start by choosing two centers randomly from the sample space, let’s make them green and red:

We assign each point to its nearest center:

Then, we move each center to the centroid of its cluster:

Notice now how some of the points are closer to a different center than the center they’re assigned now. Indeed, they belong to a different cluster.

So we reassign the clusters:

Again we calculate the centroids:

We repeat these steps as many times as we need to, usually until the clusters do not change anymore. Depending on the data it may take more or less iterations, but it normally converges fairly quickly.

This method, unfortunately, does not always achieve an optimal result. Technically it always converges on a local optimum, which is not always the global optimum. The local optimum can be arbitrarily worse than the global optimum.

Take note of how the result of the algorithm depends entirely on the results of the random starting positions of the clusters.

If you’re very very lucky, they might as well end up at exactly the optimal locations.

If you’re really unlucky, however, they may end up all in a corner of the map; and the result configuration would be far from optimal. We might even end up with most of the clusters completely empty. The thing is that they’re assigned completely randomly.

We can do better than that.

Improving the k-means: introducing the k-means++ algorithm

The k-means++ algorithm addresses some of the problems with the k-means algorithm, by seeking better starting clusters. Its results are almost always better than the standard algorithm.

Let’s try this.

The first thing we do is put a cluster right on top of a random point:

For each point that doesn’t already have a cluster on it, calculate the distance to the nearest cluster (which is not always the same cluster):

Next we assign a probability to each of the points, proportional to the squares of the distances:

The next cluster is chosen with this weighted probability. We repeat this until we have all k clusters distributed on top of k different points.

Then, we proceed with the regular k-means algorithm.

The result of this way of choosing is that the starting clusters tend to be spread out more evenly; moreover there’s no empty clusters. Notice how a point twice as far from the nearest cluster is four times more likely to be chosen for the next cluster.

Although this drastically improves the k-means algorithm, it still does not guarantee an optimal configuration.

Repeated simulation

There is one more thing we can do to increase our score. Being a probabilistic algorithm, the results depend heavily on the random numbers generated. Using different random numbers would achieve better or worse results.

To get the better results, we can run the algorithm multiple times, each time with a different set of random numbers. As the number of iterations increase, the score will get closer and closer to the optimum.

Implementation in Haskell

It took me about two days to write a program for this task; I’ve submitted the program to the challenge. There the source code is available, as well as various benchmarks.

Looking through and running some of the other entries, it seems that my program beats most of them. One exception is the entry (entries) by idevelop, which produces considerably better scores than mine for the extremely large input sets. On the other hand, my program does better on most other inputs (medium and large) by repeating the simulation a few hundred times, (usually) arriving at the optimum 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.

Investigations on star polygons with a star polygon / stellar number generator

Note 9/3/2010: Redone all of the diagrams

If you are just looking for a download link to the program, here it is. To run, save as Stellar.jar (Java is required)

As school has been over for more than a week now, I’ve had time to (among other things) study geometry. I’m just spending an hour or two every day working through various exercises in Geometry Revisited.

This blog post is long overdue; it had been sitting in my drafts section with a few sentences written since the middle of April. Maybe it’s still useful now, maybe not. Anyways.

I myself am not in IB, because of my hatred of being forced to do copious and tedious amounts of homework. Many of my friends, however, take IB math. One famous project in IB math (not only in my school, but also in other schools) is a large project known as the math portfolio. From what I’ve heard, this consists of a dozen or so pages of writeup on some extended problem.

I first heard about the existence of such a project when a few of my friends asked me for help on it. The project was related to ‘stellar numbers’; a picture of the assignment can be found here. The problem itself seems rather trivial, thus I don’t feel it necessary to discuss it in this blog post.

My investigations here, although inspired by this assignment, is only marginally related to the assignment itself. The end product to be handed in for grades was supposed to include diagrams. However, it isn’t so easy to draw diagrams of stars (see above image) either by hand or on the computer. I saw many of my friends hastily put together their diagrams of stars using Powerpoint or MS Word, using the line and circle tools and a heck lot of copy-and-pasting. The result, unsurprisingly, is messy and inexact. One friend of mine wrote a computer program to output Latex code to draw the stars; the details of how this is done is something I consider more difficult and interesting than the project itself.

Keeping along with my theme of geometry this week, it is useful to figure out the geometry of star polygons before writing programs to generate them.

Some geometric constructions

Consider the five sider star (fig.1):

We can see that the five corners of the star, ABCDE, are the same distance from the center K of the star. This means the five points lie on a circle; furthermore the distances between the corners are the same.

A similar phenomenon occurs with the five points between the corners, FGHIJ. They, too, lie on a circle centered around K.

Let us call the radius of the larger circle r, and the radius of the smaller circle i. Any star can be built around the framework of two circles. For example, our five pointed star (fig.2):

There is, however, one more characteristic present in star polygons that we neglected in the above diagram. It is that we chose the values of r and i pretty much arbitrarily.

Notice that in (fig.1), the sides EF and GB are parallel. It can be shown geometrically that if parallel, EF and GB are also concurrent. In (fig.2), EF and GB are not parallel nor concurrent.

Although any values of i and r for i<r are enough to produce a star, it is necessary to further adjust the ratio between i and r in order to produce a correct star polygon.

Let us denote n to mean the number of points of a star, and d to denote the density of a star.

What do we mean by density? In order to define density, we will take a step back and take a look at alternative ways that star polygons can be constructed.

At present we are looking at star polygons as points on two distinct circles joined together with alternating line segments. Here is a completely different way of presenting it (fig.3):

Points ABCDE are spread equally on a circle. For the five points, every two points are connected by a line. We define density to be this number: the density for this star is 2.

It is possible, perhaps easier, to implement a drawing routine this way. However, by doing this we would have to erase the lines FGHIJ, which seems straightforward but is troublesome in implementation. We are going to stick to the two circles paradigm.

If d=1 , then our ‘star’ would be degenerate; it would merely be a n-sided polygon. On the other hand, we assume that the inner circle has positive radius, thus,

d < \frac{n}{2}

For any integer n with n \geq 3 , the maximum value of d is given by:

d \leq \lfloor \frac{n-1}{2} \rfloor

Next is finding a way to express the ratio between the radii in terms of n and d.

Here we combined the previous two diagrams, and added some new lines. Since our star contains so much symmetry, what follows can be extended to all corners of the star, and also to stars with different densities and number of corners.

Let us call the angle \angle EKA to be x, which is \frac{1}{n} of the circle, or \frac{2 \pi}{n} radians.

Let y be the angle such that

x:x+y = 1:d

.. whence here d=2 , therefore x=y=72^\circ .

As \triangle EKB is isosceles, \angle BEK = \angle EBK , and \angle BEK + \angle EBK + x + y = 180^\circ ; therefore

\angle BEK = \frac{1}{2}\left[ 180-(x+y) \right] = 90-\frac{1}{2}(x+y)

.. whence here \angle BEK = 18^\circ .

Next, \angle EKL = \frac{1}{2}x , in our case 36^\circ , thus the measure of \angle EFK can be found:

\angle EFK = 180 - \left[ 90-\frac{1}{2}(x+y) \right] - \frac{1}{2}x = 90 + \frac{1}{2}y

In our case \angle EFK = 126^\circ.

By the sine law in \triangle EKF,

\frac{r}{\sin (90 + \frac{1}{2}y)} = \frac{i}{\sin \left[90-\frac{1}{2}(x+y) \right]}

Or,

i = \frac{r \sin \left[90-\frac{1}{2}(x+y) \right]}{\sin (90 + \frac{1}{2}y)}

Simplifying, we get

i = \frac{r \cos \left[ \frac{1}{2}(x+y) \right]}{\cos (\frac{1}{2}y)}

We defined that x = \frac{2 \pi}{n} and that x+y = \frac{2 \pi d}{n} , thus we write y:

y=\frac{2 \pi (d-1)}{n}

And that brings us to the final formula:

i = \frac{r \cos (\frac{\pi d}{n})}{\cos \left[ \frac{\pi (d-1)}{n} \right]}

Evaluating it for our star, we find that if r=1, then d \approx 0.38197.

Implementation in Java

Now that we have the math done, it is a fairly easy programming exercise to implement this as a java application. Here’s what I came up with after ~2 hours of hacking in Netbeans (animated gif):

This may be useful to future people doing the same assignment (if it ever gets assigned again), or with modifications it may be useful for other purposes too.

To use it, adjust the settings, take a screenshot, crop it, and it may be necessary to further edit it in photoshop.

Without further ado, here’s the application as a jar file:

(broken link removed)

Or the source as a Netbeans project:

stellar-src.zip (37kb)

Do whatever you want with them, and have fun!

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.

Challenge of the Week 05/11/2010

Update (7/31/2010): This article has been rewritten, with several more elegant solutions added, rather than the coordinate solution presented originally.

This is the second time I’m attempting a Challenge of the Week problem, after solving this one and winning coupons for Baskin Robbins’ Ice Cream (which by the way I can’t use because I’m in Canada).

Well my solution here is pretty inelegant and is a sort of ‘coordinate bash’ geometric solution. Pretty sure a better solution exists, but this is the best I could do for now.

The problem is originally from here (although I expect it will be somewhere else by the end of this week).

Problem

In equilateral triangle \triangle ABC, M is a point on BC. Let N be the point not on BA such that \triangle BMN is equilateral. P, Q, and R are midpoints of AB, BN, and CM respectively. Prove that \triangle PQR is equilateral.

Solution by coordinate geometry

As with coordinate geometry, I put the figure on a cartesian grid with B as the origin.

Without losing generality, we can let BC be on the x-axis and C be (4,0). Also let M be (4x,0) for some value x between 0 and 1. So 4x is between 0 and 4 and is any point on BC.

Doing this doesn’t lose generality because any instance of this problem can be rotated and scaled so that B is the origin and C is (4,0).

I choose these values for the initial points in order to end up with easier to work with points for PQR.

Noting the coordinates of the points:

B = (0,0)

C = (4,0)

M = (4x,0)

Since we know B and C, we can calculate A and N:

A = (2,2 \sqrt{3})

N = (2x, -2x \sqrt{3})

It becomes easy to calculate P, Q, and R:

P = (1, \sqrt{3})

Q = (x, -x \sqrt{3})

R = (2x+2, 0)

We now calculate the distances of PQ, QR, and PR using the distance formula:

\begin{array}{rcl} PQ &=& \sqrt{(x-1)^2 + (x \sqrt{3} + \sqrt{3})^2} \\ &=& 2 \sqrt{x^2 + x + 1} \end{array}

\begin{array}{rcl} QR &=& \sqrt{(2x+2-x)^2 + (x \sqrt{3})^2} \\ &=& 2 \sqrt{x^2 + x + 1)} \end{array}

\begin{array}{rcl} PR &=& \sqrt{(2x+2-1)^2 + \sqrt{3}^2} \\ &=& 2 \sqrt{x^2 + x + 1)} \end{array}

We find that the three simplify to the same thing. That means PQ = QR = PR and \triangle PQR is equilateral.

Solution via trigonometry

Rather than a coordinate bash, we can use a similar trigonometry bash. We let a be the larger equilateral side (AB), and b be the smaller equilateral side (BN).

Using the law of cosines, with the fact that \cos 60^\circ = \frac{1}{2} and \cos 120^\circ = -\frac{1}{2}, we can get these equations:

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

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

PQ^2 = (\frac{a}{2})^2 + (\frac{b}{2})^2 + (\frac{a}{2})(\frac{b}{2})

If we just simplify these three expressions, we find that they are exactly the same:

PR^2 = QR^2 = PQ^2 = \frac{a^2+ab+b^2}{4}

which proves the result.

Solution via homothetic triangles

A more elegant and less ‘bashy’ solution exists via homothety.

We expand triangle PQR by a factor of 2 about the point B, giving the new triangle ANK. That is, BA is twice of BP, and BK is twice of BR, and so on.

It is sufficient to prove that \triangle ANK is equilateral, as it is homothetic to \triangle PQR.

Since BK = 2BR, it follows that BM=CK. It is obvious that \angle ABN = \angle ACK = 120^\circ, and also that AB = AC, thus triangles ABN and ACK are congruent. Thus, AN = AK.

As \angle BAC = 60^\circ, it is also true that \angle NAK = 60^\circ, thus proving triangle ANK to be equilateral by SAS.

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.