Given a finite family of polyominoes (of any sizes), is the set of the polyominoes that do NOT contain any...

No solution was found in the collected postings.

[ Editor: what follows is Yann David's summary of the replies,
  January 1997, which says the main question was not settled. ]

We did not come up with any definite solution, but there were some
very interesting hints towards a plausible solution.

The problem was suggested by "Winning Ways" (Berlekamp, Conway & Guy),
volume 2, page 684 -they exhibit a finite family of polyominoes that
are distinguished by the fact that they do not contain any member of
another finite family of polyominoes.

All I have found out so far is the pretty obvious fact that the set of
the polyominoes which do not contain any instance of the "target"
family is finite if and only if there is a generation of polyominoes
(all the polyominoes of a given size) such that every member of the
generation contains at least one member of the family.  All subsequent
generations share, of course, the same property.  The problem can then
be restated in terms of finding the order of a "critic" generation,
given a target family (one would have "only" to test every member of
the critic generation - does it contain any member of the target
family? that question is NOT difficult - so as to decide whether the
non-containing set is finite or not.

-- Yann David

Wei-Hwa Huang wrote:

>I don't know about the the problem, but if it is true, it would sound
>very similar to Sylvester's Theorem and make a darned good variation
>of Sylver Coinage.
>
>Sylvester's Theorem (in this case; he had a lot of other theorems)
>says that given any two relatively prime positive integers, only
>a finite number of positive integers cannot be expressed as a sum
>of non-negative multiples of these two integers.
>
>For instance, all integers greater than 100 can be expressed as
>some non-negative multiple of 9 plus some non-negative multiple of
>10.
>
>In Winning Ways the game Sylver Coinage is introduced; basically,
>two people alternate saying positive integers, where you cannot say
>any integers that can be expressed as a sum of non-negative multiples
>of all the integers previously said.
>
>The person who says 1 loses.
>
>You can see the similarity between your game and Sylver Coinage, I
>hope.

Dan Hoey wrote:

>The word "polyomino" is the more widely-used term, or "n-omino" for
>what you call "generation n".
>
>I haven't heard of your problem before, even of it being posed.  I'll
>have a look at _Winning Ways_.  Do you know of any other references?

I answered:

You won't find a clear statement of that problem in _Winning Ways_,
it is just hinted at there.  I don't know of any other reference, but
such a simple problem must have been posed in some book or article
already.

He wrote:

>Now that I've looked it up, I see.  One thing I see is that the
>problem is very close to the "unavoidable subgraph" problem that was
>used in solving the four-color theorem.  We ask whether given a finite
>set of graphs H and an infinite set of graphs G, whether all but
>finitely many elements of G have an element of H as subgraph.  In that
>general setting, I'm almost certain it's undecidable.  I don't know if
>there's any way to make it easier by using the fact that G is a
>representation of the polyominoes.
>
>While looking it up, I ran across the Sprouts discussion, and the
>FTOZOM.  It looks surprisingly like another instance of the same
>problem.

David Moews made, in my opinion, the most interesting contribution.
He wrote:

>Given any polyomino P, let G(P) be the (connected) graph obtained from
>P by placing a vertex at each square of P and joining two vertices iff
>their squares are neighboring.  Call P a snake if G(P) is a path.  Now
>we can restrict our attention to snakes, in the sense that
>
>   given a family S, the set of polyominoes not containing any member
>   of S is finite iff the set of snakes not containing any snake member
>   of S is finite.
>
>The left-to-right implication is obvious, since no snake can contain a
>non-snake.  For the right-to-left implication, if there are infinitely
>many polyominoes not containing any member of S, then there must be
>polyominoes of arbitrarily large size not containing any member of S,
>and we can trim these polyominoes down to arbitrarily long snakes which
>cannot contain any snake member of S.
>
>We can code snakes by strings: e.g., given a snake
>
>                      ***
>                    *** **
>                    *
>
>we can code it as *AB*CD*CD*AB*CD*CD*BA*CD*, writing a * for each
>square, AB for a move up, BA for a move down, CD for a move right, and
>DC for a move left.  With this code each snake has exactly 2
>representations which are reversals of each other (depending on which
>end you start from,) and snake X contains snake Y just when Y's string
>is a substring of X's string or the reversal of X's string.
>Unfortunately this does not reduce the problem to the corresponding
>problem about strings (which would be decidable) because there are
>many strings which look very much like snakes but are not, owing to
>self-intersection, e.g., *AB*AB*CD*CD*BA*BA*DC*DC*.
>
>|...
>|Notice that the reverse problem is quite entertaining too: given a
>|finite family of poliminoes, is there any other finite family such
>|that the first one is the family of all those that do not contain any
>|member of the second one?
>
>Obviously, the first family has to be closed under downwards
>inclusion.  Given that it is, and that the maximal order of polyomino
>present in the first family is N, we can let the second set contain
>all polyominoes of order <=N+1 not present in the first.

As I asked why the string problem he stated was decidable, he answered:

>If we have a set S of strings over some alphabet, e.g., {ABC, CCC, CB}
>over the alphabet {A, B, C}, it's easy to write down a regular
>expression that recognizes all strings containing some member of S (in
>this case,
>
>      ((A|B|C)*ABC(A|B|C)*)|((A|B|C)*CCC(A|B|C)*)|((A|B|C)*CB(A|B|C)*).)
>
>Now it's known that the languages recognized by regular expressions
>are the same (and in fact, effectively the same) as those recognized
>by finite automata; but it's easy to complement the language
>recognized by a finite automaton (just complement the set of accepting
>states.)  Hence we can also write down a regular expression that
>recognizes the set of all strings not containing some member of S.
>Then all we have to do is decide whether this expression recognizes
>infinitely many strings.  This is easy since it recognizes infinitely
>many strings iff it contains a nonempty expression followed by *.
>
>An alternate proof: let the maximal word length occurring in S be m.
>Start at the empty word, and begin producing a tree of words not
>containing any member of S by adding all possible characters at the
>end of the word.  If the set of words excluding S is finite, we will
>eventually stop and realize this.  If not, a node W will eventually
>occur in the tree such that an ancestor V of W has the same last m
>characters as W [Editor: "as V" in the original].  Then if we write
>W=VQ, {V, W=VQ, VQQ, VQQQ, VQQQQ, ...} is an infinite set of words
>excluding S.
>
>I am sure there are much better algorithms available.

I first thought his second algorithm was transposable to polyominoes:

It looks to me like your tree algorithm for strings works just fine
when applied to snakes, resorting to some string representation of
them - the one you introduced, or more simply we can denote the moves
by E, N, W, S and the nodes by *.  When examining whether a snake (A)
contains another one (B), we have to take into account several
representations of B - depending on the geometrical transformations
that map a snake onto an equivalent one (we may retain translations
and/or rotations and/or reflexions), and for each position there are
two descriptions, one starting at each end of the snake.  The same
transformations should be considered while developping the snake
tree :) Anyway, these are only details which are easily managed, my
point is that the key idea of the algorithm remains valid; in short:
developping the tree until it can't be developped any more - it is
finite - OR we run accross some node w such that w=vquq and vq is an
ancestor of w and the length of q is the same as that of the longest
snake in the family.  Therefore we're left with yet another complexity
problem.

