Saturday, February 11, 2017

fibonacci foolery

Some misleading dissections

Consider a square whose sides are 5 units in length. We are going to dissect the square by cutting it as shown below.  We can then re-arrange the pieces to form a rectangle.

But wait, the square has area 5 * 5 = 25, while the rectangle has area 8 * 3 = 24... somewhere we lost one square unit. This paradoxical result tells us that something is wrong, but what is it?

Let's look at another very similar dissection, this time using a square with sides length 8 units, sliced up and re-assembled in a similar way:

Here the square has area 8 * 8 = 64, but the rectangle has area 13 * 5 = 65. In this case we have gained one square unit (maybe borrowed from puzzle above?).

In both cases, the discrepancy in the areas tells us that we are doing something illegal when we re-assemble the square into the rectangle. You can see where the problem is if you look at the triangles within the rectangles. Consider the first problem, where we split up the length 5 into lengths 2 and 3. Can we really put those pieces together? Apparently not - if we try to fit one of the triangles and quadrilaterals pieces together, we find that they don't actually form a right-triangle - the hypotenuse is not straight, it bumps out a bit:

In the (2,3,5) problem, if the figure did line up properly, the large triangle with base 8 and height 3 would be similar to the smaller triangle with base 5 and height 2. This would mean that 2/5 equals 3/8, which is not true. If we place the original triangle of base on top of the larger triangle, the pieces would not line up:

The Fibonacci connection

You may have noticed something familiar in the numbers used in the dissections above. Both triples (2, 3, 5), used in the first dissection, and (3, 5, 8), used in the second, are successive terms in the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, ..

The Fibonacci sequence is defined recursively by:

Can we construct another misleading dissection using the next Fibonacci triple (5, 8, 13)? Let's see:

Our square in this case has area 13 * 13 = 169, while our rectangle has area 21 * 8 = 168. So we are back to losing a square unit when we re-assemble the dissected square into the rectangle.

It turns out that Fibonacci triples like these will always generate these "off by one" illusions, because three successive terms in the Fibonacci sequence always obey the Cassini identity, which expresses the situation shown in these diagrams: if you have a Fibonacci triple (a, b, c), then the product of a times c is going to be either one more or one less than the square of b. More precisely, Cassini tells us:

The Cassini identity can be proved in a variety of ways, including induction. For n = 1, we have 0*1-1 = -1, so the identity is satisfied.  If we assume the relationship holds for n = - 1, we can prove the n = k case as follows:

See some more proofs of the Cassini identity here.

A Golden Solution

This dissection and re-assembly of the square into a rectangle looks like a nice one, and we'd like to find a case where it works: we want to find where to cut so that the square pieces fit correctly into the rectangle and the areas of the figures match up. Clearly basing the cut on the Fibonacci numbers won't work...

Let's start with a square whose sides are length 1. We would like to find two numbers a and b such that we can perform the dissection and assembly as shown below.

What we would like is the area of the rectangle to equal that of the square:

And taking the positive solution from the quadratic formula, we get:

We used the capital Greek letter Phi here because this quantity is known as the golden ratio conjugate, making the base of our rectangle, 1 + b, equal to the golden ratio.

This is a nice surprise because of the close association between Fibonacci numbers and the golden ratio  -  the quotient of consecutive Fibonacci numbers becomes closer and closer to the golden ratio as the Fibonacci numbers get larger.

So, while using Fibonacci numbers in the dissection always yields nice deceptions which alternate between gaining and loosing a square unit, slicing the square using the golden ratio (or golden ratio conjugate) gives us a perfect re-assembly of the square into a rectangle.

Sunday, January 29, 2017

build your own knight's tour

A couple of posts back I mentioned some knight and king's tour puzzles that I had put together (knights here, kings here). I've added another page based on the same underlying framework where you can build your own knight's tour.

You start off with something like this:

Green squares indicate a legal move, and the numbers on each square tell you how many open moves are available from that square.

Visited squares are marked with a check, and a map of your path is traced on the image below the board.

