-1
$\begingroup$

Inspired by the four colours puzzle.

The goal is to color the squares of an $n\times n$ grid with $n$ colors such that

  • All squares are coloured.

  • no two squares of the same color touch at an edge or corner

  • there are an equal number of squares of each color.

For which values of $n$ is this possible?

$\endgroup$
  • 1
    $\begingroup$ @CipherRiddle Michael is right. Your first bullet point should really be changed to "all squares are coloured". It's not that it's insoluble with the "at most one" thing, it's just ... a bit strange to say "at most one" when you really mean "zero". $\endgroup$ – Rand al'Thor Oct 26 '16 at 11:08
6
$\begingroup$

It's possible if and only if

$n$ is not $2$ or $3$.

Proof is as follows.

$n\leq3$

It's trivially possible for $n=1$. It's impossible for $n=2$ and $n=3$, because four distinct colours are needed in order to colour any $2\times2$ square in such a way that no two cells of the same colour meet at an edge or vertex.

$n>3$

Let the first row of the $n\times n$ block contain one cell of each colour. Let the second row contain the same colours in the same order but cycled round by two places (e.g. ABCDEF -> CDEFAB). Keep on filling in each row in this way until you reach the bottom of the $n\times n$ block.

For example, with $n=7$ we have

A B C D E F G
C D E F G A B
E F G A B C D
G A B C D E F
B C D E F G A
D E F G A B C
F G A B C D E

$\endgroup$
  • 1
    $\begingroup$ It's possible for n=1 $\endgroup$ – YowE3K Oct 23 '16 at 20:11
  • 1
    $\begingroup$ I'll give you a +1 for caving in to my pedanticism (I'm not so pedantic that I care whether "pedanticism" is a real word though) $\endgroup$ – YowE3K Oct 23 '16 at 20:17
  • 4
    $\begingroup$ @YowE3K Oh, I love p̶e̶d̶a̶n̶t̶i̶c̶i̶s̶m̶ pedantry. I'm a pure mathematician; pathological counterexamples are part of my daily bread ;-) $\endgroup$ – Rand al'Thor Oct 23 '16 at 20:32
  • 1
    $\begingroup$ I should point out that the middle part of the "m" in your last comment does not appear to be crossed out - is that just my display, or did you accidentally use strike-through on the space instead of the "m"? $\endgroup$ – YowE3K Oct 23 '16 at 20:36
  • 1
    $\begingroup$ @YowE3K SE doesn't support <strike></strike> in comments, so I used this generator. +1 for EXTRA pedantry. $\endgroup$ – Rand al'Thor Oct 23 '16 at 20:38

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.