Thursday, June 30, 2011

kixote, or knight's path puzzles

If you can make puzzles out of king's tours, why not try to do the same with knight's tours? Here is a first attempt. Remember, a knight moves this way:

So, the goal of these puzzles is to complete a "knight's tour" of the board, honoring the numbers that have already been filled in. The types of boards that you can use for a knight's tour are much more limited than those you can use for a king's tour. The two puzzles in this post are based on a 5x6 board (as in "quick chess" if you have ever played that).

First draft of "kixote" instructions: Fill in the missing numbers so that when followed in order they form a "knight's path" around the grid, where each square is visited exactly once. A knight is a chess piece that follows an L-shaped path, moving in one of these ways: (a) two steps vertically followed by one step horizontally, or (b) two steps horizontally followed by one step vertically.

Kixote Puzzle A

Kixote Puzzle B

OK, but what about the silly name "kixote"? Well, it's clear that any number puzzle has to have a three syllable name that sounds vaguely Japanese, and this one should have something to do with knights that roam around

It seems that one way to make a puzzle is to start with a problem and its solution, and then hide part of the solution. Finding the solution to the problem is now just a puzzle, since some of it is right there in front of you. In this case, the original problem is finding a knight's tour - the puzzle is generated by taking some particular solution and hiding some of it. To be a well-formed puzzle, you should only be able to obtain the original solution, not several other solutions that just match on their exposed parts. Making sure that the puzzle is well-formed either takes good puzzle-making skills, or good puzzle-checking algorithms. Right now, I have neither - please let me know if these puzzles work or not.

Update: the solutions to the puzzles in this post are here.

Tuesday, June 28, 2011

Hidato, or a king's tour

I picked up a logic puzzle book on the weekend and learned of Hidato puzzles - a type of number puzzle that was developed (recently, I think) by Gyora Benedek. This appealing genre of puzzle was, according to Benedek, inspired by trying to follow the path taken by small fish as they darted through a coral reef.

In a Hidato puzzle you are given an n-celled grid where some cells contain numbers while others are left blank. Your task is to fill in the blanks so that the numbers form a the consecutive series from 1 to n. Cells are considered adjacent if they are touching edges or corners. Another way to think of the puzzle is to imagine moving along the grid while trying to fill in the numbers 1 to n in order - you are allowed to move one square at a time either horizontally, vertically, or diagonally.

Just as Sudoku are latin squares with missing values, so the Hidato are really king's tours in disguise. A chess king can move one cell in any direction, and a king's tour is a complete covering of the chessboard where each square is visited exactly once (a hamiltonian path on the king's tour graph). As with knight tours, a king's tour can be open (if the final square is not adjacent to the start) or closed (if you are one move away from the beginning when you get to the end). Below is an example of an open king's tour on standard 64 cell chess board.

A solved Hidato is a completed king's tour since it is played on a chess-like grid and the Hidato moves are precisely those which a king is allowed. Whether by accident or design, the Hidato puzzles I've seen so far are not 8x8 boards like in standard chess - I've seen 6x6, 7x7 and a variety of rectangular and odd-shaped boards.

Here are two not-too-hard Hidato-inspired king's tour puzzles (note that I am not calling them Hidato - that's a trade mark... they are "king's tour puzzles") on a 5x5 board (the solutions at the bottom of this post). These puzzles were created by first creating a king's tour and then only labeling some of the cells - hopefully enough to guarantee the uniqueness of the solution.

King's Tour Puzzle A 

King's Tour Puzzle B

You can generate king's tours using the same algorithm as used for knight's tours. You can also use the same knight-tour techniques to transform an open king's tour into a closed king's tour.  The "king's graph" is much more connected than the knight's graph, so tours are much easier to generate (and close). The interior cells have 8 neighbours, with cells at the edges and corners with 5 and 3, respectively.

If you picture the board as a graph, kings have a lot more edges to travel along than knights do.Interestingly, the sequence, 6, 20, 42, 72, 110,... (A002943) gives the number of edges in a king's graph for an n+1 by n+1 board, and this sequence shows up as a diagonal in the Ulam number spiral of a few posts back.

Here are solutions to the small king-tour puzzles above.

Puzzle A Solution

Puzzle B Solution

Update: I have put up a page that generates playable Hidato puzzles here.

Friday, June 24, 2011

graph paper collection 1

Neat graph-paper variants are easy to come by, but I decided to pull together some collections that lend themselves to certain geometrically-inspired math doodling. The first collection includes isometric dot paper,  tumbling block paper, and some detached square paper - all generated at (what a name!).

Isometric dot paper is now a staple of middle-school math (I only first saw it a few years ago though).

Tumbling block paper is a quasi-regular rhombic tiling that's really just the isometric paper with the dots connected in a certain way.

One of the things that the "detached square" paper helps you draw are overlapping columns that look like the Penrose impossible staircase.

 The graph paper and other stuff from this blog can be found here.

Tuesday, June 7, 2011

jump math

I attended a JUMP-math presentation last week - here are some of my notes. JUMP is a Canadian charity that produces mathematics teaching and learning resources for grades 1-8. It was founded by John Mighton, a very interesting guy.

Some things that I've learned about JUMP:

