Thursday, September 6, 2007

Skolem-Langford Series Puzzle!

Years ago when I first started doing SNAP Math Fairs with my students, I was always looking for great problems/puzzles to assign. Any problem that is presented on paper but is easier to solve using hands-on pieces, is perfect for math fair. One book I used endlessly was a book by Ivan Moscovich called 1000 Playthinks. For my first fair, which was with an entire school of 120 students from grades k-12, besides using Ted Lewis' Math Fair Booklet, the rest of my puzzles came from either Ivan's book or the puzzles.com website! So my students were given lots of Playthinks! I love this book. (as an aside, I hope to meet Ivan Moscovich at the next Gathering. I am told he attends this event, Wow! that will be a thrill!)
Well, one of my favourite puzzles is this one, Playthink #255:


So I assigned this Playthink to two girls both named Meghan (and Megan). Meghan's parents owned a glass factory so their project was spectacular! Made of Plexiglass! The girls enjoyed making it and trying to figure out a solution! Here are some shots of their very beautiful project! I have taken this to conferences, along with many other projects from math fair, to show as examples of what a project could look like. This particular project always gained some attention as mathematics professors I knew would start to analysis its properties. I loved this most!

These girls were in grade 8 at the time! Job well done! Their main focus on this project was to find a solution to the puzzle. I wish I had steered them also in the direction of investigating the math behind it as well. At the time, I didn't know about the Skolem-Langford series. Maybe I should write a book about great hands-on puzzles that also include the great math behind them! (like Towers of Hanoi, pythagorean triples, triangular numbers, etc..) This would be cool to do both at the elementary level and the secondary level. There's more power in learning mathematics when there's a hands-on investigation as well. They simply retain it better! I could go on, but I digress!

One of the challenges in math fairs, is that the girls had to think of a way to make this problem accessible to younger children. (we were a k-12 school remember!) So they cleverly created an easier level where you were allowed to cross the semicircles. This still proved to be challenging however easier than this solution shown where semicircles are not crossing.
Well, you can imagine my surprise and absolute pleasure when at the IPP exchange this year I was George's assistant and his puzzle was similar in 3D and then he told me about Stan Isaac's puzzle which was 2D. With permission from Stan, here below is his puzzle. You can see it has 12 semicircles whereas the girls project had 8.

Stan told me his puzzle was suggested by Donald Knuth. (Martin speaks very highly of Donald Knuth, another brilliant mind I'd like to meet someday.) The puzzle is called Rainbones. Here is what Stan says about it,

"Mine was suggested by Don Knuth, who was studying Langford sequences, which looks at what numbers can be arranged the way RainBones forces. That is, sequences of digits where each digit, 'k', is separated from a second 'k' by exactly 'k' other digits. There are many variations, for instance using 3 copies of each digit, or not starting with "1", or using any set of digit pairs, not just in sequence. There are lots of math papers on these numbers, sometimes called Skolem-Langford (Langford stated the original problem, which he got from looking at his child's colored blocks; Skolem did some mathematics, but subtracted the two number positions instead of looking at the number of spaces between them, so he would call the distance between the first two numbers "1", where Langford would say "0"."

Here is Donald Knuth's (Ka-nooth) link:

http://www-cs-faculty.stanford.edu/~knuth/

Stan also wrote to me the following:

"When you allow the semicircles to cross, you get the original Langford problem. (If you look carefully at the picture of me from IPP that you posted, you can see a small linear puzzle with dots in it. It's another version of the original Langford problem, using plastic strips instead of semicircles. That particular example uses 7 pairs instead of the 8 in PlayThinks or 12 in RainBones.)

Allowing crossing, there are solutions for any number either divisible by 4 or when the next number is divisible by 4 -- that is, it is solvable by 3, 4, 7, 8, 11, 12, ... but not by the other numbers. For the Skolem version (which is the one in PlayThinks) I'm not sure which numbers work, but (since you can put the smallest piece, the one I think of as "0", at the end of any Langford solution), I think there are more solutions than Langford. Notice that if you don't allow crossings, you get my puzzle (which has fewer solutions than when you allow crossings), and if you don't allow crossings, but do allow not only hanging from either side of the line, but also in 2 other directions, you have George Miller's U-Tube. There also exists a version made by someone in France many years ago, which allows 5 directions (that is, it goes around a pentagonal core, but is otherwise much like Georges). "

So below, with George's permission, is his puzzle from IPP called U Tube. Its very similar to the ones above however you have four sides of the rectangular prism (tower) with 16 holes cut out on each side. You have 8 "U" pieces that must fit around the tower, however, once a hole is used on one side, it cannot be used on any other side. You have to find a way that all 8 U pieces fit on the tower.




It was fun being George's assistant on this. You should have heard all the different ways he explained how to do the puzzle when he was exchanging with other IPPers. It was hilarious. He kept coming up with different analogies! And it was interesting, no matter what nationality the person was who he explained his puzzle to, they all knew what You Tube was! It was fascinating!

So I had to share this story with you because it is amazing how this has grown with me over the years! And now I have 3 different variations of it in my collection. I want to try to dissect the math in it much more. Now, I need to find the one in 5 directions with a pentagonal core that Stan mentioned!

Any ideas?

No comments: