The 7 Tetris block circumference problem

Fancified name in the title aside I was checking out some worksheets for geogebra yesterday and came across one which had predefined tetris block elements. I played around building different shapes, originally wondering if you could make a periodic pattern out of an even ditribution of tetris blocks but I eventually landed on a different question which will be the topic of this prost.

So you start with the 7 basic tetris blocks as featured in the image below.sevenbasictetrisSo these pieces you can stick together into chunks in an amazing number of ways and each new figure naturally has some circumference. Assuming all the pieces fit rogether in one chunk the maximal circumference such a figure can have is 56 (think about it) but the question quickly becomes: What is the least circumference such a composite piece can have?

Here are some of the initial trial and error solutions which I played around with

Tetriscompositesnominimalcircumferencebut there nevertheless is a packing with even smaller circumference and it is proving the existence and minimality of this packing that will be the theme of this post.

Continue reading

Folding polyhedra and a novel connection between folding a tetrahedron and a 2D result.

So I’ve been folding a lot of polyhedrons out of paper this past week. Like a lot… But since the types of interesting polyhedrons I have left to built take a bit too long to construct adn I already wasted enough time folding the (small) stellated dodecahedron.

WP_003716

Instead I’m rather reviewing the ‘legitimacy’ of the folding schemes and figure out what relations actually govern weather something fits together or not. The prototypical example is the tetrahedron, the polyhedron with the fewest number of faces. The explicit construction of the regular tetrahedron (all sides equilateral triangles) is easy to show directly and is found in the elements and elsewhere but you can fold generic tetrahedrons by just making 4 triangles such that every triangles has common sides with the other triangles in a natural way. Made from one piece they are then flded together to form a possibly irregular tetrahedron. foldingapyramid

Empirically and intuitively this basically defines natural, a result in no need of further explanation. Nevertheless mathematically it almost seems coincidental. Just because two face can be glued pairwise doesn’t immediately mean all the faces should fit together collectively even though it’s about as natural a thing to postulate as the equality of the two base angles in an isosceles triangle.

The novel thing is that you can turn this 3 dimensional problem into a 2 dimensional one and use the vast machinery available to you in that space. You can note that folding an individual side is equivalent to rotating it about it’s common side with the bottom triangle where the it’s outer corner traces out a circle lying in a plane parallel to the altitude of the triangle and perpendicular to the common side.

