You see with only four colors you may… Oh wait what?

Earlier today a guy sitting next to me was just killing time by just drawing random figures in MS Paint and using the fill in areas with the fill in tool. I was going to humor him to try to color his picture with as few colors as possible (with the rule that no adjacent zones have the same color). I was presuming that we would end up with something hinting at the 4-color theorem but as I was doodeling I began to realize that there was something weird going on. You see… I only seem to need 2 colors to color my partitions of the plane. The actual partition is created by tracing a continuous line around and only allowing pair-wise intersections and eventually closing it on itself.

PathcoloringI

After some inspection I’ve come to the conclusion that whatever is going on is a consequence of the way I am tracing out the curve, where the fact that I am not allowing  the line to pass though the same point more than twice so every vertex in the corresponding graph always has 4 neighbors which must be the source of it.

Could of course also just be an odd coincidence that my partitions have had this property but I am nevertheless looking forward to figuring out why or how to construct a counterexample.

EDIT: July 2015. Since as it stand I’m probably not making another post on this until I’ve come up with an original proof I’d nevertheless like to add that the result indeed holds and is exclusive dependent on every vertex having even degree (in this case). “The two color theorem” will produce some proofs but if you have Peter Cromwells Polyhedra available at your local library I’d like to recommend it’s chapter on colorings which contains a proof of a slight rephrasing of this result on page 339-341 on top of some other novel results.

Spending the weekend folding polyhedra and finding convex internal angles

So I’ve managed to resolve the circle construction question from a few posts back and determined that any number n can be constructed by a fairly small number of operations; more precisely the 2-logarithm the number but I’ve put off putting together a good description of the proof as I’ve been preoccupied with school, work, and another new mini-project: Polyhedra.

I originally got the idea that I should look back into Polyhedra after I overheard some students mentioning the concept of the Euler characteristic of a graph (V + F – E) and recognizing that I remembered very little of that particular theory I set to refreshing on the theory and making lots of paper polyhedra, drawing Hamiltonian paths, and colorings and so on as I stumbled over them.

WP_003402

As I reviewed the E + F – E = 2 proofs I also had to recognize that I had some gaps in my knowledge regarding the formal existence of triangulation of polygons and continued on the merry chain of ‘better check that’ untill I at the bottom of the chain ended up with

Every polygon has a strictly convex angle. (An internal angle less than \pi)

A statement for which I designed the following proof (which I unfortunately realized had some issues as I was typing it)

Let  P be the polygon A_1 A_2 \cdots A_{n-1}A_{n}spanned by the n points A_1, A_2, ..., A_n in the plane. Consider the line L formed by extending the segment A_1 A_2 and let A_k be a vertex on $P$ which is of maximal distance from $L$. Or more precisely has the following property

  • For any other vertex A on P the distance from A to the line L is shorter or equal to the distance between B and $L$.

Now (using the Paralell postulate) let L' be a line through B which is parallel to L. By construction all vertices on P either lie on L or on the same side of L' as L (A_1 and A_2). Let us for convenience say that P lies on the ‘south side’ of L'.

At most one of Bs neighbors in the polygon on P lie on L' (for otherwise it would be a redundant vertex) and so the angle formed by these three points contained on the south side of $L’$ is strictly convex and it is an internal angle of P. (It is internal for a ray from due north into B intersects the polygon 0 times (an even number). We have therefore found a strictly convex internal angle!

I will have to admit that I realized an issue with this proof as I finished it as I had somewhat embarrasingly not properly considered how to formulate (prove) that the ‘south’ angle at B was indeed the internal one and it sort of exposes that I haven’t collected enough formal devices to differentiate between angles of the form CDE and $latex EDC without coordinates or images and the proof isn’t as satisfactory as I’d like and I will see if I can fix it.

The image I had in my mind for why this was true was after all pretty straight forward.

ExistenceofConvex

Using higher maths the existence of a strictly convex internal angle can be straightforwardly deduced from the existence of the convex hull as the convex angles of the hull put upper bounds on at least 3 internal angles of any polygon. But it of course has the issue of just kicking the ball further down the corridor as you’d have to prove the existence of a convex hull.

Constructing more integers using compass. 7 and 15.

Tired an a little bit hungover today I decided to play some more with the concept of constructing a multiple lengths with a compass and as few operations as possible; the problem I sketched yesterday in: https://seriouscephalopod.wordpress.com/2015/04/03/o/

Nothing interesting really except firstly I realized I had missed that there was a 3-circle construction of ‘7’ while I had originally displayed a 4-circle construction in the original post and I suppose I should correct myself plus I thought it was kind of cute.

Creating7Using3Circles

