Wednesday, December 5, 2012

hex life and sandpiles

As I mentioned in a previous post, I've been meaning to learn more about cellular automata. Maybe in preparation for more formal learning, or maybe instead of it, I've been playing around with some simple examples.

Another Hex Life Critter
The classic cellular automata example is Conway's Game of Life. One thing I've been playing with here is using a grid based on hexagonal-close-packed circles instead of the usual squares.

Although this hex life is not as exciting or explosive as the standard square grid Game of Life, it does yield some nice stable patterns and oscillators (in the earlier post I mentioned some windmills and blinking diamonds). The picture at the top of this post is of another formation that includes a repeating 3-cycle.

Reasoning out why a pattern stays, decays, or oscillates reminds me of playing MineSweeper, without the explosions. For a given pattern, look and see how many "live" cells are around each cell, and decide whether or not that cell will stay the same or change state, based on the rules.

The standard Game of Life rules, used here, are:
  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population. (Starvation)
  2. Any live cell with two or three live neighbours lives on to the next generation. (No Change)
  3. Any live cell with more than three live neighbours dies, as if by overcrowding. (Overcrowding)
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. (Birth)
There are lots of other rules that give interesting patterns - sandpiles, for example.

Hex Sandpiles
I learned about these from a recent post on Math Munch. Unlike the standard Game of Life, sandpile cells have many states - not just dead or alive. The pictures below show some sandpiles on a hexagonal grid where there are six states, state 0 is black, state 6 is white, and states 1-5 are shades of grey.

Initially, all cells in the sandpile have state 0 (no grains of sand in that cell). One particular cell, the center of the sandpile, keeps having its state incremented (sand is pouring onto that cell). The key rule for sandpiles is that once a cell reaches its maximum state (full of sand) it spills out into its neighbours: once a cell reaches state 6, it gets reset to state 0 and all its six neighbours have their state incremented by 1.

This leads to a symmetric growing pattern that, when done on a hexagonal board, creates patterns that look like snowflakes. What is interesting to watch with these is that things can progress quite slowly until suddenly the whole pile can get into a state where there are cascading changes as waves of "sand" ripple through the whole pattern.

Here are some examples of the sort of things you'll see while watching sandpiles grow (on the white background below, state 0 is white and state 6 is black):

Monday, October 22, 2012

triskelion spiral

Maybe inspired by looking at those snake limits or water-bomb twists, I was looking at spirals again today (see a post here from a bout a year ago). This time, looking at spirals that are generated when you take a polygon, rotate it, and grow it several times. Here's one made up of about sixty triangles:

This spiral reminded me of the Manx flag - which is a motif that is sometimes called the triskelion.

Here's a similar spiral, using pentagons instead of triangles:

Thursday, October 18, 2012

Borges, Escher, & Origami Tessellations

The Argentinian writer Jorge Luis Borges is a favorite of mathematics enthusiasts - many of his short stories and essays have overtly mathematical themes, and much of his writing plays with structure and paradox in a way that appeals to readers that have a mathematical bent (see this Wikipedia article on Borges and mathematics).

I just recently read his short-story collection, a Universal History of Iniquity, which does not have any direct mathematical overtones (that I can recall), but whose cover in the Penguin Classics edition plays homage to Borges' mathematical ways with one of M.C. Escher's limit engravings Snakes.

In keeping with the mathematical theme, a  new cover for the same book features the origami tessellations of Eric Gjerde (see his post about the cover here).

The tessellation is Gjerde's water-bomb tessellation, and is one of the more easily folded models from his book. See this video on Happy Folding for a demo of how to make the water-bomb tessellation - it is fun to fold, and can be playfully integrated into other origami projects... for example, Beth Johnson has turned it into a sheep.

Friday, October 12, 2012

hex life

One of mathematics' best known recreations is Conway's Game of Life, popularized by Martin Gardner in his Mathematical Games column (see this recent post on Math Munch for another classic Gardner recreation: flexagons). John Conway first came up with his Game of Life using a square grid and (as described in this nice wikipedia overview) four basic rules:
  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
