- It's been more than 18 months since I last mentioned one of my favorite
unsolved combinatorial puzzles in the recipe for Nov. 21-27, 1984,
so I'll repeat it here. As explained earlier, the problem concerns invariant finitite
configurations, known as stable periodic objects (SPOs), for Moore
neighborhood, threshold 2 excitable cellular automata. But the puzzle can
be formulated quite simply without any reference to the associated
dynamics.
- Namely, supposing that N colors are arranged in a cyclic color
wheel, is it possible to paint a finite collection of sites in the
two-dimensional integer lattice so that each site of a given color
sees at least 2 of its 8 nearest neighbors with the preceding color from
the wheel? It is not hard to design examples for N up to 5 with pencil and
graph paper. N = 6 is more of a challenge; try it! This week's soup is an SPO for
N = 7 designed a few years ago by Dan Pritikin, a combinatorist now at Miami of Ohio.
It reminds me of a pagoda at least as much as Ursa Major suggests a bear. The frame around
the image specifies the cyclic palette arrangement if anyone wants to verify
the solution by hand. (A more sensible alternative is to use our
WinCA software to check invariance under range 1 Box, threshold 2,
7 color Greenberg-Hastings dynamics.) Get the experiment
dan7.xpt and initial bitmap
dan7.bmp to watch the pagoda's
evolution.
- Remarkably, Pritikin went on to find exotic SPOs for 8, 9 and 10 colors, this last being
featured in our recipe a year and a half ago. Get
dan10.bmp to
meet the record holder since there is still no known example with 11 or
more colors. In contrast to Dan's 10-color giant, which sends out waves in
four directions under GH dynamics, the pagoda is content to shimmer. For anyone
with a combinatorial bent who would like to make new progress on this
problem, I suggest that the most 'doable' and interesting result at this
point would be to show there are no examples once N is sufficiently large.
That seems to be the conjecture of most folks who have thought about the issue.
Whatever methods might establish the existence of a finite maximal number of possible colors
would undoubtedly yield dividends for other chapters in excitable CA theory.
|
