2
$\begingroup$

EDIT: I have been working on this for a while now and I can say that a $2\times 2$ grid is such a deceiver because the maximum colors we can do for it is $2$. From $3$, everything breaks as there will always be adjacent cells colored.

Given a $K\times K$ grid of cells and $N$ distinct colors, in how many ways can we color the grid such that no two adjacent cells are colored. That said, if two colors touch horizontal or vertical to each other, they are adjacent. That is to be avoided, as some images below show. Of importance are cases where $N$$\le$$K^2$. As you might have imagined, the $K^2$ defines the possible spaces. It is undesirable to end up with a case where we have too many colors than is the square space. Waste of paint. Anyway, also, each color is used only once. Keeps everything neat.

Consider the following $7\times 7$ grid of cells where we are working with $2$ colors. The following coloring's acceptable;
enter image description here

This, too, is acceptable. Yes, the cells are adjacent, but not horizontally/vertically. enter image description here

However, the coloring below is not acceptable; enter image description here

This is also not acceptable; enter image description here

How can this be solved?

$\endgroup$
  • $\begingroup$ The different colors just gives us a factor of $N!$, and then you may as well ask "How many ways are there to color $N$ squares black so that no two black squares are adjacent?" It's a bit simpler, I think. But still not trivial. For $1\times K$ grids, it's not too difficult, but square grids are another story. $\endgroup$ – Arthur Nov 18 '19 at 11:56
  • $\begingroup$ Interesting. What about rectangular grids? What would happen then? But yes, the fact that this is a square grid weighs heavy. $\endgroup$ – Muga S. Nov 18 '19 at 12:00
  • $\begingroup$ In general, rectangular grids are, if anything, more difficult than square grids. Just because there is more freedom. That being said, answering for specific recttangular grids, like $1\times K$ (which is pretty easy) and $2\times K$ (which looks like it's a little tricky but not too bad) might be easier than square grids. $\endgroup$ – Arthur Nov 18 '19 at 12:04
  • $\begingroup$ @Arthur Indeed. I would understand why a $1\times K$ grid would be easier to solve than the others - it's just one row; a queue of items - in this case, colors. It is a rectangular grid, no one's denying that. True. However, whether it's a true rectangle is another story. $\endgroup$ – Muga S. Nov 18 '19 at 14:38
3
$\begingroup$

Here are the results for small $K$ and $N$, without the factor of $N!$: \begin{equation} \begin{matrix} &K\backslash N &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 \\ &1 &1 \\ &2 &4 &2 &0 &0 \\ &3 &9 &24 &22 &6 &1 &0 &0 &0 &0 \\ &4 &16 &96 &276 &405 &304 &114 &20 &2 &0 &0 &0 &0 &0 &0 \\ &5 &25 &260 &1474 &5024 &10741 &14650 &12798 &7157 &2578 &618 &106 &14 &1 &0 \end{matrix} \end{equation} The count for $N=1$ is obviously $K^2$. The next few columns appear in OEIS as sequences involving placements of nonattacking wazirs on a chessboard: A172225 A172226 A172227 A172228

$\endgroup$
  • $\begingroup$ Correct me if i'm wrong, but your data claims that in a $3\times 3$ grid where we are supposed to use two colors, there are $0$ possible ways to color. Isn't this incorrect? We could color the top-most-left cell and then the bottom-most-right cell (and several other ways). $\endgroup$ – Muga S. Nov 18 '19 at 17:28
  • $\begingroup$ No, for $K=3$ and $N=2$, the count is 24. I updated the table to show that $K$ is the row and $N$ is the column. $\endgroup$ – Rob Pratt Nov 18 '19 at 17:57
  • $\begingroup$ So you're claiming that a $3\times 3$ grid, using $2$ colors, can be colored in just $24$ different ways? I don't know. I'm rather skeptical about your solution. How can you prove correctness? Since that is a relatively small grid, I did it by hand and ended up having $44$ combinations. I zipped a few of the images here. I'm not saying the answer is $44$. I'm just saying your answer of $24$, hence your entire table, might be incorrect. $\endgroup$ – Muga S. Nov 18 '19 at 19:30
  • $\begingroup$ $\binom{9}{2}=36$ is a trivial upper bound obtained from considering all pairs of cells. $\endgroup$ – Rob Pratt Nov 18 '19 at 21:53
  • $\begingroup$ I wasn’t able to open your attachment, but I suspect the discrepancy is that my table shows the number of ways to color $N$ of the cells black, as in @Arthur’s comment. To get the full count, you would then need to multiply by $N!$. For $K=3$ and $N=2$, this would yield $24\cdot 2!=48$ colorings. For a simpler case, consider $K=N=2$, where my table has a count of 2, but this yields 4 colorings. $\endgroup$ – Rob Pratt Nov 19 '19 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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