David Moews answered:

>I agree that congruences changing the string representation of a snake
>pose no problem (I did not mention these earlier because I was not sure
>whether you were considering a polyomino as containing congruent images
>of its subpolyominoes or not.)  Unfortunately there is a larger
>problem, because of the fact that some strings which seem to represent
>snakes in fact self-intersect.  For example, suppose we wish to find
>all snakes not containing any polyomino congruent to a member of the
>following set S:
>
> **    *
>**     ***     ****
>         *
>
>There are infinitely many strings not containing the string
>representation of these snakes: in fact, any initial segment of
>
>*E*E*N*N*W*W*S*S*E*E*N*N*W*W*S*S*E*E*N*N*W*W*S*S*....   (to use your
>notation)
>
>is OK.  However, these strings do not correspond to infinitely many
>snakes, because unless an initial segment of the above string is
>sufficiently short, it self-overlaps, so, in fact, the only snakes
>avoiding S are subpolyominoes of
>
>***
>* *
>***   .  For a more difficult example, take S' to be
>
> **    *      *
>**     ***    ****    *****        ;
>         *       *
>
>then any string of the form
>
>(*E)^a (*N)^b (*W)^c (*S)^d (*E)^e (*N)^f ...     (a,b,c,d,e,f,... in
>{2,3})
>
>would seem to be OK (where (T)^i denotes i repetitions of the string
>T), but again there are only finitely many snakes avoiding S'.

I answered:

I think we are left with two main problems:

1) Designing an algorithm to find out whether, given a polymino P, a
node n on P, and a snake S, we can attach a infinite series of
instances of S to n which has got n as only intersection with P;

2) Proving that, if there are infinitely many polyminos avoiding the
target set, then there are two snakes V and Q such that the polyminos
{V, VQ, VQQ...} are indeed snakes avoiding the target family.

Given an excluding snake W ending with the same last n moves as one of
its ancestor V (W=VQ), we could check whether {VQ, VQQ, VQQQ...}, is a
set of snakes, thanks to 1); 2) would garantee that we would eventually
stumble against a proper (V, Q) pair whenever the avoiding set would be
infinite.

Now, 1) looks pretty easy:
a) check whether {S, SS, SSS...} are valid snakes : they are iff SS is
a snake;
b) (if a) holds) consider PS, PSS, PSSS... until you obtained a
intersection OR the [city block] distance of each node of the (n+1)th
instance to each node of P is bigger than that of its counterpart in
the nth instance to the same node of P (I hope that makes sense :) .

But 2) is just a personal guess...  Maybe an infinite excluding set can
have some sort of an odd "spiral" structure?

-- Yann David <100552.1400@CompuServe.COM>, France