mathrecreation

fractals on friday

2013-05-24T19:15:00.000-07:00

patterns abound

2013-04-25T16:53:00.001-07:00

Since noticing this graphic, I've spent a little time contemplating the patterns you can make by connecting 12 dots that are evenly distributed around a circle (above: no lines, and all lines). Twelve dots around a circle has some cultural resonance - we still see them up on many walls keeping time. Feeling the pull of patternicity and agenticity, other people, more mystically minded than I, have spent a lot of time making patterns on zodiac circles that look a lot like the ones here. What really makes 12 so useful and open to this circle pattern making are all those divisors (1, 2, 3, 4, 6, 12), which contribute towards making 12 the smallest abundant number (6 is perfect because it is equal to the sum of its proper factors, 12 is abundant as the sum of its proper factors is greater than itself).

good ole prime spiral

2013-04-16T19:17:00.001-07:00

For a while I have been putting up images from this blog on tumblr (if you like the pictures but not the words, that's the version of this blog for you). Far and away the most popular picture is this one, which reminded at least one fellow tumblrite of the Death Star. To be honest, I don't really know why this picture stands out from the others, or why you might choose to re-blog it rather than a picture of a kitten (I guess no one blogged this over a kitten... most choose this and a kitten).

I do occasionally throw some things up there that don't have a blog post associated with them, and I think this might be one of them (until now).

This is a picture of a quadratic number spiral with only the primes showing. The site that introduced this type of number display to me is the aptly named NumberSpiral.com, which has a great overview that I won't bother summarizing here - best that you read it there. There is lots of playing around that you can do with these spirals (you can plot polygonal numbers on them, and look for other interesting sequences, for example).

frames and octahedrals

2013-04-03T15:13:00.000-07:00

Looking at a polka-dotted shower curtain the other day, I started to play a game of connect the dots. I was looking at "frames" of dots like the ones below, and counting the squares that could be made using only the dots on each frame as vertices.

So, consider an n by n square grid with points at each vertex and points one unit apart around the perimeter For an such a grid, how many squares can be drawn by connecting 4 points on the perimeter of the grid, and what is the total area of all the squares drawn? Read no further if you want to do this yourself.

Counting the squares is pretty straight forward - for an grid with sides length n there will be n squares. There is the full n by n square formed by joining the vertices of the grid, and then a series of smaller rotated squares, the base of each formed by joining the ith point along the bottom with the (n-i)th point along the left side (consider the lower left corner to be the origin (0,0) and count to the right and up).

The areas of these squares are also easy to calculate, thanks to the right triangle that is made by the square and the frame that it is tilted in.

If you add up the areas for a given n, and look at the sequence that you get - you'll find that these give the octahedral numbers (OEIS A005900). A nice surprise (for me at least). Octahedrals are figurate numbers, like like polygonal numbers but in this case three-dimensional: two square-pyramidal numbers (OES A000330) stuck together to form an octahedron.

Figurate numbers have long been a favorite topic in recreational mathematics (there are several posts about them on this blog - like this one), and sometimes they show up when you are not expecting them.

The geometric aspect of figurate numbers sometimes allow you to express numerical relationships nicely using pictures. I don't think the picture below (which shows the n = 3 case) quite qualifies as "a proof without words", but I think it helps to show why the octahedral numbers pop out when you "draw squares on frames."

why stop at four?

2013-03-26T19:29:00.000-07:00

The Ontario Social Studies Curriculum says:

By the end of Grade 2, students will:
– recognize and use pictorial symbols
(e.g., for homes, roads), colour (e.g., blue
line/river), legends, and cardinal directions
(i.e., N, S, E,W) on maps of Canada and
other countries;

I was helping out with some Grade 2 homework the other day, and when it came time to mark the cardinal directions I reached for an old trigonometry text book to show a much more detailed compass rose. Young students can figure out how many points you have each time you sub-divide the compass (4, 8, 16, 32, ...), and the naming conventions for the points also make sense to kids (what's between North and East? North East! What's between North and North East? North North East!).

calculated thought experiment

2013-03-21T16:38:00.001-07:00

I always feel that I come away with something new whenever I read Ludwig Wittgenstein's Remarks on the Foundations of Mathematics - likely because I understood so little on each previous read. In the book, one thing he tries to get at is what we mean by words "mathematics" and "calculation," and in doing so he asks questions that are so basic that they call into question our implicit assumptions about what these words mean. One of these sets of questions ask about whether our mental state and attitude in any way influences whether or not we are actually "doing mathematics."

For example,

"Imagine the geometry of four-dimensional space done with a view to learning about the living conditions of spirits. Does that mean that it is not mathematics?... Could people be imagined, who in their ordinary lives only calculated up to 1000 and kept calculations with higher numbers for mathematical investigations about the world of spirits?"

Does it matter what we think we are doing when we are doing math? As long as we are moving the symbols around correctly does it still count as mathematics?

Elsewhere he asks "What would happen, if we rather often had this: we do a calculation and find it correct; then we do it again and find it isn't right; we believe we overlooked something before - then we go over it again and our second calculation doesn't seem right, and so on. Now should I call this calculating, or not?"

Does calculation require a social convention - if one person performed something once, could it be considered an algorithm? "What about this consensus - doesn't it mean that one human being by himself could not calculate? Well, one human being could at any rate not calculate just once in his life."

Some of the most fascinating thought experiments that Wittgenstein proposed (way back in 1942-1944) were about (what we would now call) computers or "mobile devices":

"Does a calculating machine calculate? Imagine that a calculating machine had come into existence by accident; now someone accidentally presses its knobs (or an animal walks over it) and it calculates the product 25 x 20."

Has any calculation happened in this case? Later he suggests a scenario that now seems quite familiar:

"Imagine that calculating machines occurred in nature, but that people could not pierce their cases. And now suppose that these people use these appliances, say as we use calculation, though of that they know nothing. Thus e.g. they make predictions with the aid of calculating machines, but for them manipulating these queer objects is experimenting. These people lack the concepts which we have, but what takes their place?"

Very (unintentionally) prescient Ludwig! We are actually now living in a reality which closely resembles this thought experiment - and an environment that sounds like the classroom of the future as imagined by Computer Based Math. What will replace current concepts of number once our experience with calculation is mediated entirely by machines whose cases cannot be pierced? And will we even notice that they have been replaced once they are gone?

syllabi old and new

2013-03-03T10:18:00.000-08:00

If you can, please take a moment to look at the syllabus above. Here's a zoom in on one of the flows between third and fourth year:

I was prompted to dig out this pretty relic from my collection of old books after reading about the ongoing efforts to describe the ideal curricular progressions for Common Core State Standards for high school mathematics (via a post by +Raymond Johnson that linked to the Common Core Tools blog).

If you look carefully at the topics, and the emphasis on set theory and logical sequencing, you may be able to guess when this curriculum was in effect (maybe I'll provide the answer in a future post). What will the new CCSS progressions tell us about what we value in mathematics education?

what's the name of that graph

2013-02-15T21:36:00.001-08:00

The Edge, with its deep thoughts and long interviews, seems at odds with typical Internet culture, and yet is representative of a particular type of discourse that could only exist with the Internet - or maybe the conversations like those at the Edge would exist without the net, but most of us would have no access to them.

Content aside, I noticed the graphic above in the promotional material for the new Edge book, This Explains Everything. At first I thought it was a complete graph on 12 vertices (K_12) - which you would think make a nice choice of graphic to represent the fully networked world that the Edge folk themselves exemplify (it has all possible edges).

But if you look again at the image on the graphic (sorry it is small), you'll see that this isn't quite right. It really looks more like this:

This graph is, I think, the sum of the complete graph on eight vertices and the empty graph on four vertices. The sum of two graphs is formed by taking both graphs and connecting the vertices from one graph to all the vertices of the other.

Imperial and Alan

2013-02-15T21:35:00.001-08:00

Almost every day as I walk to work and pass the Imperial Barber Shop I think of Alan Turing.

foiling understanding

2013-02-08T06:31:00.000-08:00

A statement about mathematical understanding in the Common Core State Standards was recently pointed out to me:

One hallmark of mathematical understanding is the ability to justify, in a way appropriate to the student’s mathematical maturity, why a particular mathematical statement is true or where a mathematical rule comes from. There is a world of difference between a student who can summon a mnemonic device to expand a product such as (a + b)(x + y) and a student who can explain where the mnemonic comes from. The student who can explain the rule understands the mathematics, and may have a better chance to succeed at a less familiar task such as expanding (a + b + c)(x + y). Mathematical understanding and procedural skill are equally important, and both are assessable using mathematical tasks of sufficient richness. (CCSS for Mathematics, page 4).

No surprise that FOIL is singled out as the example of school mathematics where procedure trumps understanding. For this particular topic, I think that using generic rectangles to visualize the distributive law is better than relying on mnemonics at all, but I'm sure there are other equally good ways of avoiding the FOIL trap. Generally, whatever the topic, the challenge is to find representations that extend existing understanding rather than applying rules without comprehension.

Posts about generic rectangles are here and here.

hex life and sandpiles

2012-12-05T10:48:00.000-08:00

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:

Any live cell with fewer than two live neighbours dies, as if caused by under-population. (Starvation)
Any live cell with two or three live neighbours lives on to the next generation. (No Change)
Any live cell with more than three live neighbours dies, as if by overcrowding. (Overcrowding)
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):

triskelion spiral

2012-10-22T17:44:00.001-07:00

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:

Borges, Escher, & Origami Tessellations

2012-10-18T08:29:00.002-07:00

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.

hex life

2012-10-12T06:46:00.001-07:00

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:

Any live cell with fewer than two live neighbours dies, as if caused by under-population.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overcrowding.
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.

Generic Rectangles

2012-09-16T08:06:00.001-07:00

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).

