Colored Squares and Cubes

  1. Color each square in a grid, such that no two neighboring squares have the same color, and each square neighbors any other color only once. (Neighboring squares share sides - don't consider corner-touching squares to be neighbors.) What is the minimum number of colors needed for:
    1. a 3x3 grid?
    2. a 4x4 grid?
    3. the plane?
  2. Color each cube in a 3-D lattice such that no two neighboring cubes have the same color, and each cube neighbors any other color only once. (Neighboring cubes share faces - don't consider corner- or edge-touching cubes to be neighbors.) What is the minimum number of colors needed for:
    1. a 2x2x2 cube?
    2. a 3x3x3 cube?
    3. a 4x4x4 cube?
    4. 3-space?
Extra Credit: How do the answers change if we allow wrapping - that is, if we assume left touches right, top touches bottom, (and front touches back, for the second part)?

Source: Original.

Solutions were received from Samantha Levin, Henry Bottomley, Sandy Thompson, and Parthiv Shah.

Henry Bottomley's solutions are quite comprehensive: 

The solutions are:
1.1 5; 1.2 5; 1.3 5
2.1 4; 2.2 7; 2.3 7; 2.4 7
Bonus: 
1.1 9; 1.2 8
2.1 impossible; 2.2 9; 2.3 8

Examples:

1.  For 3x3, 4x4 or the plane as a whole, it is obvious that at least 5 colours
are needed as each square must touch four other distinct colours.  Since it
is possible to colour the plane using five colours, this is the solution to
all three questions.  The following colouring involves each row being offset
a couple of places from the preceedeing row:
............
.ABCDEABCDE.
.CDEABCDEAB.
.EABCDEABCD.
.BCDEABCDEA.
.DEABCDEABC.
.ABCDEABCDE.
.CDEABCDEAB.
............
etc.
so A always has B,C,E and D around it, all in the same relative positions and
similarly for the other colours. 

So possible solutions for 3x3 and 4x4 are 

ABC     ABCD
CDE     CDEA
EAB     EABC
        BCDE

while 2x2 requires exactly 4 colours for the 4 squares, e.g.
AB
CD


2.  For 3x3x3, 4x4x4 or 3-space as a whole, it is obvious that at least 7 colours
are needed as each cube must touch six other distinct colours.  Since it is
possible to colour the Since it is possible to colour 3-space using seven colours,
this is the solution to the last three questions. The following colouring involves
each row being offset two places from the preceeding row, and each plane being
offset three places:
............ ............ ............ ............
.ABCDEFGABC. .DEFGABCDEF. .GABCDEFGAB. .CDEFGABCDE.
.CDEFGABCDE. .FGABCDEFGA. .BCDEFGABCD. .EFGABCDEFG.
.EFGABCDEFG. .ABCDEFGABC. .DEFGABCDEF. .GABCDEFGAB.
.GABCDEFGAB. .CDEFGABCDE. .FGABCDEFGA. .BCDEFGABCD.
.BCDEFGABCD. .EFGABCDEFG. .ABCDEFGABC. .DEFGABCDEF.
.DEFGABCDEF. .GABCDEFGAB. .CDEFGABCDE. .FGABCDEFGA.
.FGABCDEFGA. .BCDEFGABCD. .EFGABCDEFG. .ABCDEFGABC.
.ABCDEFGABC. .DEFGABCDEF. .GABCDEFGAB. .CDEFGABCDE.
............ ............ ............ ............
etc.
so A always has B,C,G and F around it and has E and D above and below, all in
the same relative positions and similarly for the other colours. 

this gives a 3x3 solution such as 
ABC  DEF  GAB
CDE  FGA  BCD
EFG  ABC  DEF

and a 4x4 solution such as 
ABCD  DEFG  GABC  CDEF
CDEF  FGAB  BCDE  EFGA
EFGA  ABCD  DEFG  GABC
GABC  CDEF  FGAB  BCDE

For 2x2x2 at least four colours are needed for the top plane (as in 2x2) and
this is indeed a solution, e.g.
AB  DC
CD  BA


Bonus.  With the wrapping suggested, 2x2 and 2x2x2 are impossible since each
square or cube touches another on more than one side (if this doesn't count
then 4 are needed for 2x2 and 2x2x2 exactly as above, since every square or
cube which touches another in the wrapped version - always twice - also touches
it in the unwrapped version - once). 

For wrapped 3x3 nine colours are needed as every square is either adjacent or
next to adjacent to every other, e.g. 
ABC
DEF
GHI

So for wrapped 3x3x3 nine colours are needed for the top plane, but nine is
also sufficent for all three planes, e.g.
ABC  IGH  EFD
DEF  CAB  HIG
GHI  FDE  BCA

For 4x4 at least eight colours are needed, as each coloured square prevents
its four neighbours being adjacent to another square of that colour, and after
two squares have been coloured the same there are no available squares for that
colour.  Eight is sufficient, e.g.
ABCD
EFGH
BADC
FEHG  

For 4x4x4 eight colours are required for the top plane as in 4x4, and eight
is sufficient for all four planes, e.g.

ABCD  GHEF  BADC  HGFE
EFGH  CDAB  FEGH  DCBA
BADC  HGFE  ABCD  GHEF
FEHG  DCBA  EFGH  CDAB

Lots of symmetry and knight's moves in these solutions

Regards

Henry Bottomley
Mail to Ken