Things like Conway's Game of Life are examples of what are more generally called Cellular Automota - there are lots of great websites that offer overviews of these, and many include interactive demonstrations.

I've been wanting to play around with life-like automata for a while, so for fun I decided to try out the standard 4 rules (above) on a grid made of hexagonal close-packed disks, instead of the usual square grid. On a hexagonal grid, every cell has only 6 neighbours, instead of the usual 8. This little experiment showed me how delicate and perfect Conway's original life is - and how changing the geometry a little can have a big impact.

In the experiments that I tried, hex-life, quickly dies down to a few stable formations (patterns that don't change) and oscillators (patterns that move through a set cycle of formations). These were pretty, but I didn't observe any of the explosive or travelling patterns that makes the usual Game of Life so interesting.

One oscillator that emerged was a simple "windmill" (you can see one in the middle of the screen capture above) that has three dots that seem to rotate around a central dot. This is actually an oscillator of period 2 that is governed by rules 1, 2, and 4. The diagram below shows how many neigbours each cell has - with live cells coloured blue and dead cells coloured white.

Another oscillator was the blinking diamond shown below. The two cells across the middle of the diamond blink in and out of the live state, governed by the rules 2, 3 (blinking off) and 2, 4 (blinking on).

I found a some other oscillators, and quite a few stable patterns, but nothing too exciting - I am sure there is a joke I could make here about having a stable, nice, but not too exciting hex life, but I won't. :) 

BTW - just as I was writing this up I came across a new post about a continuous version of Life - definitely worth looking at.

Sunday, September 16, 2012

Generic Rectangles

Quite a while ago I posted about using the grid method for dividing polynomials. Using grids or generic rectangles as they are more commonly called, makes dividing polynomials seem like doing a crossword puzzle or a sudoku.

There are number of ways to use generic rectangles, and I thought I would try to do a few posts about some of their other uses, which include factoring trinomials and completing the square. This first post is just going to be about polynomial multiplication.

When multiplying, generic rectangles seem to provide for polynomials what grid multiplication and lattice multiplication provide us for numbers - a way of arranging things on the page so that we don't mess up our calculations. Grid and lattice multiplication allow us to break down our numbers into more manageable chunks and, in the case of lattice multiplication, give a way to keep track of "carries." In school, grid and lattice multiplication are sometimes presented as an alternative to standard "long" multiplication.

Those familiar with grid and lattice multiplication for numbers will feel at home with generic rectangles, but there are some differences. In the world of polynomial multiplication, there are no "carries" (terms in a polynomial, unlike decimal places don't overflow into each other), and there is no generally used "long multiplication" style that needs replacing. For polynomials, what generic rectangles give us is a way to keep track of all those terms that come out of the distributive law, which most students struggle to keep track of using mnemonics like FOIL. (Once recursion becomes something well-understood in middle school,  FOIL might be a reasonable way to teach the distributive law, but until then, teachers please consider using generic rectangles.)

Generic rectangles also have an affinity with algebra tiles - a manipulative that is sometimes for learning polynomial multiplication. If you use algebra tiles, generic rectangles are a nice thing to move on to if you tire of pushing around all that plastic. Unlike those rigid tiles, generic rectangles are more generic: although they don't provide the full force of the area metaphor for multiplying that algebra tiles do they allow you to multiply any kind of terms.

A first example
The first thing to do when provided with two polynomials that are to be multiplied is to set up the grid, with the terms from one of the polynomials across the top row, and the terms from the other down the leftmost column.

Each term is multiplied, like terms are gathered, and the results are summed, which provides the answer.

A little bigger example
Here's an example with a trinomial and a binomial.

Again, step 1 is just putting the factors to be multiplied on the left most and topmost column and row of the grid, and step 2 is just completing the term-by-term multiplication to fill in the grid.

Finally, like-terms are collected and the final result can be written out.

An infinite example
That's fun, but what about multiplying together two infinitely long polynomials? Why not? Of course, we'll  quickly run out of space, but we might see something in our grid that will help us get to a solution.  Now, instead of thinking of polynomials in the way you might usually think of them, you should consider these infinitely long polynomials as formal power series - polynomials that we will never evaluate, and that we are just treating as worthwhile mathematical objects in their own right, regardless of whether they ever converge.

Consider the product:

We can make a grid like this:

And start to fill it in:

Do you see the pattern that is emerging when you start collecting like terms? Once you do you'll probably agree that:
If you go a little further with this, you'll find the triangular numbers lurking in here. For  d > 0:
The power series on the right has coefficients that are the "d-1"-dimensional triangular numbers (or, the d-1 column of Pascal's Triangle - see this post).

Thursday, August 16, 2012

a deep dive into the multiplication table

When I was quite young, I was told "no one will pass Grade 5 without memorizing the multiplication table!" With fear and dread I did somehow pass despite my teacher's grim prediction, and even progressed a little further without learning my tables.

Once my enemy, now my friend, those old tables which once seemed to bar my educational progress now appear to me full of interest and beauty.

1. Rainbows in the table

Is there a pattern to how the numbers in the table grow? Sure there is, and its hyperbolic. If you color in the numbers of the table according to their magnitude, you might notice bands of color that curve in an almost rainbow-ish fashion. See here for a bit more on this.

2. Stars in the table

As you skip along a row or column, do the last digits of the numbers form a pattern? You know they do, but drawing out the pattern on a circle shows some affinities among the multiples that you maybe had not noticed before. Start with 10 points around a circle, and skip count by a number, joining up the last digits as you go. Here's what happens for the number 6:

Different numbers sometimes give the same stars, but joined in a different order - maybe you can figure out why.

For a little more on this, see here.

3. How often do numbers appear?

How many times does a given number appear in a multiplication table of a certain size? How often do primes appear? How often do composites? What number appears most frequently?

Not too surprisingly, the number of times a number shows up in a multiplication table depends on how many ways you can multiply two numbers together to get that number. So, a prime is only going to appear twice (on the top and left borders of the table).

As you explore these questions, you may find that the answers would turn out a whole lot nicer if only we used a slightly different kind of multiplication table. That's what I found anyway, and it lead me to look at an extended multiplication table. These are a pain to write out (use a computer if you can) but have lots of nice properties.

Below is a picture of the extended 12 table (which contains a standard 3x3 table). The rule for writing these out is that you make each row by skip counting up to a given number (12 in this case).

In the extended 12 table above, every prime less than 12 appears exactly twice, and every composite less than 12 appears a number of times that is directly related to the number of factors it has. In fact, every number appears a number of times equal to the size of its factor lattice. For example, the number 12 occurs 6 times - here is a picture of its factor lattice, which has size 6:
For a little more on factor lattices, see here, and this post gives some information on how these lattices are connected to the extended multiplicaiton table.

3. What is the average of the numbers in the table?

Why go out and gather data to do your "data management" activities when you've got a nice slab of numbers hanging on your classroom wall? What is the average of all the numbers in a multiplication table anyway?

Add 'em up and divide by how many numbers are in the table - but don't rush. The structure of the table makes it kinda easy. Consider an n x n multiplication table. If you add up a single row, it would look like this:

Which could also be written like this:
And all the rows are like that, so it makes it a lot quicker if you determine the sum of the first n numbers once, and then re-use it.

If you find the mean of the table, you'll notice that the average of all the numbers in the table is equal to the average of the number (or numbers) in the table's exact center. In other words, the average is also the average of the middle. If you use an odd number for n the mean of the table is equal to the single number in the middle (try it for a 3x3 table if you want to do it quickly). If you choose an even number for n (like the usual 10 or 12), then there is no number in the middle and you need to take the average of the four middle numbers.

Figuring out the formula for the mean, and showing that it is the same as the middle, or average of the four middle numbers, is a fun exercise if you like calculating with sums. Here's one derivation of the mean calculation:

5. Adding up numbers in the table leads to other surprises

Once you start adding up entries in the table, you might come across some other surprises.

For example, the sum of the entries in the main upwards diagonal and the diagonal above it is equal to the sum of the entries in the main downwards diagonal. Some on this here.

One other thing that might go unnoticed is that if you sum just the numbers above and including the upward slanting diagonal, you get a special kind of number known as a "triangulo-triangular" number (see here).

6. Skip counting on Sun Flowers

Leaving the classroom behind, consider skip counting and finding patterns in the sunflowers out in the meadow. OK, maybe not, but in an idealized mathematical sunflower you might notice some nice patterns - here the "seeds" that are multiples of 5 are colored in a numbered phyllotaxis spiral:

See more on this here.

Sunday, June 24, 2012

last-digit sequences

When you look at the last digits of an Integer sequence, you get a whole new Integer sequence. For example, if you look at the last digit of the sequence a_n = n^2 -n +1, you get the repeating last-digit sequence shown above (it has a period of 5). Neat thing: any sequence "like" this one will always have a repeating last-digit-sequence, and that last-digit-sequence will have a period of 1, 2, 5, or 10.

Here is another example that has a last-digit sequence with period 10:

Just looking at the last digits of powers of n provides other simple examples (see this old post).

Except when the terms are negative, last digits can be obtained by using modular arithmetic and working “modulo 10”, “ 54 mod 10” is 4, “12 mod 10” is 2, etc. So for the most part, instead of saying "last digit"  we can just say “mod 10” to get the last digits. When negatives are involved, the last digits can be found by “mod 10 – 10,” so without loss of generality we’ll just say "mod 10" when we want to grab the last digit of some number.

Let's look at sequences that you get from polynomials with Integer coefficients, a_n that are of this form:
It turns out that this kind of sequence modulo 10 repeats itself with a period that divides 10 - you can see this is true by proving that
This statement says that the sequence, mod 10, will repeat itself every 10th term - so its period must be a divisor of 10 in order for this to happen, which means its period must be 1, 2, 5 or 10.

One way to see this true is to consider any term  in the sum that defines a_n, and verify that when you sub in n +10, you'll get something that is congruent to n, modulo 10. This just requires ye-olde binomial theorem: all terms in the expansion except for one are congruent to zero mod 10 and just vanish:

These sequences sometimes also have nice symmetry in their last-digit sequences. When this symmetry happens you are able to find some value k where:
The value of k/2 provides you with an axis of symmetry for your sequence. For example, the first sequence shown above, a_n = n^2 -n +1, (this sequence is "Hogben's central polygonal numbers," mentioned here), there is a symmetry at = 3, so our k is 6.

Here's another similar observation about these kinds of sequences (those generated by polynomials with Integer coefficients) - their terms are either always even, always odd, or alternate between even and odd values (e.g. you won't get a sequence that goes "even, even, odd, .." or some combination other than the three possibilities mentioned). Can you see how you can show that this is true using similar arguments to the ones used here for last-digits?

Thursday, June 14, 2012

put in one's place

Consider, if you will, the question "What is the last digit of 4316 * 12  + 511?"

One way to quickly answer "what is the last digit?" questions like this is to realize that you don't need to do the full calculation - only the last digits of each number in the problem contribute to the last digit in the answer. So, you just need to calculate 6 * 2 + 1 and look at the last digit of that, which is 3.

When can we use this short-cut? With impunity when only multiplication and addition of positive Integers are involved - here only digits-in-the-ones-place of the inputs affect the digit-in-the-ones-place of the output. If you throw multiplication's tricky partner division into the mix, then I think that all bets are off (digits in all places affect the ones position in the result when you divide). However, we can still proceed with caution when  subtraction and negative Integers are in play: if we get a negative along the way while we are looking at the ones place, we need to pause and see if we should have "borrowed" from the tens place that we were ignoring.

For example, what is the last digit of (91536 - 648) * 12? Ignoring everything except the last digits in the original problem we have (6 - 8) * 2 = ( -2 ) * 2. At this point, we need to stop and realize that instead of keeping the -2 we should have borrowed from the tens position of  91536, giving us an 8 in the ones position, so we should have (8) * 2 = 16, so the last digit of (91536 - 648) * 12 is 6.

PS: The rest of the Peanuts cartoon featuring Peppermint's inventive rules for arithmetic can be found here.

Wednesday, June 6, 2012

more simple-yet-complex fractals


I'm back to playing around with fractals that are generated by looking at complex points that stay bounded when (repeatedly) plugged into a simple quadratic expression, as described here and here. I liked the pictures that came out, so I thought I would post them. :)

As mentioned previously, I'm using Processing for this, but now am using a Processing plugin for Eclipse (I'm currently using proclipsing, but I think there are other plugins available). I'm guessing that few people will be pleased doing this - people who like Processing's simplified view of Java may be intimidated by Eclipse, while hard-core Java programmers would likely not see much benefit in using Processing's library (I'm likely selling Processing short in thinking this -  I only have used a small bit of Processing and don't have a full appreciation for what it does).  But I like the simple API and model that Processing provides, and much prefer using a real IDE and writing most code outside the PApplet class. So, right now, I'm liking it just fine and would recommend it to anyone who thinks they might have similar preferences.

Thursday, May 31, 2012

liar-truther accusation graphs

One of the puzzles concerning the island of liars and truthers (#2 in the first post about these problems) involved a bunch of islanders accusing each other of lying, leaving you to sort out who was telling the truth and who wasn't.

I decided to present the solution in a truth table (in this post), but it turns out that for this kind of puzzle the answer is presented better (and found more easily) if you use a graph. For example, the graph at the top of the page (K_24,12) could represent 24 truthers, each accusing a group of 12 liars of lying - or it might be 12 truthers and 24 liars - it's hard to tell :).

Let's say you have an "accusation" puzzle, where a bunch of islanders are directly accusing each other of lying. Let each islander be represented by a vertex, and let each accusation be represented by an edge.

Note that it amounts to the the same thing if A accuses B, B accuses A, or if they both accuse each other, so it doesn't matter who accuses who - our graph doesn't need to have directed edges. The important thing to note is that if there is an accusation between A and B, then one of them must be a liar and the other must be a truther.

We want to find out who among the islanders are liars are truthers, and maybe represent this by colouring the vertices for liars one colour, and the vertices for truthers another colour. If A and B are connected by an edge this means that one of them is accusing the other of being a liar, they can't both be liars or both be truthers - so the vertices cannot be the same colour. You may see where this is going:  finding a solution to the puzzle is equivalent to finding a two-colouring of the graph.

What if in our puzzle we have some islanders "praising" other islanders - like if D says "A is telling the truth."? We might be tempted to add in a new kind of edge to represent this in our graph, but this isn't necessary. If D says that A is telling the truth, this means that both D and A must be the same - they must either both be liars or both be truthers. From the point of view of our graph, we can represent this by collapsing D and A and represent them both by the same vertex. Note that you can't have D and A accusing each other and praising each other at the same time - you get a liar paradox if you do.

Here is an example:

You meet a group of islanders and want to know whether they are liars or truthers. Alice says "Bob is a liar", Bob says "Carol is a liar" and Carol says "Bob is lying." At that moment, Dave walks up and says "Alice is telling the truth." Who are the liars and who are the truthers?

We can start by modeling the problem as a graph - with edges for "accusations" and to start with the "praise" as a dashed edge (1). Then we collapse the nodes that have a dashed edge between them (2) and finally find a 2-colouring of the graph (3).

This shows that either (a) Alice, Dave, and Carol are truthers and Bob is a liar or (b) Alice, Dave, and Carol are liars and Bob is a truther.

I think that seeing this as a coloring problem makes it more obvious what the solutions will generally look like. For example, if the puzzle hasn't "pinned" any of the islanders by saying explicitly that they are a liar or a truther, or hasn't fixed the number of liars or truthers (e.g. by saying "there are two liars" or something similar) any solution that you find will also give a "complementary" solution by reversing the colours - turning every liar into a truther and vice-versa. Also, in any puzzle where there is an accusation, the group of islanders cannot be all liars or all truthers.

In a problem like that doesn't have any islanders standing alone (i.e. not praising or accusing anyone and not being praised or accused by anyone else), if there is a solution, the graph will be bipartite. The picture at the top of this post is of a complete bipartite graph, which is what you get if all truthers are accusing all liars (or vice-versa). Here are some pictures of complete bipartite graphs, and here are some more.

A lot of liar-truther problems are not like these "accusation" scenarios. See here for more variations on the liar-truther theme.