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.

What is the minimum number of colors needed to color every unit square of $\mathbb Z^2$ such that if any polyomino of order $n$ is placed anywhere on the grid it would have all its unit-squares placed on squares of different colors?

share|improve this question
    
@matt: I restored "polyomino", which I believe was the intended meaning. I never heard of a "polyominal", and in case you meant "polynomial", I don't think that's what's intended. –  joriki Jan 2 '12 at 13:05
    
@Chandrasekhar: No problem; I'd already deleted my comment because I realized you'd been editing an old version and probably hadn't seen this one yet. –  joriki Jan 2 '12 at 13:33
    
@joriki (also 0.99999....9999) Yes, my apologies. I wasn't careful enough in reading the post. –  matt Jan 2 '12 at 13:37
    
Is the question about the chromatic number of the graph induced by a particular polyomino, or the set of all polyominoes of order $n$? The latter is just the distance graph for $d\le n-1$. The former might be more interesting... –  mjqxxxx Jan 2 '12 at 13:46

1 Answer 1

up vote 4 down vote accepted

For odd $n$, the answer is $(n^2+1)/2$.

To see that this number is necessary, consider a diamond-shaped patch of $(n^2+1)/2$ squares. They are all within a distance of $n-1$ of each other, and thus must all have different colours.

To see that this number is sufficient, consider the colouring $x+ny\,\bmod\,{(n^2+1)/2}$. Equicoloured squares within a row are $(n^2+1)/2\ge n$ apart. Equicoloured squares in consecutive rows are $n+1$ apart, and this increases until the progression wraps around and gets close to $0$ again. This happens at $\Delta y=(n\pm1)/2$, and the corresponding distances are

$$\frac{n\pm1}2+\left|\frac{n^2+1}2-\frac{n(n\pm1)}2\right|=\frac{n\pm1}2+\frac{n\mp1}2=n\;.$$

The next wraparound occurs at $\Delta y=n$, and then the distance in the $y$ direction is already enough.

For even $n$, the answer is $n^2/2$.

To see that this number is necessary, consider a diamond-shaped patch of $n^2/2-n+1$ squares and shift it to the right by one to add another $n-1$ squares, for a total of $n^2/2$. The squares in this shape are all within a distance of $n-1$ of each other, and thus must all have different colours.

To see that this number is sufficient, consider the colouring $x+(n-1)y\,\bmod\,n^2/2$. Equicoloured squares within a row are $n^2/2\ge n$ apart. Equicoloured squares in consecutive rows are $n$ apart, and this increases until the progression wraps around and gets close to $0$ again. This happens at $\Delta y=n/2$, where the distance is $n/2+n^2/2-(n-1)n/2=n$, and at $\Delta y=n/2+1$, where the distance is also $n/2+1+(n-1)(n/2+1)-n^2/2=n$. The next wraparound occurs at $\Delta y=n+1$, and then the distance in the $y$ direction is already enough.

share|improve this answer

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.