rotatingtrianglesinpyramidIf the three faces are to come together their corresponding circles must intersect at a single point which means 1. the planes of rotation intersect along a common line (which is perpendicular to the plane and forms the height of the tetrahedron and 2. with the altitudes of the faces and satisfying relations to guarantee a consistent height.

Especially 1. is interesting because it forms a more ‘physical explanation’ for why dropping and extending altitudes in the original net intersect at a common point which can be taken as a purely classical 2 dimensional geometric result.

pyramidtriangletheoremThe thing I find neat is that this result seems kind of arbitrary in 2D but as part as a 3-dimensional picture it makes perfect sense.

I’ll have to see what’s the best way of extending this to folding schemes with a general polygonal base.

The cuboid volume formula and the dissection of a cuboid into a cube

So at the end of the last post I gave the outline of the idea of how you might extend the dissection of a rectangle into a square and the definition of area to an analogous procedure for the cuboid and it’s volume. The idea is really simple but I thought I’d practice my diagram writing skill by providing an illustration and expand the definition of volume.cuboiddissection0

Okay so we say that we have a cuboid with dimensions a \times b \times c where we conventionally say that it has volume abc meaning it has the same volume as a cube with side \sqrt[3]{abc}. Let us use dissection to motivate this; that is describe a procedure of cutting up the cuboid and reassembling it into the prescribed cube.

We will essentially perform regular rectangle to square dissections face-wise splitting the cuboid into prism.

Let us start with the a \times b face and dissect it into a rectangle having one side \sqrt[3]{abc} and the other (by the area formula) being ab / \sqrt[3]{abc}.Applying this to the whole cube the cuts through the face are extended through the solid along planes perpendicular to the face forming prism which are rearranged to form a new cuboid with \sqrt[3]{abc} as one of it’s side.

Note the depth c of the cuboid is unaffected by this procedure.

cuboiddissection0

(You might need more pieces than the image indicates)

Next we turn out attention to the face with sides ab/\sqrt[3]{abc} and c and perform the same procedure where this face is transformed into a rectangle with one side being \sqrt[3]{abc} by construction and the other side

\cfrac{\text{Area of face}}{\sqrt[3]{abc}}= \cfrac{abc / \sqrt[3]{abc}}{\sqrt[3]{abc}}=\sqrt[3]{abc}

And so this face is square! All the sides of this cuboid are therefore equal and we’ve ended up with a cube.

*This procedure is not original but my interpretation hasn’t been checked so some caution should be taken

Sidenote: Just as triangles and polygons can be dissected to rectangles a prism can therefore be disected into a cube as well and paying attention to the details of such a procedure you recover the conventional Bh formula for general prism. For the cylinder we don’t have any elementary means of dissecting into a cube but just as you may approximate a cirvle by triangles you can approximate the cylinder by triangular prisms and obtain the standard formula.

Dissection of a rectangle into a square and a definition of area

This post is simply a reworking of my previous post on this subject as I realized I had missed a special case which is accounted for in a single line but which nevertheless had gone unmentioned. The problem was to start with a rectangle of dimensions a \times b, naturally having area ab and cutting it apart into pieces which are then rearranged to form a square with the same area.

This procedure involves abusing the knowledge that the resulting square will have as the lengths of its sides \sqrt{ab} where you start by cutting a ‘pseudo-diagonal’ having this length across the rectangle, having sliced of a triangular corner. Displacing this corner to the other side of the rectangle you obtain a parallelogram with \sqrt{ab} as its base and implicitly also \sqrt{ab} as its height by virtue of the known area. This parallellogram is then cut along on of it’s altitudes normal to the side with length \sqrt{ab} and rearranging this pieve the resulting shape is a square. Diagrammatically the procedure is shown below.

BisectingFatRectangleNote 1: There were two things I wanted to expand on regarding this procedure. Firstly that it needs to be supplied an additional step if the rectangle is too wide. More precisely if the base is more than twice the height. 2a < b If that is the case an additional cut will be required. We may first note the limiting case 2a = b where the second cut now  intersects with one of the corners

BisectingDoubleRectangle

and if the width is increased beyond this limit our desired seond piece is only partially contained in the actual paralellogram. You see pretty much immediately that all you need is to move this piece and then slice of a tip segment and move that but it’s nevertheless an additional step which should have been noted upon.

BisectingThinRectangle

Note 2: The second thing I wished to expand upon was simply argument for the fact that this actually forms a square. Knowing all the formulas for area it is pretty easy to fill in all the blanks such as that parallelogram with area ab and and base b must have height $a$ or if a rectangle has area A and base $b$ then its height would be \sqrt{A} / b and so on.

However it would be much neater to take this rearrangement as the proof that the area of a recangle with sides $a\times b$ has area ab. To outline this proof I will make use of this particular definition of area:

If a geometrical figure can be cut into a finite number of smaller pieces and rearranged into the shape of a square with side \sqrt{A} we say that the figure has area A

This is not a complete definition of area as what constitutes a ‘piece’ and ‘rearranged’ is unclear and not all figures are necessarily rearrangeable and like all casual definitions it might invite paradoxes but it allows us to form a class of figures which we say have equal area and make more practical sense of that means instead of just memorizing formulas. For example to say an A4 paper has an area of 623.7 cm^2 now means it can be cut and rearranged into a square with a $\sqrt{623.6} = 27.97$ cm side.

The part of the dissection which I would like to prove without references to area that the resulting shape really is a square. With reference to the diagram below we say we have a parallelogram height a and base b so such that it’s slanted side has length sqrt{ab} and wish to show that the altitude normal to DC goign through B, BE, also is \sqrt{ab}

areaofrectangleproof

This is most easily proven using the similarity of the two triangles AEB and EDB which follows from the angles A and C in a paralellogram being equal. From this we get

BE / b = a/\sqrt{ab}

and thus

BE = \sqrt{ab}

Therefore it is truly a square that the rectangle is being rearranged into and just to be needlessly pedatic lets once again note that all this meant that a rectangle with dimensions a \times b was possible to rearrange into a square with side \sqrt{ab} meaning the area of the rectangle really is ab!

Sidenote: What jogged my memory on was that I’ve been thumbing through this Peter R: Cromwells rather charming book Polyhedra where the problem of how you might define volume partially (but ultimately not exclusively) though dissection sprang to mind. On page 45 I also recovered another outline of how to dissect a general polygon to a square though with a different final step than my own and for whatever reason omitting the step outline above. In principle you should be able to perform this dissection ‘face wise’ to prove the volume formula of a prism (or rather the a\times b \times c cuboid) but I’ve yet to complete the details of the proof.

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…