Besides for that i suppose I have tried to gather some more empirical data regardning these constructions. I tried to write a program to runt through all simpler construction as if in a tree diagram with a new node added in every step but not having figured out a good cutoff condition I got stuck with too many ‘stupid constructions’ since I counted them all and the data set grew to quickly in relation to the data I got so I decided to scrap the algorithmic approach before I’ve figured the system better.

So I just tried to find constructions by hand and though my ‘minimas’ are only upper limits than unquestionable minimas as a result but here are the first minimal construction numbers which feel somewhat certain at least.

n m_n
2 1
3 2
4 2
5 3
6 3
7 3
8 3
9 4
10 4
11 4
12 4
13 4
14 4
15 4
16 4
17 5

At least in the beginning it has turned out that the powers of 2: 4,8,16 have formed good proto-constructions from which I can add just one circle to get to a nearby number so you can see that the number of circles necessary increases as you pass 4, 8, and 16. This might just be a quirk of the fact that these numbers are still pretty close to eachother or it is something fundamental. Nevertheless I can as the following question for further inquiry:

Question 2:  For some n is there a number k such that 2^n < k such that the minimal number of circles necessary to construct k is less than n (m_k \leq n)?

I suspect there is but we’ll see… I was however able to find a counterexample to Question 1 in the previous post.

Question 1:  Is the inequality

m_n \leq a_1 m_{p_1} + ... + a_{k}m_{p_k} \qquad (n = p_1^{a_1}\cdots p_k^{a_k})

in fact an equality or what is the smallest n such that it is a strict inequality?

That is as there better constructions than just reusing the constructions for it’s factors. The counterexample I found was 15 = 3 * 5 which using first the 3-step construction for 5 and then multiplying that by 3 using 2-circles takes a total of 5 circles as seen below

Creating15Using5Circles

Red circles first construct 5 and blue circles then construct 15 from multiplying 5 by 3.

However using first the 3-step construction of 8 and then adding one more circle you can get to 15. Creating15Using4Circles

So the inequality was not an equality. That’s nice because on one hand it would have been a scarily powerful result had it been true but this way (it being not) I don’t have to think about it anymore.

How many circles does it take to make an integer?

A few days ago I made a post about me beginning to play a little more with the concept of ‘minimality’ when it comes to compass and straight edge constructions. That is to try to complete a geometric construction in as few operations as possible at least for now considering the act of drawing circles and lines equally arduous and extending existing lines to infinity to be free.

Today I’ve begun to play a little with perhaps the simplest of the construction problems; that of creating a length which is a multiple of another length both starting at the same point.

It is fairly straightforward to realize that constructing an n-length will take at most n-1 operations as you can work your way over to n by means of iterated drawings of circles of radius 1 using the extremities as new centers. See the picture below for the example of constructing the length 5.

Draw5by5It is however evident that this is not the way which requires the fewest number of operations as if you instead make of use of some greater circles you can cut down the 5-construction to at least 3 operations as seen below.
Draw5by3

I suspect that some larger n-lengths might have their minimal construction by means of moving ‘off’ the line and  making use of some triangles or other shapes but if I for the time being limit myself to only making these kind of ‘circles along a line’ constructions I suppose the minimal number of circles necessary to make the numbers 2 through 8 should be visualized by

MinimalMultiples2through8

One thing you notice quite quickly when building these constructions is that they have something to do with prime numbers. Not surprising perhaps given that I was playing with multiples but I just wasn’t expecting it. You see this in the examples of 6 and 8 which are the composite numbers that the 6:construction involves first the construction of 3 and then doubling that length by the 2 construction and for the construction of 8 = 2*2*2 we resure the construction of 2 three times.

Thus if we call m_{n} the minimal number of circles necessary for constructing a length n we may put an upper limit on m_{n} for composite numbers. If n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}

m_n \leq a_1 m_{p_1} + a_2 m_{p_2} + ... + a_k m_{p_k} (1)

This is about as far I’ve come today with regards to interesting results playing with this problem but I am posing the following question for later

Question 1:  Is the inequality of (1) in fact an equality or what is the smallest n such that it is a strict inequality?

I’ve yet to make much progress with regards to some systematized way of investigating this construction problem except for the fact that you can reduce the construction to a symbolic scheme letting {0,1} be the set of the two numbers you start with and {0,1,2} the set you get when you put a circle about 1 with radius 1 and {0,1,2,4} what you get when you put a circle about 2 with radius 2 and so forth.

