Introduction

Match-stick puzzles are one of the most popular mind benders around. Sure, you might say, but they are far from being the most interesting ones in light of their apparent simplicity. Indeed this is how a famous geometer by the name of T. R. Dawson felt around the end of the 1930's. This is why he sat down and, after defining the set of allowed manipulations, showed that, using an infinite supply of match-sticks, one can construct exactly those points that one can construct using a ruler and a compass. This is no small feat -- one can build great structures and extravagant cities with these points.
    To see this, simply look at the coordinates of these, so called, constructible points. Call the numbers representing them points constructible numbers. One can show these numbers form what is known in mathematics as a number field. This simply means that if we take two such numbers and we add, subtract, multiply or divide them, we get another constructible number. But this is not all constructible numbers allow us to do -- we can also take the square root of a constructible number and the result will, again, be a constructible number.
    In this page, we shall try to give an intuitive proof of the equivalence of the match-stick model and the straight-edge and compass model. We shall first set down the allowed manipulations with match-sticks. Next, the ruler and compass model will be briefly described and we shall establish exactly what needs to be proven. Finally, the proof will be presented using the interactive applet as a demonstration tool. The applet will also allow you to play with the match-stick model (you can find an applet simulating the ruler and compass model here).

Match-Stick Model

    Here we discuss the model as proposed by Dawson. Suppose we are given an infinite supply of match sticks of length one. We construct figures with the sticks according to the following rules:
  1. A stick may be laid to pass through a given point, or with one extremity at a given point.
  2. A stick may be laid to pass through two given points if the distance between them is equal to one, or with one extremity at one point and passing through the second if the two points are less than a unit apart. We do not, however, allow to put two sticks such that they overlap (intersect at more than one point). Note: This restriction is adopted to improve the elegance of the construction.
  3. If a point is close enough to a line (i.e. distance less than or equal to one), a stick may be laid with one extremity at a given point and its other extremity on a given line.
  4. Two sticks may be laid simultaneously to form an isosceles triangle, two of their extremities coinciding and the other two being at given points no more than two units apart.
    The constructed points are the extremities of the sticks already laid down. It should be noted that the first rule is not meant to allow one to put two sticks "end on" or to put a stick pointing at some remote (not close enough -- distance more than 1) point. Of course, the above rules are useless unless we have some points to start with. For that reason, we may assume that we are given two points which are strictly closer than one stick-length away. Note that if the two starting points are exactly at distance one from one another, the only type of construction allowed would be to put a stick through them and proceed building equilateral triangles in all directions. To give you a first taste of how this model works, try solving the follwoing exercise

Exercise. Given two points strictly less than one unit distance apart, construct a square such that one of its sides is the stick passing through the two starting points.

Use the applet to do this. If you are looking for a hint, here is the solution without lables. And this is the complete solution.

Straight-Edge and Compass Model

    This is also known as the "Ruler and Compass Model." The rules for constructing points using this model are as follows:
  1. We can draw an infinite line passing through any two constructed points.
  2. We can find the intersections of the line passing through two constructed points and a circle which with centre a constructed point A and radius the distance between A and some other constructed point.
  3. We can find the intersections of two circles, each defined by its centre (a constructed point) and any point on its circumference.
    Here, the constructed points are the intersections of lines (built as by the rules) with lines, lines with circles or circles with circles. The only starting condition we need is two points the distance between which is one.
    With this in mind, it is readily seen that this model can do all the match-stick model can and more easily. (If you do not feel this way after reading through the rules for both models, spend some time playing with the two applets -- the one found here on the Match-Stick Model and the one found here on the Ruler and Compass Model.) However, the other direction is not immediately obvious.  This is why, in the next section, we shall outline a proof of why one can, by using the Match-Stick model, construct all the points that are possible to construct with the Ruler and Compass model.

Match-Sticks are equivalent to a Straight-Edge and a Compass

    You may find the title of this section a little odd, especially if you have not been reading this document sequentially. In this section, we shall outline a proof of the fact that using a straight-edge and a compass or using an  unlimited supply of match-sticks does not matter if we are only interested in the points which can be constructed with those tools. For a more precise description of what is allowed in each model look at the previous two sections.
    Before we get into the details of the proof, note that the point of this document is not to give a completely detailed and mathematically rigorous proof, but, rather, to present the key ideas that allow one to accomplish that. Of course, one can always go to the reference section for pointers to places where a more detailed proof may be obtained.

    Now, to the proof proper. As suggested in the previous section, using a straight-edge (unmarked ruler) and a compass, one can easily construct anything one can construct with match-sticks alone. This is because we know how to translate and rotate distances and we are given distance one to start with. For more detail look at [2]. Therefore, we shall concentrate on proving the converse. We shall first demonstrate how to do some useful constructions which will thereafter be used in showing that the three constructions given here can be carried out using our match-stick model. We shall call those 'helper constructions' lemmas, which is a term used in mathematics and given to results that are used to prove other results.

