# Placing Chain Of Colored Links Into A Grid

Leroy Quet qq-quet at mindspring.com
Wed Nov 5 03:49:16 CET 2003

```[I had thought I had sent the below, which I posted to sci.math in
mid-October, to seq.fan already, but it is not in my in-box from this
group. If I have already sent it to you all, then I apologize.]

So, there were never any replies to any of my questions (which were
poorly asked, in any case) anyhow.  I will send the post to seq.fan
because of the possible sequences that might result from specific cases
of the below (such as the number of possible placements when the chain is
colored according to some predetermined rule).

----

Let us say we have a loop of chain (or we have a necklace) of m^2

Now, we take a m-by-m grid, over which we can place the chain so that
each square contains exactly one link.
(m is even.)

How many ways can we expect to be able place the chain so that no
similar colors are in any immediately adjacent (up/left/down/right)
squares?

(Of course, the exact number varies according to how the links are
colored. I guess I am just wishing for some analysis on this. Perhaps
the number is exactly determined or approximated asymptotically based
on some statistic of how the chain is colored.)

And what would the number be in the range of, if the chain need not be
a loop?
(m may be either odd or even, in this case.)

This question was directly inspired by this puzzle from way back:

I wonder if I can get any idea if any such maze has multiple solutions
(after rotation/reflection), and if so, what would the magnitude of
this number of solutions be.

thanks,
Leroy Quet

```