The idea is that to any set of numbers you can add any number which is the difference of existing numbers To {0,1,2,4} you may add 7 because 4 – 1 = 3 and you add this to 4 to get 7. I don’t have the time to think more on this right now but since today is easter and I will be tied up in family stuff for the weekend I want to make sure I remember to get back to it afterwards.

Working with a compass and straight edge takes time…

I am somewhat embarrassed to admit today was the first time I actually played with a physical compass despite being well into my 20s,having studied university maths for years and worked with the euclidean constructions for a year. WP_003271

Having run though most of the simple geometry questions I’ve had recently I thought I should return to just playing a bit more with the actual construction parts instead of the proof parts and the puzzle like questions of trying to figure out construction which consume the smallest number of operations. I was originally mesmerized by this sort of question when I looked up some of the constructions for how to trisect a line and finding it kind of surprising how few operations (circles and lines) you can reduce it to. When sketching constructions by hand it’s easy to loose track of how many steps you need to perform an action in practice as you bisect and angle there or draw a perpendicular here while the number of circles and lines being implicitely necessary can be quite staggering. On top of that most of the constructions in the Elements employ the operation of ‘moving a line segment to a point’ which if you’re actually to do it with circles and lines makes you go “HELL NO!. because (as far as I’ve counted) takes 4 circles and 2 lines for that simple thing…

Playing more by hand should probably add the necessary frustration to push me to find or look up some new methods.A for my weekly TikZ practice here is the fastest way to draw a parallel line through a point I’ve come up with so far:

TodrawaparallellLinewhich relies on the similarity of inscribed triangles.I would be genuinely surprised (or embarrassed) and not a little bit impressed if there was a faster one but I suppose eventually I’ll bother looking up whatever theory there is concerning minimality problems.

Why believe in the distributive law?

Today I did some substitute teaching math at a Swedish gymnasium (sort equivalent to highschool in the US) but my duties as prescribed by the lesson plan didn’t involve any substantial teaching but instead I was supposed to just aid them as they repeated some earlier work on their own. As they did this the basic problem of the day was that very few of them (okay, I’ll admit it, none…) very few of them knew how to work with multiplication by parenthesis.

The typical kind of uninspiring but nevertheless important type of problem to rewrite something on the lines of (x + 4)(x - 3) into ‘parenthesis free form’ x^2 + x - 12 and so on. There wasn’t time for an actual lesson on this so I mostly just game them ‘the rule’ and ‘pattern’ in most cases and moved on but it’s nevertheless really uncomfortable so as I got home I felt I should try to play with some arguments for why the distributive law ought to be true. You know… why you belive it in the first place.

What I’m talking about here is of course the expression

a \dot (b + c) = a \cdot b + a \cdot c

which in a sense is just an axiom but in most interpretations or visualizations of numbers has some very direct manifestation and I’d like to discuss my 3 main ‘spaces’ for where this law occurs starting with natural numbers and ending up with a geometric proof but in each case the real problem is just finding an interpretation of what multiplication \cdot is an play with it.

Multiplication as iterated addition

In the context of multiplication with natural numbers you can interpret 3 \cdot 4 to read literally as “three fours” or more precisely the sum of 3 fours: 3 \cdot 4 = 4 + 4 + 4, and more generally as:

n \cdot m = \underbrace{m + m + ... + m}_{\text{n times}}

interpreting a multiplicative expression as an instruction on how to carry some kind of addition. From this perspective the distributive law simply expresses the rearrangement of terms

5 \cdot (3 + 2) = (3 + 2) + (3 + 2) + (3 + 2) + (3 + 2) + (3 + 2)

5 \cdot (3 + 2) = 3 + 3 + 3 + 3 + 3 + 2 + 2 + 2 + 2 + 2 = 5 \cdot 3 + 5 \cdot 2

where the right hand side is simply the embodiment of the sentence “five threes and five twos” while the left hand side was “five threes and twos” which are naturally the same thing.

Working strictly symbols  you might say that a ‘proof’ of distributive law for integers is the same.

n \cdot (m + r) = \underbrace{(m + r) + (m + r) + ... + (m + r)}_{\text{n times}} = \underbrace{m + m + ... + m}_{\text{n times}} +\underbrace{r + r+ ... + r}_{\text{n times}}

n \cdot (m + r) = n \cdot m + n \cdot r

(This presentation I suppose is in spirit similar to what you would do to prove the distributive law for natural numbers in the Peano- or a Peano-like construction of the natural numbers.)
rectangleare1

Visualizing multiplication as area

The area definition of multiplication

The I suppose most common visualization for the distributive law I find in Swedish school book is using a particularly suggestive pictorial image using rectangular areas and which is nice because it’s very direct but has the problem of representing products of numbers as something different than numbers obscuring the super central property of closure but I get ahead of myself. So you start with the notion that if a and $b$ are two lengths represented as lengths then a \cdot b can be said to be the area of the rectangle which has a and b as its two sides.