a deep dive into the multiplication table

2012-08-16T20:28:00.000-07:00

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.

last-digit sequences

2012-06-24T12:51:00.001-07:00

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 n = 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?

put in one's place

2012-06-14T20:16:00.000-07:00

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.

more simple-yet-complex fractals

2012-06-06T18:40:00.000-07:00

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.

liar-truther accusation graphs

2012-05-31T16:18:00.002-07:00

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.

return to the island of liars and truthers

2012-05-09T16:14:00.001-07:00

This post has the answers to the puzzles in the last post, so you might want to read that one first.

Jeff left a comment suggesting another question that I wish that I had worked into my little story of the islanders, so this late addition was put in as part 5 which you may have missed if you read the post early. Also there was an error in part 3 which meant that although you could solve the puzzle it didn't really work well, so this was fixed also. Sorry for any remaining errors.

Throughout we are assuming usual two valued logic and the law of the excluded middle, which you either believe or you don't (see here).

I seem to remember being stumped the first time that I came across my first liar and truther puzzle. If you are like me and didn't have the insight of how to solve these the first time, once you see how one is done you will still enjoy applying the same method to figuring out the others.

Before going further you may want to look at the problem in the original post.

1. Going to the Village

You can't just ask the islander what village is up ahead: she might be a liar. Instead you have to find a question whose response will (a) give the answer and (b) not depend on whether the islander is a liar or truther. One possilbe question to ask is "Is that your village?" If the answer is yes, you can rest assured that it is the village of the truthers.

