Ken's Puzzle of the Week

Patterns of Circles in a Grid

  Fill a grid with black, white and gray circles, such that:

  • Each black circle neighbors an even number of black circles (0 may be considered even.)
  • Each white circle neighbors an odd number of white circles.
  • Each gray circle neighbors an equal number of black and white circles.
An example 3x3 grid is shown.

Try to solve the puzzle for 3x3 to 6x6 grids with the following different requirements:

  1. Maximize the number of black circles.
  2. Maximize the number of white circles.
  3. Minimize the number of gray circles. Can a grid be made without any?
  4. Evenly distribute the circles. That is, minimize the difference between the max and min colors.

Source: Original.
Solutions were received from Keith F. Lynch and Dan Chirica.  Keith was quite thorough:

 

Black = #, grey = *, white = .

You asked for solutions from three on a side through six on a side.
I've solved it for zero on a side through seven on a side.  For no-gray, I've solved it though eleven on a side.

The total number of solutions for zero through seven on a side (excluding rotations and reflections) 
 are: 1, 2, 2, 5, 12, 69, 243, 1710.  This is not in Plouffe's On-Line Encyclopedia of Integer Sequences.

All-gray is a solution for every possible side length, including infinite.

> 1. Maximize the number of black circles.

#

. .  or  * *
. .      * *

# # #
# . #
. * *

# # # #
. # # .
. # # .
# # # #

# # # # #
# . # # .
. * * * .
# * . * #
# # . # #

# # # # # .      # # # # * #
# . # # . *      . # # . . *
# # . # # *  or  . # # . . #
# # # # # .      # # # # # #
. # # . # .      # # . # . .
. * * . # #      # . # * * #

# # # # # * *
# . # # . . #
# # . # # # #
# # # # # # #
# . # # . . #
* . # # . . *
* # # # # * #

> 2. Maximize the number of white circles.

#  or  *

. .
. .

# # .       # . .
. # .  or   * . .
. # #       # * #

# # . #
# . . .
. . . #
# . # #

. . . . .
. . . . .
. . # . .
. . . . .
. . . . .

# . # . . .
. . . . # #
# . . . * #
. . . # . .
. # * . . .
. # # . . .

# . . # . . #
. . # . # . .
. # . . . # .
# . . # . . #
. # . . . # .
. . # . # . .
# . . # . . #

> 3. Minimize the number of gray circles.  Can a grid be made without any?

Yes, apparently always, though I haven't proven it except where the side length is congruent to two mod three.  
I've solved this for up to eleven on a side.  Note that all solutions (so far) have symmetry.
The number of solutions for zero through eleven 
(not counting rotations or reflections) are:  1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 5, 1.
This is not in Plouffe's On-Line Encyclopedia of Integer Sequences.  I may submit it.

#

. .
. .

# # .
. # .
. # #

# # # #      # # . #
. # # .  or  # . . .
. # # .      . . . #
# # # #      # . # #

. . . . .
. . . . .
. . # . .
. . . . .
. . . . .

# # # . # #      # . . . # .
# . # . # .      . . # # # .
# # . # . #  or  . # . . # #
. . # # . #      . # . # . .
# # . . . #      # # # . . .
# . # # # .      . . # . . .

# . . # . . #
. . # . # . .
. # . . . # .
# . . # . . #
. # . . . # .
. . # . # . .
# . . # . . #

. . . . . . . .
. . . . . . . .
. . # . . # . .
. . . . . . . .
. . . . . . . .
. . # . . # . .
. . . . . . . .
. . . . . . . .

# # # . # # # . #       . # . . . # . . .
. # # # . . . # #       . # # # . . . # #
# . # # # . # # #       . . . # . . . # .
# . . . . . # # .       # . . # # # # # .
# . # . # . # . #  or   . . . # # # . . .
. # # . . . . . #       . # # # # # . . #
# # # . # # # . #       . # . . . # . . .
# # . . . # # # .       # # . . . # # # .
# . # # # . # # #       . . . # . . . # .

Any of:

# # # # # # # # # #      # # # . # . # # # .      # # . # . # # # . #
. # # . # # . # # .      # . # . # # . . . #      . # . # # . . . # #
. # # . # # . # # .      # # . # . # . # # .      # . # . # . # # . .
# # # # # # # # # #      . . # # . . . . # #      # . # # # . # . # #
. . . . . . . . . .      # # . . . . . # # #      # . . . . . # # # .
. . . . . . . . . .      . # # . . . # # . #      . # # # . . . . . #
# # # # # # # # # #      # . . . . # # . . .      # # . # . # # # . #
. # # . # # . # # .      # . # . # # . . . #      . . # # . # . # . #
. # # . # # . # # .      # . # # # . . . . .      # # . . . # # . # .
# # # # # # # # # #      . # . # # # . # . #      # . # # # . # . # #

# # . . . . # # . .      . # # . . . . # # .
# . . # # . . # . .      . # . . # # . . # .
. . . # . . # # . .      # # . # . . # . # #
. # # # . # . # # #      . . . . # # . . . .
. # . . . . # . . #      . . # . . . . # . .
. . . # . . # # . .      # # . # . . # . # #
# . # . # # # . # .      . # # . . . . # # .
# # # # . # . . # .      . # . . # # . . # .
. . . # . . # # . .      # # . # . . # . # #
. . . # # . . . . #      . . . . # # . . . .

. . . . . . . . . . .
. . . . . . . . . . .
. . # . . # . . # . .
. . . . . . . . . . .
. . . . . . . . . . .
. . # . . # . . # . .
. . . . . . . . . . .
. . . . . . . . . . .
. . # . . # . . # . .
. . . . . . . . . . .
. . . . . . . . . . .