Then a \cdot (b + c) can be visualized as the are of a rectangle which corresponding sides but that rectangle can be seen as the composition of two smaller rectangles.rectanglearea2

Comparing the two areas we arrive at the distributive law again.

Descartian multiplication

Another system which has the distributive property and which algebraicly is exactly the same as the (positive) real number system is working with relative proportions of lengths. That ‘2’ represents a length which is twice as long as the length called ‘1’ and adding lengths (‘1 + 3’) is to put lengths ‘1’ and ‘3’ next to each other to form a new length. In virtually every respects lengths are real numbers but just cutting ahead I simply define the length a \cdot b as the length obtained through the following construction:Definitionofdescartianmultiplication

This is essentially the was Descartes treated multiplication and working with proportions of similar triangles this construction checks out.

Now we can derive (a) distributive law from this construction by constructing all the lengths $a \cdot b$, $a \cdot c$ and $a \cdot (b + c)$ along a line and noting the existence of a congruent triangle which allows the equality to be obtained.

Distributivepngproof

This is probably my favorite trivial example of a ‘proof’ of the distributive law for real numbers but the formal part of the proof unfortunately relies on the most obscure of the Euclidean congruence theorem. To establish that the two triangles are congruent you would note that they both have the same base b and since their bases are parallel they share two angles as the base and from the so called ASA-congruence condition (Prop 26 Book I in Euclid).

Closing thoughts

I think all of these proofs of the distributive law in their respective settings have different benefits. The counting one is naturally the simplest one and is more obviously connected to numbers but it doesn’t give any indication as to why the same thing should hold for real numbers and students are usually averse to formalizing their approach to natural numbers since they’ve already developed so much intuition about them. The area one is the most instructive for real numbers but frankly I hate it since thinking about a \cdot b as an area screws with closure.

The final one is probably closest to an honest ‘proof’ since we closure is maintained and it’s fairly obvious but it relies on the most machinery and especially machine that is’t taught in Swedish schools anymore.

There some other ‘proofs’ of the distributive law I have in mind but none I think would be convincing to a student…

Pythagorean theorem by dissecting two squares into a third

In the last post in which I was discussing the problem of cutting a polygon into pieces I wrapped up the final argument by simply stating the fact that two squares can be cut into pieces and rearranged into another square rather than prove or demonstrate it. I didn’t bother giving the actual proof or demonstration because a) it was late when I finished the post and b) there are better explanations of the proof out there than the one I can come up with.

The ‘I’m bad at coming up with the best schemes for explaining things’ -thing is of course true one day later but in sketching a program which would do dissections in an automated way I ended up making some Tikz pictures anyways so I thought I might as well share them for completeness.

So given two squares the larger one can be cut into three parts and the smaller one into two parts and the pieces can be combined into a square which has the sum of their areas. As I said then this is related to Pythagorean theorem and the actual construction can be seen here.

Pythagorasbyrelocation

I apologize for my terrible choice of colors but as to finding the actual cuts you can essentially just place the smaller squares next to each other and cut out two equal straight triangles which corresponds to the triangle in the Pythagorean theorem.

Pythagorasbyrelocation2

 

Here is the very inoptimized Tikzcode for generating the triangle and squares. \a and \b determines the sizes of the squares.

\begin{tikzpicture}[very thick,scale = 1]
\pgfmathsetmacro{\a}{3}; %Side of bigger square
\pgfmathsetmacro{\b}{2};%Side of smaller square

\draw [fill = yellow] (0,0) -- (\b, 0) -- (0, \a) -- (0,0);

\draw [fill = red](-\a, 0) -- (\b - \a, 0) -- (-\a, \a) -- (-\a,0);
\draw [fill = blue](\b - \a, 0) --(0,{\b * (1 - \b / \a)}) -- (0,0) -- (\b - \a,0);
\draw [fill = green](\b - \a, 0) --(0,{\b * (1 - \b / \a)}) -- (0, \a) -- (-\a,\a) -- (\b - \a,0);

\draw [fill = cyan](0,0) -- (0,{\b * (1 - \b / \a) - \b}) -- (\b,0) -- (0,0);
\draw [fill = magenta](0,{\b * (1 - \b / \a) - \b}) -- (0,-\b) -- (\b,-\b) -- (\b,0) -- (0,{\b * (1 - \b / \a) - \b});