Lemma I. Given two distinct points, A and B, which are at distance less than or equal to one, we can construct an arbitrarily long line segment that passes through those two points.

Here is the construction.

Figure 1.

Note that this not only produces a line, but it also gives a means of obtaining a particular parallel to AB -- the one at distance sqrt(3)/2. Note that this procedure may be used to extend a given line. Try it out.


Lemma II. Given two points, A and B, one distance unit apart, we can find a point M which is the midpoint of AB.

Here is a construction that bisects the angle formed by putting two sticks to form an isosceles triangle.

Figure 2.

Observe that the procedure can be applied to bisect any angle less than 120deg and not equal to 60deg. Also, note that this construction supplies a means of dropping a perpendicular from a given point C to AB, by laying CA and CB as the first step. if the distance between C and AB is not less than one, we can, using the construction in Lemma I, "lift" AB up by laying down parallels. This, of course, applies whenever this distance is not an integral multiple of sqrt(3)/2. However, discounting this restriction, once we have dropped the perpendicular to some parallel of AB, we can bring it down all the way to AB by applying Lemma I to extend it. Try bisecting a segment yourself.


Lemma III. Given points A and B at distance exactly 1, we can find the midpoint M 1/2 away from both A and B.

Figure 3 depicts a possible construction for finding the midpoint. We start with points A and B which are assumed to be one stick length apart. Also, we are given a point C on the initial stick. It turns out that we can always find such a point, but showing this is left as an exercise for the reader (Hint: Consider the triangular lattice by building only equilateral triangles starting at (0,0) and superimpose the triangular lattice starting at (1/2,0)). The best way to understand how the construction goes, is to try to reproduce it. Here is the setup for the applet. Follow the alphabetic order of the points from Figure 3 and note that to get D, E and G you need the second rule, to get K use the first rule with DJ and to obtain K use the first rule again but with HF.


Figure 3.

