This is the solution to the Snakes on a Plane puzzle.
Eight snakes can satisfy the requirements, as shown here:
Here's a proof that it can't be done with fewer than eight snakes.
Snakes can be classified two ways: those that touch tails with their snouts, and those that touch middles with their snouts. Let's call them green and black, respectively. It can quickly be seen that green snakes only touch black snakes and vice versa. Thus we need equal numbers of green and black snakes, and since one green snake must touch 3 others, we're going to need at least 3 of each.
A solution with 6 snakes would involve 3 green and 3 black, with every green snake touching every black snake. The fact that this must be done on a plane with no overlaps makes it equivalent to the famous 3 utilities puzzle, and therefore impossible. So it can't be done with 3 snakes of each color, and we need at least 4 of each color. Therefore, the solution can't have fewer than 8 snakes.
In graph theory terms, the snakes must form a planar, cubic, bipartite graph. The only cubic, bipartite graph of order 6 is the utility graph, K3,3, which is nonplanar. The only cubic, planar, bipartite graph of order 8 is the cubical graph, which the above pictured solution is isomorphic to.
[ Front page | About/contact | Copyright waived | Valid HTML ]