\draw [fill = red](\a, \b) -- (\a + \b, \b) -- (\a, \a + \b) -- (\a,\b + \b);
\draw [fill = blue] (0,\a) -- (\a - \b,{\a + \b * (1 - \b / \a)}) -- (\a - \b, \a) -- (0,\a);
\draw [fill = green](\b, 0) --(\a,{\b * (1 - \b / \a)}) -- (\a, \a) -- (0,\a) -- (\b,0);

\draw [fill = cyan](\a,\b) -- (\a,{\b * (1 - \b / \a)}) -- (\a + \b,\b) -- (\a,\b);
\draw [fill = magenta] (\a - \b,{\a + \b * (1 - \b / \a)}) -- (\a - \b, \a) -- (\a,\a) -- (\a, \a + \b) -- (\a - \b,{\a + \b * (1 - \b / \a)});
\end{tikzpicture}

Cutting and rearranging one polygon into another

I think Vladimir Arnold is one of my favorite modern mathematicians. Partly because I find his writings lucid but mostly because every interview or talk I’ve read by him is hilarious. He also took an interest in educational practices which of course resonates with me even though naturally his perspectives are somewhat skewed. One of the books he helped put together and which I came across recently is a set of problems aimed at children called Problems for children: 5 to 15 (in english). When you read it you have to either decide that it’s a joke or more of an idea of how you could set the bar because some of those problems are hard for even for guys like me and I’m 8 years past 15 at this point.

Still some of the problems are really good and especially #13 is a nice example of a problem for which it actually hurts to be proficient in math because you might jump to an answer to quickly. I’ve been slowly going through the problems every other day recently and today I worked with #39 and I thought I would just try and outline my approach to it because it’s a nice problem.

If two polygons have equal areas, then they may be cut into a finite
number of polygonal parts which may then be rearranged to obtain both the
first and second polygons. Prove this!

It is more or less clear that you should really just try and prove that any polygon can be cut and rearranged to a specific polygon such as a square for then you can just reverse the process to move to any polygon from the square. The scheme I followed to prove it was the following one:

1. Find a way to turn rectangles into squares

2. Find a way to turn triangles into rectangles

3. Find a way of turning a polygon into a collection of triangles

4. Find a way of combining a collection of squares into a single square

where in reality the motivation for it all worked in the opposite direction.

Starting out

I like Arnolds book because usually you can find some hint as to how you can approach the problem either from the image associated to the problem or from some other problem which might be more general in nature. If you have a polygon with a certain area A such that the base is \sqrt{A} then it’s height is also \sqrt{A} and just cutting off a corner an rearranging it you get a square with the same area.

equalbaseheighttosquare

Cut and transform rectangle to parallelogram with base \sqrt{A}

Now if the you have a general rectangle you can turn it into a paralellogram with base \sqrt{A} simply by drawing a line with that length from one of the corners to the opposite side and lop of a corner, move it to the other side and you get a parallelogram of the desired form. To find the actual distance $\sqrt{A}$ you can use the Euclid construction of the geometric mean of the two sides the special case of which I discussed in the square root post a while back.

rectangletoequalpolygon

Dissect parallelogram to rectangle

To cut and transform a parallelogram into a rectangle is just a special case of the method for transforming the other parallelogram into a square but I list it anyways for chronology.

ParalellogramtoRectangle

Cut and transform a triangle to parallelogram

This one didn’t come naturally to me as I originally tried to approach the triangle before the rectangle (for some reason) but once I recalled that cutting the triangle along the midpoints of two sides produced appropriate angles and lengths so that you can rotate the top part to form a parallelogram this one was obvious.

TriangletoParalellogram

 

General polygon

Now the case of a general polygon is within my grasp and I like my final solution though I have to admit its not very optimal in terms of the number of cuts you will effectively have to make. The points is that if we have any (n + 1)-sided polygon it can always be cut into n triangles each of which can be cut and transformed into a square.

TransformTriangleToSquares

The is likely multiple ways of fitting these pieces together but working specifically with squares I found that combining that cutting and transforming two squares into a cube is intimately related to Pythagoras theorem since several proofs of it consists of cutting two squares placed along the sides of a right triangle and rearranging them to form the square of the hypotenuse. Rather than restating a specific one I’ll just reference cut-the knots excellent collection of proofs where for example Proof #2 will do the trick of designing a procedure for combining two squares.

Final notes: Just to round of the evening I did some searches on this type of problem now that I was done and two results with I find worth to mention was a friendly intruduction from Berkley with animations (including the Pythagoras cut) as well as a site by  Gavin Theobald who has studied a method for finding more minimal cutting methods which though less natural to me is pretty impressive.

Would probably be kind of fun to program a program which dies this sort of thing and animates but I guess that’s a project for another day.