This construction does more than just prove the Lemma III, it also has the following consequences:

  • First, the construction will apply, as in Lemma II, to bisect an angle of 60 degrees.
  • Also, the construction will apply, as in Lemma II, to drop a perpendicular on a given line, where the perpendicular is an integral multiple of sqrt(3)/2 --- that is, this solves the only problem we had in Lemma II in constructing a perpendicular from a given point to a line. Of course, we can again lift up the line and use these constructions to drop a perpendicular.
    • Lemma IV. Given a line l (defined by two points A and B) and a point C not on the line, we can construct a parallel of l that passes through C.
    Here is a partial picture of an example construction (Note that A and B may be very far from one another -- look at Theorem 1 below -- here the points were chosen so as to simplify the figure).

    Figure 4.

    The idea is to keep lifting up AB until the parallel is within distance 1 of C. Then the third rule allows to construct points D and E on the picture. Using Lemma I, we can extend the segment EC to EF. Finally, the parallel at C is given by bisecting the angle at C formed by DC and FC (for the bisection refer to II or III).  The reason for that is the following calculation:

    We want CG to be parallel to ED. For that we need the angle <FCG to be equal to <CED. So if <DCF = 2(<CED) CG would indeed be parallel to AB. Now, since the triangle DCE  is isosceles, we have that 180 = 2(<CED) + <DCE. Also, since EF is a line, we must have that 180 = <DCF + <DCE, and solving the system of equations we obtain the result.
    Try to find the parallel yourself. If you have problems doing that here is the complete construction.


    Lemma V. Given any two distinct points A and B, we can bisect the distance between them, that is, we can find the midpoint M between A and B.

    On Figure 5, we see an instance of this problem. As mentioned in the proof of Lemma III, we can find a point C which within distance 1 of A. It is safe to assume that it will not be on the line joining A and B (if it is, there is another point which is not -- see the exercise in the lemma). Nw, we have the situation in the previous lemma, that is a line -- defined by AC -- and a point, B. We can therefore, construct a segment at B going through some D which is parallel to AC.  Now, the idea is to build similar figures until the points Y and Z are produced such that dist(Y, Z)<= 1. At that point, apply Lemma II or III to obtain the desired point. If you need more details look at [2].


    Figure 5.

    You can try out this construction here.
        We are now done proving intermediate results. In what follows, we shall treat the rules for the Ruler an Compass model one by one and we shall show that we can carry out those constructions in the match-stick model.

    Theorem 1. In the match-stick model, we can build a line given any two constructed points A and B.

    If the points are at distance less than or equal to one stick length, just apply Lemma I. On the other hand, if they are far apart, by Lemma V, we can find the midpoint M between A and B. This point is also on the line we want to construct, so we can now look at the two smaller segments AM and MB. Apply the same idea -- that is, split in two if necessary -- and eventually we will have constructed a point P on the desired line which is close enough to either A or B and so that we can put a stick through AP, say. Finally, by the first lemma, we can extend this line as necessary.
    For the subsequent theorems, there are animations of constructions, to restart them, simply click on the image.

    Theorem 2. In the match-stick model, we can construct the points that correspond to the intersections of a line, defined by two points, and a circle, defined by a point C (centre) and a point D on the circumference (CD is the radius).

    First, here is how one transfers a length (in this case the radius)
     
    1. Draw the radius CD.
    2. Construct the line where the distance is to be transferred.
    3. Bisect the angle between the two segments using Lemma II or III, say.
    4. Drop a perpendicular from D onto the bisector.
    5. The intersection gives the desired point.
    		  

    Now to the demonstration
     
    1. Assuming we have the line already (step 0) drop a perpendicular from C to the line AB.
    2. Next, extend the line CE and transfer the radius onto that extension using the above idea.
    3. We know that there is a point close to F, so we can construct the point G such that FG is of unit length.
    4. Construct the line segment CG using theorem 1.
    5. Extend FG.
    6. Construct a perpendicular to CG at E.
    7. Build a parallel to CF at H and transfer to it the length GH.
    8. Now, build a parallel to HE at K to obtain L. 
    9. If the line actually intersects the circle, it would be possible to now put a unit stick from L and touching the line AB at M. To see this consider the similar triangles FGC and FHE and note that LE=GH. From here we can conclude that LE=(CE/CF).
    10. Build a parallel to LM at C. It turns out that this actually gives one of the desired points. To see this, consider the similar triangles LME and CEN. Using the identity from the previous step, we can show that CN=CF=CD, that is we have the right point.

    Theorem 3. In the match-stick model, we can construct the points corresponding to the intersections of two circles A(B) and C(D).
    First, a clarification. A(B), for example is used to denote a circle as in the previous theorem, i.e. A is the centre and B is a point on its circumference. Note that we do not claim that we can draw the circles, but merely to find their intersections. The idea is to devise a construction that finds the midpoint of the intersections (if only one intersection the co2nstruction will find it immediately)  and, since it will be on the line joining the two centres, erect a perpendicular at that point. Using this line and any of the two circles, we can apply Theorem 2 to find the intersections. So, here is a demonstration of the construction
     
    1. Produce AB and AC.
    2. Construct a parallel to AB at C and transfer the distance CD to it.
    3. Join C to B.
    4. Extend AB and produce a parallel to BC at E. The intersection of that parallel with the extension of AB gives F.
    5. Now, produce a parallel to AC at B and transfer the length BF to it obtaining a new point G. Note that BG is now of length equal to the radius of the smaller circle.
    6. On AC transfer the radius of the big circle obtaining H.
    7. Join H and G and produce a parallel to HG at B. Label the intersection of said parallel with AC -- J.
    8. Now join C and F and produce a parallel to the new segment at J obtaining K.
    9. Transfer the length of AK to AC obtaining L.
    10. Finally, bisect the segment LC to get M and erect a perpendicular to AC at M.
    At this point you may be wondering why this construction gives what we said it would. A complete proof will not be presented, but here is a hint: Look at the final picture. Call the radius of the big circle a and that of the small one c. We can now imagine two triangles. Pick the top intersection of the circles and call it I. Now, we have the right angle triangles AMI and CMI that share the side MI. Therefore, by Pythagoras,
     AM2-CM2 = a2-c2
     (AM-CM)(AM+CM)=(a-c)(a+c)
    AC/(a+c) = (a-c)/AL
    where L is such that LM=MC. From here, it should be easy to write down a formal proof if so desired.