1. JUMP provides resources for the classroom teacher that are grounded in a very positive and research-based philosophy for mathematics education. JUMP 1-8 resources line up with the  Ontario Curriculum (and the Western Curriculum, and to a lesser extent, the Atlantic Curriculum). I can't really do the JUMP approach justice in this note, but I'll try to highlight a few reasons why I am impressed with it below.

2. JUMP  has been by adopted in various schools throughout Canada and around the world. JUMP should be more widely adopted in Ontario public schools, but currently it is not. I think there are three key reasons for this: a) its history; b) its charity status; c) some misunderstandings about its methods.

3. The various JUMP resources that are available include: (1) JUMP teacher-resources are available online for free at their website. You have to register to get these because JUMP has to track who is using its materials as part of its charity designation. (2) You can order the JUMP workbooks from here also (these will cost you) - these are intended to be used along with the teacher resources. (3) There are also 'JUMP at home' books which are available from book stores and are based on materials that have been licensed from JUMP.

4. John Mighton, JUMP's founder strongly believes that no one has an innate inability that prevents them from learning and enjoying mathematics. I agree, and I think sharing this assumption is a necessary starting point for anyone involved in teaching math to young people.

A bit more context: 

JUMP, having started as a tutoring program founded by an education-industry outsider is not always understood to be a complete classroom program, which it now is. Its charity status means that it threatens the big industry text-book publishers who, while promoting their own (for-profit) texts and resources, likely do their best to block JUMP from gaining any ground. JUMP's charity status has led it to adopt a business model where it offers its teacher-resources for free, and recoups costs through printing and selling workbooks (which they claim are not even necessary - the teacher resources are the main part of the program). As a charity, JUMP has not joined the text-book publishing business, and because it does not publish a bound textbook it is not fully sanctioned by Ontario's Trillium List. In addition to these barriers, JUMP has often been misunderstood, and sometimes misrepresented by its proponents, as a "back to basics" approach that is somehow at odds with current approaches in math education.

Seeing JUMP as "back to basics / skill and drill" approach to mathematics misunderstands its approach at a fundamental level. This misunderstanding has developed in part because of the workbooks (which at a quick glance look like a bunch of worksheets), and because JUMP is very task-oriented. Folks from JUMP take pains to point out that it does not emphasize drill, but instead "guided exploration" and "micro-inquiry" - the workbooks are supplementary, and shouldn't be looked at out of context from the teacher resources. Although the teacher is called up on to explicitly teach concepts, the lessons are set up so that students are continuously working on tasks, providing many opportunities for formative evaluation and feedback.

In this approach, numeracy is developed through careful and precise attention to details - nothing is glossed over or assumed. This shows an appreciation both for the underlying mathematics and for difficulties learners can face. Nothing is ever presented as "this is how it is done, just memorize the algorithm." For example, the development of the standard long-division algorithm in grade 5 is extremely well done, with great use of base-10 blocks, and constant references to the way "sharing" concepts were modeled in earlier lessons. Going through this helped me understand long-division better. :)

There should not be a trade-off between skill-mastery and creativity in mathematics. According to the JUMP philosophy, strong skills, factual knowledge, and confidence open up possibilities for creativity and risk-taking. They a pre-requisite for problem solving - you can't do higher-order work if you are mired in calculation difficulties and lack the confidence to experiment.

There are lots of informational/promotional videos about JUMP on their youtube channel, and also an extended interview with John Mighton on the TVO site.

Thursday, June 2, 2011

sequences on a spiral

Question 28 of Project Euler has us looking at number spirals. Put the number 1 in the middle of a piece of graph paper and start writing the natural numbers as a square spiral moving outwards from the center. Here is a Tinkerplots file (used to make the pictures in this post) for a spiral with sides length 99 (and a plaintext file, and a smaller a Fathom file). If you begin looking at the spiral, you'll likely find a number of sequences that you can learn more about from the Online Encyclopedia of Integer Sequences.

The numbers on the main upwards diagonal, taken in the order you find them walking on the spiral, are "Hogben's central polygonal numbers," 1, 3, 7, 13, 21, 31, 43, ... (OEIS A002061), although I don't know what makes them polygonal (more on this on a page by Robert Munafo).

If you start summing this diagonal as you walk around, you get a sequence 1, 4, 11, 24, 45, 76, 119, ..., (OEIS A006527) where every number turns out to be the sum of two tetrahedral numbers (a tetrahedral number and one two indexes behind it).

The numbers on the main downwards diagonal (1, 5, 9, 17, 25, 37, 49, 65, ...) provide another sequence that appears in the OEIS as A080335.

Instead of looking for sequences on the features of the square, you can mark off known sequences on the spiral and see what they look like. I tried this with some polygonal numbers, and found that they (not to surprisingly) form spiral patterns much like they do when plotted on the round number spiral. Below are some pictures of the triangular numbers (OEIS A000217) and the heptagonal numbers (OEIS A000566).

The sequence plot that made this square spiral famous is that of the prime numbers - when you plot the primes on this square spiral you get what is called the Ulam prime spiral. Certain surprising local regularities emerge in parts of the spiral that are best seen if you make it big enough.

What is most noticeable when you plot the primes on the number spiral are the places where primes seem to line up along various diagonals. These clusters indicate the existence of prime-generating quadratics.