I have found one solution for twelve on a side so far (there may be
more):

# # # # # # # # # # # #
# . # # . # # . # # . #
. . . . . . . . . . . .
. # . . # . . # . . # .
# . # # . # # . # # . #
# . # # . # # . # # . #
. # . . # . . # . . # .
. . . . . . . . . . . .
# . # # . # # . # # . #
# # # # # # # # # # # #
. . . . . . . . . . . .
. . . . . . . . . . . .

Note the pattern for two, five, eight, and eleven on a side.  This can obviously be extended indefinitely.

> 4. Evenly distribute the circles.  That is, minimize the difference 
> between the max and min colors.

Of the side lengths I looked at, only for six on a side can there be exact equality.  
(There might also be for nine, twelve, etc., on a side, but I didn't check.)

#  or  *

. .  or  * *
. .      * *

# . #      # . .
* . *  or  * . .
* # *      # * #

# # . #      # # . .      # # * #      # # * *
. # * .  or  . # * #  or  # . . *  or  # . . #
* . * *      . * . *      * . . #      * . . *
# * * #      # * # .      * # * *      * # * #

Any of:

# # * . #   # # * . #   # . # . #   # . # . #   # . # . *   # . # * #
. # . * *   . # * . *   * * . * *   * * . * *   * * . * #   * * . * .
# . # . #   # . # * #   # . * # .   # . * * *   # . * * *   . # * # .
* # . * .   * # * * .   # # * * .   * * # # .   # # # * .   . * . * *
* . * # *   * . . # .   . . * * #   # . . # .   . . # * .   # * # . #

# . # * .   # . * * *   . # # * *   . # # * *   . # . # .   * . # * *
* . * . #   . * * # .   . # . . #   . # . . #   # . # # .   * # . # .
* # # * *   * * # . #   * * * * *   * * * * *   . # * * *   # . * . #
. # . . #   * # . . #   # . # # .   . # # . #   * * . . #   . # . # *
. # # * *   * . # # .   * * . # .   . # . * *   * * # * *   * * # . *

Any of:

# # * # * #   # # * . . #   # # * . . #   # . # # . .
# . * . * .   . # * . . *   . # * . . *   * * . # * #
* * . # * .   * . * # # *   * . * # # *   . # * * . *
# . # # * #   # * # . . #   * # * . # .   * . * * # .
* * * * . .   * . * # # *   # . # * . *   # * # . * *
# . . # . .   . # * . . *   . # * . # *   . . # # . #

# . # . . *   # . # . * #   # . # . * *   # . # . * *
. * # # * #   * . # # . *   . * # # . #   . * # # . #
. . # # . *   * # # . # .   . . # # . .   . . # # . .
# . * # . #   * * . # . .   # . # * . #   # . # * . #
. * * . * .   * . * . . #   * . * . * *   * . * * . *
* # * * # *   * # * # * *   * # * # * *   * # * * # *

# . # . * *   # . # . * *   # . . # . .   # . * # # *
. * # # . #   . * # # . #   * * # # * #   * . * # . *
. . # # . .   . . # # . .   # . * * . *   * # * . * *
# . * # . #   # . * # . #   * . * * . #   # . # * # *
* . * * . *   * * . * . *   # * # # * *   # . # . . *
* # * * # *   * * # * # *   . . # . . #   . # . . # .

# * # * # .   . # # # * *   . # # * # .   * # # * . *
* . . * . *   # . . . # .   . # . . * .   . * # . * #
# . . * # *   . # # . . #   * # # * # #   * . . . # #
* * * # # .   * * * # # *   * . . * # .   # # . . . *
# . # # . #   * * . . * .   # . . * . *   # * . # * .
. * * . # .   * * # * # .   * * # * # *   * . * # # *

For seven on a side there are exactly 100 solutions with a difference of one between the least and the most
numerous color, 58 where the black circles have an excess of one, 42 where the white circles have an excess
of one, and no solutions where the grey circles do.  Here's one solution:

* . . # # * *
* # # * . # .
# . * . * # .
# * . # . * #
. # * . * . #
. # . * # # *
* * # # . . *

Since yesterday, I've learned that the 12 on a side no-gray pattern I emailed you is the only one, and I've
found one 13 on a side pattern:

# . . # . . # . . # . . #
. . # . # . . . # . # . .
. # . . . # . # . . . # .
# . . # . . # . . # . . #
. # . . . # . # . . . # .
. . # . # . . . # . # . .
# . . # . . # . . # . . #
. . # . # . . . # . # . .
. # . . . # . # . . . # .
# . . # . . # . . # . . #
. # . . . # . # . . . # .
. . # . # . . . # . # . .
# . . # . . # . . # . . #

So the number of solutions for each N starts 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 5, 1, 1, ...

I have since confirmed that that's the only 13, and that there's exactly one 14, which I already knew about:

. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . # . . # . . # . . # . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . # . . # . . # . . # . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . # . . # . . # . . # . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . # . . # . . # . . # . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .

So the number of solutions for each N starts 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 5, 1, 1, 1, 1, ...

It's interesting that it's so small, but never zero (at least not yet).  And that all the patterns have
symmetries.  I think it's trying to tell me something.

I still don't know if there's a 15.  It took over a week of CPU to confirm that that was the only 14.
Instead of searching for *all* 15s, I'll just search for symmetrical ones.  That will be a lot faster,
but won't tell me much if it doesn't find any.

Mail to Ken