A truther answers "yes" if it is the truther village because they are telling the truth, a liar answers "yes" in the same situation because they are lying. A truther answers "no" if it is the liar village because that's the truth, and again the liar would answer "no" because they are lying. Nice, eh?

2. A Bunch of Islanders

This is probably the easiest of the questions, and there are a variety of ways to figure it out. I think the clearest way to see the solutions is to make a truth table, although presenting it this way is probably more work. Our table will have columns A, B, and C representing Alice, Bob, and Carol, but it will also have columns for the statements that Alice (A), Bob (B) and Carol (C) make about each other. Whether A, B, or C is T (truther) or F (liar) must be consistent with the statements made. For example, when Alice says "Bob is a liar" either A=T and B=F or A=F and B=T. Put another way:

Regardless of who the liars and truthers are, they have to be able to make the statements that they make. So, we know we've found a possible solution when all the columns in the truth table that represent these statements are true.

From the table, the only solutions are that either that Bob is a truther and Alice and Carol are liars, or that Bob is the liar and Alice and Carol are truthers.

3. Looking for the Ferry

Now, in my original post I messed up the wording of the puzzle a bit. I have changed it so you might want to check back. You can answer the puzzle in its original wording using the same method as part 5 (below). The change is that Xavier and Yvette are from different villages and don't want to talk about them, and this change in wording forces you to use a different approach.

