What are your favorite puzzles/toys for introducing new mathematical concepts to students? We all know that the Rubik's Cube provides a nice concrete introduction to group theory.  I'm wondering what other similar gadgets are out there that you've found useful for introducing new math to undergraduates and/or advanced high school students.
 A: Replying to Dan Brumleve's recommendation of the card game "Set" as an answer because my comment was exceeding the maximum allowed size.
The card game "Set" is most analogous to playing tic-tac-toe on a 4-dimensional lattice of size $3 \times 3\times 3\times 3$, allowing for lines to wrap around in that 4-space.
As Douglas Zare described it, the "game asks you to recognize lines in affine 4-space over the field with 3 elements."  There are $3^4=81$ cards, with each card showing a design that can be described by 4 attributes, with each attribute containing 3 elements: 3 colors, 3 shapes, 3 levels of shading (outlined, striped, solid), and 3 cardinalities (1,2, or 3).
Twelve cards are initially dealt with players competing to find a grouping of 3 cards such that their attributes are collinear in the 4-d space: either all the same or all different.  Thus each line in affine space can also be described by the vector $v\in ${$-1, 0,+1$}$^4$ (but excluding $\{0\}^4$) and a representative member of that grouping.  Each card can be also be seen as describing a permutation on the group of the 81 cards.
One quick question that comes out of this is

*

*Are 12 cards sufficient to guarantee that the cards dealt contains such a collinear grouping?

The answer to that is no.  If the people playing concur that the 12 cards initally dealt does not contain 3-points in the 4-d lattice that are collinear, then 3 more cards are dealt, etc.

*

*What is the minimum number of cards that must be selected to guarantee that that it contains a collinear group of three?  The answer to that (21) must be one more than the answer to

What is the maximum number of cards that can be played which do not contain a collinear group of three? (ans=20)
The card game misuses the mathematical term "set" in its name and in its directions for playing the game, since it asks the players to yell out "set!" when they find such a collinear grouping in the 4-d lattice.  It should be rightfully called "line", or perhaps most correctly "4-dimensional affine space line over the field with 3 elements".  But yelling that out each time would certainly slow down playing the game. :)
<Link> has an article from the Mathematical Intelligencer about this game by Benjamin Lent Davis, Diane Maclagan and Ravi Vakil.
A: I'm amazed no one mentioned using the Towers of Hanoi to teach recursive thinking and inductive proofs. The question to answer is `what's the minimum number of moves to shift a stack of n disks from the far left to the far right?' 
Wooden models of the tower game can be bought very cheaply here. I love giving this to students to play with as they work out the algorithm then try to write down the inductive proof.
A: Very low-tech - I cut a square out of a piece of cardboard and use it to illustrate the group of symmetries of a square, first day of a group theory course. 
A: The Tangle is a plastic manipulative toy that can be used to introduce students to
knot theory. This is what the Tangle looks like:

