Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Which polyominos (with orientation) of $n$ squares, requires the least number of different colors, $c(n)$, such that if this polyomino is placed anywhere on an optimally colored infinite square grid of $c(n)$ colors, it will have all its squares placed on different colors?

And which polyomino(s) require the most colors, and how many colors as a function of $n$?

Also: How to show that a finite number of colors (depending on n), suffices for any subset of n unit-m-cubes, in Z^m?

share|improve this question
    
Maybe the more natural question is for which not necessarily connected set of n squares –  user1708 Jan 4 '12 at 12:43
    
    
Brooks' theorem says that the chromatic number of a graph is at most $\Delta + 1$, where $\Delta$ is the maximum vertex degree (and is only $\Delta + 1$ if the graph is complete or an odd cycle). A set of $n$ points in $\mathbb{Z}^m$ has at most $n(n-1)$ different vector separations between distinct points, so the induced graph (which is regular) has degree at most $n(n-1)$, and can't be either complete or an odd cycle; so $n(n-1)$ colors will always suffice. –  mjqxxxx Jan 4 '12 at 19:06
add comment

1 Answer

Rectangular $n$-ominoes have $c(n)=n$, the minimal possible value.

Let’s call polyominoes for which $c(n)=n$, “optimal”. Colouring the grid with diagonal stripes shows that thin snake-like directed polyominoes such as the following are also optimal.

$\hspace{2.5in}$ snake

Optimal polyominoes can’t be arch-shaped like the following; each of the cells in the ‘gap’ have to differ in colour from all the cells in the arch shape.

$\hspace{2.75in}$ non-convex

This is a particular case of the following condition on optimal polyominoes.

If $P=\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$ is an $n$-omino with the $(x_i,y_i)$ being the cell coordinates, then let $P+v$ be $P$ translated by vector $v$, and let $$D(P)=\{(x_i-x_j,y_i-y_j):(x_i,y_i)\in P,(x_j,y_j)\in P\}$$ be the “distance polyomino” of $P$. For example, the distance polyomino of the ‘F’ pentomino (on it’s ‘back’) looks like this (distance polyominoes are always centrally symmetric):

$\hspace{2.75in}$ D(F)

Now if for any cell $v\notin P$, we have $P\subset D(P)+v$, then $P$ is not optimal, because there is no way to colour $v$.

As well as excluding arch-shapes, this condition excludes others from being optimal, such as this hexomino:

$\hspace{2.75in}$ non-optimal hexomino

This condition can be generalised as follows:

If for any $S\subseteq P$ and any cell $v$ such that $S+v\cap P=\varnothing$, we have $$\left|\;\bigcup_{u\in S}\;P\;\setminus (D(P)+u+v)\;\right|<|S|,$$ then $P$ is not optimal, because there is no way to colour the cells in $S$.

This generalised condition excludes the ‘T’ pentomino from being optimal (the two cells on one side of the stroke cannot be coloured). However, it fails to exclude the ‘F’ pentomino (which is also non-optimal).

Many polyominoes can be seen to be optimal simply by (rotating and) numbering the cells from left-to-right, top-to-bottom in the natural manner. If in the result, the numbers down the columns form arithmetic progressions with the same difference in each column, then the polyomino is optimal (cycle all the colours on every row). This works for rectangles, snake-like directed polyominoes, all row-convex polyominoes with only two rows, and all pentominoes except the ‘U’, ‘T’ and ‘F’ (which are all non-optimal). It also works for some non-convex polyominoes, like this octomino:

$\hspace{3.1in}$ non-convex octomino

Also, any row-convex polyomino in which each row is the same length is also optimal (cycle the colours on each row). Thus the following (non-convex) hexomino is optimal:

$\hspace{3in}$ non-convex hexomino

Are there any optimal polyominoes that are neither row- nor column-convex?

share|improve this answer
    
By "As well as excluding non-convex polyominoes", I think you mean "As well as excluding some non-convex polyominoes"? Otherwise your last two examples would be counterexamples. –  joriki Jan 5 '12 at 11:18
    
@joriki: Corrected; thanks. –  David Bevan Jan 5 '12 at 12:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.