In the spirit of the first puzzle, you need to implicate the islanders in the question, so that when the liar is lying then this is somehow conjuncted with their answer (negating their false answer). One way of doing this is to ask Xavier "Which way would Yvette tell me to take to get to the ferry?" Whatever Xavier answers, take the other path.

If X is a truther and Y is a liar, X will truthfully reply with what Y would tell you, which would be a lie. If X is a liar and Y is a truther, then X will lie and tell you the path that Y would not have chosen for you.

4. Leaving the Island

Isaac and Jane are giving you a two statement version of the liar paradox. If they are from the island, this can't be resolved (if I then not J, but then not I, etc.). So, these two must be from off the island, and when Isaac says "Jane is a liar" he doesn't mean "Jane is someone whose every statement is false" but rather means something along the lines "Jane sometimes lies" or maybe "don't trust Jane." In any case, probably best not to hang out with these two and instead spend more time with the islanders who are at least consistent.

5. Postscript: on the Ferry

So, how can you always get the right answer out of an islander? You can generalize the method used in question 1 about the village (unless, as in the reformulated question 3 the islander refuses to talk about their village).

Suppose you want to know if a statement A is true or false. You should ask the islander "would someone from your village say that A is true?" If the answer is yes, then you know, no matter whether the islander is a liar or a truther that A is true, but if they answer no, you know that A must be false. This relies on the double negation that will happen when a liar talks about their village.

So, you could ask the captain a question like "would someone from your village say that this is the ferry to the mainland?"

on the island of liars and truthers

2012-05-07T19:42:00.000-07:00

I've been looking at logic puzzles over the last couple of days - my favorites are the ones that involve the Island of Liars and Truthers. These logic puzzles are particularly appealing because they can be thought of as variations and elaborations of the famous liar paradox, known and loved by all.

I've come across these in various places - there are quite a few examples of these on the Internet, but if you just google "liars and truthers" you get lots of hits pertaining to conspiracies, so you have to go one further and google "liars and truthers logic puzzle" or "island of liars and truthers" to find them. I didn't find the ones below in my recent searches (although you might find them ... I didn't search too hard, after getting caught up reading about the melting point of steel, etc.) - they are adapted by memory from other sources that I can't recall - they are not original and variations on them are probably pretty common.

The Island of Liars and Truthers

Preamble

Imagine that you are visiting an island on which there are only two kinds of people (other than yourself): truthers, who always tell the truth, and liars, who always lie. There are two villages - one where all the truthers live, and another where all the liars live. Although they live in separate villages, liars and truthers frequently roam about the island together and generally get along just fine. Talking to islanders is a bit difficult because they all observe the peculiar custom of not answering more than one question in a conversation and generally don't elaborate on any statements they make. Another interesting feature of these islanders is that although outsiders can't distinguish between truthers and liars by how they look, liars and truthers can always tell each other apart.

1. Going to the Village

You are on the island and see a village on the road ahead of you, and you are not sure whether it is the truther village or the liar village. An islander, who may be a liar or a truther, is standing on the side of the road. What one question do you ask her to find out if the village is the truther village or the liar village?

2. A Bunch of Islanders

Leaving the village, you meet a group of three 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." After that, they don't say anything else. Suppose the group consists of one truther and two liars - who's the truther? Now suppose that the group consists of two truthers and one liar - who would the truthers be? Can this group be all truthers or all liars?

3. Looking for the Ferry

You've decided to leave the island and are trying to find the ferry that will take you back to the mainland. There is a fork in the road that splits off in two directions. Two islanders, Xavier and Yvette, are standing at the fork. Xavier and Yvette are from different villages; you don't know who is from the truther village and who is from the liar village, and Xavier and Yvette won't answer questions about their villages. What question do you ask one of them to find out how to get to the ferry?

4. Leaving the Island

At the ferry you meet Isaac and Jane. Isaac and Jane are either both from the island, or else have both just come off the ferry from the mainland. Isaac says "Jane is a liar" and Jane responds "Isaac is telling the truth." Are Isaac and Jane from the island?

5. Postscript: on the Ferry

It's a slow day, and you are the only passenger on the Ferry: it is just you and the captain. As it pulls out into the harbour you realize that you might have boarded the wrong ferry - is this really the boat that is going to the mainland? You can ask the captain, an islander himself, one question to find out.

Update: some answers here, and some discussion about drawing graphs for problems like #2 here.

envelope doodle design family

2012-04-24T18:59:00.000-07:00

I'm still playing with some simple designs and also with the "envelope doodle" of a few posts back. I called it "envelope doodle" because, it's a doodle that I used to do (I think in middle school every time we were given graph paper) and it's made up of a bunch of lines that form the envelope of a curve.

Both the first (the one made of squares at the top of the post) and last (the one below on the right) design look like standard tiles that you might find on any floor. Some family resemblance might be clear, but it is a little surprising that both are stages in the same series.

some simple designs

2012-04-17T20:37:00.000-07:00

The images at the top and bottom of this post were made in Processing and were inspired by some of the exercises from the 1972 book Principles of Two-Dimensional Design by Wucius Wong.

Forty years ago this book introduced a language for thinking and talking about the then emerging world of modern design. Today it could also be a source of exercises in basic programming, particularly well-suited for Processing.

Wong's later book, Principles of Three-Dimensional Design includes really nice examples of geometric sculpture, many based on polyhedral forms.

phyllotaxis multiplication colouring pages

2012-04-05T19:19:00.000-07:00

I thought I would try to make some printable colouring pages of phyllotaxis spirals - thinking that they could be coloured-in using multiplication-table / skip-counting rules to make patterns like the ones shown in the previous post. I've put a two-page pdf here - page one has a spiral with the numbers filled in (as above), and page two has one without numbers (for unfettered colouring).

When colouring these in, you might just shade the multiples of five - and get the picture below.

As you colour, you'll see the spiral pattern formed by the sequence 5, 10, 15, ...

You also can't avoid noticing a radial pattern as the dots seem to line out on spokes pointing out from the center. Take a closer look at that, and you'll see that adjacent numbers on the radial arms always have a difference of 55. Neato! this was something I didn't see when I generated the same pattern via software - using a pencil slows things down a bit and helps you notice things.

I'm wondering what relationships might be found in the patterns that other multiplicative colouring rules produce.

* * *

Postscript: I shouldn't have been surprised! Any time you make a number spiral skip-counting by n with k spokes, the difference along the spokes is going to be nk - in this case, skip counting by 5 and generating 11 spokes gives a radial difference of 55.