Colin Adams has published a book entitled Why Knot: An Introduction to the
Mathematical Theory of Knots with Tangle.
The publisher's blurb says:
"Each copy of Why Knot? is packaged with a plastic manipulative called the Tangle®.
Adams uses the Tangle because 'you can open it up, tie it in a knot and then close it
up again.' The Tangle is the ultimate tool for knot theory because knots are defined
in mathematics as being closed on a loop. Readers use the Tangle to complete the
experiments throughout the brief volume."
The Tangle that is included with the book is much longer than the one shown in the photograph above, so it can be bent to create fairly complicated knots.
A: I don't happen to own a planimeter, but there are simulated ones on the internet.  These use Green's theorem to compute area of a traced curve - you trace out the curve and a gadget mechanically collects the dot products of a fixed vector field and your tangent vector.  If you take your vector field to have constant curl, then the gadget has computed for you the area of a region.  I have demonstrated this to calculus students after teaching them Green's theorem, and they find it impressive, generally.
Here is a link to one: https://www.hpmuseum.org/planim/planimtr.htm#the_applet .  There is a link to a guide which describes how it works, but you may have to work it out yourself, since it's rather terse.
Another classic is to ask them to construct a Mobius strip out of duct tape, and to cut it down the middle, three levels deep (so 1 + 1 + 2 = 4 cuts in all, recording their observations.  This serves as an enticement for vector calculus students to learn topology.
A: I have used Polydrons (triangles,squares, etc. that snap together) to illustrate why there are only 5 platonic solids, to describe their symmetry groups.  They also are useful to describe Euler characteristic.
I have also used Set (as others have mentioned) to give an application of modular arithmetic and ask interesting probability/combinatorics questions, such as: "what is the largest possible number of Set cards that contains no set?"  
You can also use two jump ropes to illustrate the group PSL(2,Z) as in Conway's "rational tangles."  See Conway's lecture on it.
A: Tadashi Tokieda invents and uses a lot of toys to explore some problems in applied mathematics. Some of these toys along with explanations can be see in this youtube link.
He even made a speaking in National Museum of Mathematics this year:

A: A chess board. Preferably with two opposite corners missing.
A: David Bachman has been experimenting with using 3d printing to make models for multivariable calculus. For example, models of the graph of $z = x^2 - y^2$, showing the vertical slices and the level curves.
A: 
I made these ropes with rare earth magnets in the ends for demonstrating knots. The materials (rope, magnets, PVC pipe and glue) are inexpensive. I've used Tangle before to play with knots, but it doesn't tend to move over itself very easily and it can be hard to see at a distance which strand is on top at a crossing.
A: I have not yet experimented this, but I plan to use a hat and a skirt (with bottom larger than top) to illustrate curvature.
A: A few months back we taught a course on curves and surfaces to undergraduates and asked them to slice a bagel into two linked halves as in here. Of course, you need at least two bagels per student since inevitably most of them end up cutting the first bagel into two unlinked pieces.
The 15-tile sliding puzzle (may be a bit outdated by now) is also a good way to introduce permutation groups and even permutations in particular.
And lastly, the game of Sim (not to be confused with sim city) where two players take turns in drawing edges in red and blue on set of 6 vertices. The rule is that if an edge already exists between a and b then one cannot draw another one. The aim is to avoid a triangle in your own colour. It is known that this game always has a winner. Obvious generalizations to more colours and more vertices lead to Ramsey theory. I actually took this route while lecturing to high school kids and they get into it if you start your talk by playing a few games on the blackboard.
A: Tangloids, for understanding spinors.
A: Prof. Pedro Roitmann of University of Brasilia built these wonderful 'multiplying bottles' for teaching some properties of equilateral hyperbolas:

A: The Lights Out game, for the utility of linear algebra over nonobvious fields (here, ${\mathbb F}_2$). It's easy to find on-line versions.
A: I have been using these 3D printed models of quadric surfaces in my multivariable calculus classes. It is perhaps hard to believe at first that the hyperboloid of one sheet is a ruled surface (at least if depicted as it is in the model). But holding the straight edge of a piece of paper up to the model immediately makes it very plausible.

(source: segerman.org) 
A: 
Please forgive me for tooting my own horn, but you might be interested in this link and this link (scroll down to the section "sporadic simple puzzles").  I worked on these puzzles around the same time that I learned about basic group theory, and thinking about them really helped clarify certain ideas (such as group actions, conjugation, and the utility of studying the orders of groups and their elements).  I think they could be quite valuable as teaching aids.
A: Slightly off the mark, however you can build a toy model to accomplish the same objective.
I took my section out of the classroom to a spot not far away when I was a TA for calculus.
There was a domed window with panels on it that curved.  It was a bright day, and we could see the shadow below.  I used this as a model to demonstrate the need for a Jacobian in doing multivariate change of variables in integration.  I probably could have drawn on a balloon for a pedagogical equivalent, but I thought it was good for the section to walk to an example.
Gerhard "Ask Me About System Design" Paseman, 2010.08.14
A: The late Bernard Scott, founding professor of the Mathematics department of the University of Sussex, had two toys that I remember. One was a pair of pajamas with stripes going down the legs, with the bottoms of the legs sewn together so that the stripes matched up. By pulling the waist-cord tight a torus is obtained, with stripes going round. But when you turn the torus inside out, by loostening the waist-cord and reaching in and pulling and then retightening, you find that the stripes now go round the other way.
The other toy was a pair of small solid cylinders. Each weighed the same (easily demonstrated in a balance). Each had the same external dimensions. Each was made from homogeneous material, but one of them was hollow
(so it was made of denser material). The student was asked to demonstrate which was hollow by suggesting a physical experiment. The problem was intended to discover whether the student understood the concept of moment of inertia. The answer was to roll both cylinders down an inclined plane and explain the differing behaviours.
A: I enjoyed playing the card game Set. http://www.setgame.com/set/index.html (Wayback Machine)
Wikipedia: Set (card game)