The "Warnsdorff" heuristic for finding a tour is to always move to a square with the lowest number of available moves. This heuristic works well - it often leads you to a successfully completed tours. You can try this approach, or experiment with others. In the example above, following this method presents you with two choices initially (moving to one of the two squares with 2 open neighbours), but at the third move leaves you with only one option.

Whatever approach you take, if you feel you've made a wrong move, or find that you are completely blocked, hit the "backtrack" button to move back one step.

Some older posts on knight tours:
Knight Moves
Closing Time
Punctured Tours

Wednesday, January 18, 2017

a julia and mandelbrot fractals page

A Julia dendrite

A few years back, I posted about generating my first image of a Mandelbrot set using Processing. I decided to do it again, mostly to get some more JavaScript practice. So now a page that generates some Mandelbrot and Julia set fractals is available here.

AnotherJulia set fractal

The fractals are generated almost exactly as described in that earlier post. The only difference is the JavasScript and HTML infrastructure. Source is here for the curious.

Friday, December 23, 2016

life lessons from a knight's tour

Please check out these interactive puzzles: kixote (knight's tour) puzzles, and hidato (king's tour) puzzles.

Both are based on the idea of a solitary chess piece roaming around an otherwise empty board. A "tour" is completed if the piece touches every square exactly once.

Solving these puzzles involves revealing the hidden steps in the correct order to complete the tour. For example, in the kixote puzzle below, the first step in the tour is highlighted.

We need to find the second step in this tour. Based on how knights move, there are two options: the cell to the right of 19, and the cell to the left of 57. Looking at where the third step is (third cell down in the last column), we realise that the cell next to 19 must be number 2. Clicking on that, we unlock the next few steps in the tour:

Now at step 4, we need to find step 5, and to do that, we look at where step 6 is... and continue in that way until all the steps are revealed.

If you try this a few times, you may notice that although each tour is different, they tend to follow a familiar pattern of cycling around the edge of the board in their early stages, sometimes hopping around in the corners before moving along:

The tours look like this because of the technique used to generate them: the puzzle generator is not randomly selecting which square to move to, if it did this, it might take a long time to come up with a proper tour for you to solve. Instead of randomly selecting each move, the generator is using a heuristic to pick squares that will most likely lead to a completed tour.

To a knight, an empty chessboard looks something like this:
knight's graph

Two cells are connected if the knight can jump from one to the other. Some cells are better connected than others. The image below shows the number of connected neighbours for each cell:

The rule used by the tour generator is to always select a reachable cell that has the fewest free neighbours. This leads us towards the edges and into the corners, leaving the wide-open and accessible centre for the end. Obviously, this is not the only strategy that will work: every knight's tour is reversible, so each path which starts on the edges and corners could be flipped to produce a tour that starts at the centre. But the "start with the least open cells" is a strategy that works well, frequently producing complete tours.

Maybe there is some lesson here for many tasks: when faced with a list of things to be completed, start with the less attractive options first, and save the best until last.

Tuesday, November 29, 2016

polynomial grid division examples

There are not enough examples of polynomial division using the grid method out there. To remedy that, I have posted about 100 billion examples for your viewing pleasure. Please check ‘em out:

Jokes aside, I was looking for a small JavaScript project, and this one looked like it would be fun. It was, and I learned a few things by building it. The page will generate a small number of examples, but you can get a fresh batch by reloading. Each example is calculated on the fly, and rendered using MathJax. Currently, the displayed calculations look like this:

About half the time the examples have remainders, and the calculations vary in length and complexity in no particular order, so if you get a crop of examples that look too intimidating, or too easy, just keep trying and you should get ones more to your liking. If you see one you like, you should copy it down: you may never see it again.

I have plans to make the examples configurable and to show each part of the calculation step by step, but I may not get around to doing that for a while.

Please let me know if you get some use out of this page, particularly if you run into any trouble with it. 

Overviews of how to carry out the grid method, also called the generic rectangle method or the reverse tabular method, can be found here and here. The page does not currently provide any ‘backwards reverse tabular’ calculations, as described here.

Update: The page now allows you to choose if you want remainders or not, and does try to show some of the steps in the calculation.