11
$\begingroup$

Beginner puzzle (suitable for people who are new to puzzle solving).

Peter wants to colour the nine cells of a 3 by 3 square (see below) in such a way that each of the rows, each of the columns and both diagonals have cells of three different colours. What is the least number of colours Peter could use?

Empty 3 x 3 square grid

Attribution: UK EUROPEAN KANGAROO MATHEMATICAL CHALLENGE PINK 2016

Improve this question
$\endgroup$
3
  • 9
    $\begingroup$ Could you please stop with the "beginner puzzle" intros? Five rows of supersized, bold text that says basically nothing is not the way to make your puzzles beginner friendly. $\endgroup$
    – Bass
    Commented Sep 9 at 14:16
  • $\begingroup$ One way to make the puzzle beginner friendly is to ask experienced solvers to wait 48 hours before answering (or to hide answers for that period, which I did on a number puzzle that asked for this restraint). $\endgroup$
    – Oscar Lanzi
    Commented Sep 9 at 17:33
  • 1
    $\begingroup$ @Bass I have streamlined the ‘beginner puzzle’ introduction. $\endgroup$
    – Will.Octagon.Gibson
    Commented Sep 9 at 21:31

4 Answers 4

Reset to default
22
$\begingroup$

The minimum is

5 colors

because

these 5 cells must be all different colors, since any two share a line
partially filled grid of 5 cells
and we can fill in the rest symmetrically:
full grid

Improve this answer
$\endgroup$
16
$\begingroup$

Basically a beginner here.

Start with a diagonal. All three cells must have unique colours:

Grid with three shaded cells

Then, the two unshaded corners must be given unique colours because both of them have a diagonal with the centre, and both of them share a row and a column with the two shaded corners, and they also share a diagonal themselves.

Grid with five shaded cells

Finally, existing colours may be used to fill in the rest of the square, by rotating by three cells clockwise or anticlockwise around the centre:

Grid with all cells shaded

My answer is

five colours.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Using >! in your post will add spoiler guards, so other's cannot accidentally see your solution. $\endgroup$
    – infinitezero
    Commented Sep 11 at 6:52
7
$\begingroup$

As described in many answers, five colors is the minimum. Here we bring in the theory of pandiagonal Latin squares to show some hidden features of the solution and allow a generalization to $n×n$ arrays.

A pandiagonal Latin square is one where all the labellings are different:

  • In the rows

  • In the columns

  • And in all the diagonals that are formed if a pair of opposite edges are glued together to make a cylinder.

Pandiagonal Latin squares exist if and only if the order is one more or one less than a multiple of $6$, so we can arrange our five colors into a square of order five:

$\begin{array} &\color{blue}{■}&\color{brown}{■}&\color{gold}{■}&\color{tan}{■}&\color{black}{■}\\ \color{gold}{■}&\color{tan}{■}&\color{black}{■}&\color{blue}{■}&\color{brown}{■}\\ \color{black}{■}&\color{blue}{■}&\color{brown}{■}&\color{gold}{■}&\color{tan}{■}\\ \color{brown}{■}&\color{gold}{■}&\color{tan}{■}&\color{black}{■}&\color{blue}{■}\\ \color{tan}{■}&\color{black}{■}&\color{blue}{■}&\color{brown}{■}&\color{gold}{■}\\ \end{array}$

Since all rows, columns, and diagonals of the larger square have different colors by this construction, any $3×3$ bloc will provide the requited $3×3$ array. All such blocks are identical except for the way the colors are labeled. But also any $4×4$ block or the entire $5×5$ Latin square will also meet the problem conditions. The five colors needed for the $3×3$ square are also sufficient for $4×4$ and for $5×5$!

In general, given any $N$ an $N×N$ array can be differently colored along rows, columns and diagonals using no more than $N+3$ different colors because we can always construct a pandiaginal Latin square of order $N$, $N+1$, $N+2$ or $N+3$.

Note also that with order five there is just one pandiaginal square, as above, plus its mirror image; but for higher orders the number of possible pandiagonal Latin squares grows expinentially thus enabling many solutions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Using >! in your post will add spoiler guards, so other's cannot accidentally see your solution. $\endgroup$
    – infinitezero
    Commented Sep 11 at 6:53
  • $\begingroup$ I know, but I assumed that the cat was out of the bag. I wanted to tie the answer to the Latin square theory. $\endgroup$
    – Oscar Lanzi
    Commented Sep 11 at 8:16
4
$\begingroup$

I got

5

by "coloring" with numbers:

the image in the puzzle, with cells annotated with numbers 1 through 5 in a way that correctly solves the puzzle

Improve this answer
$\endgroup$
5
  • $\begingroup$ It took a while for me to see this because I thought the 1's in the second and third rows were 7's! Write more neatly or use the Mathjax array option to make things clear. $\endgroup$
    – Oscar Lanzi
    Commented Sep 9 at 20:36
  • $\begingroup$ Fyi, my tool of choice to draw solutions for this kind of puzzles is Penpa. $\endgroup$
    – Bubbler
    Commented Sep 10 at 9:34
  • $\begingroup$ I tried to use the same technique to solve the puzzle as you. I would like to point-out, that your construction is wrong (even though your answer is correct). There are two mistakes in your construction: firstly the second row and column have the same three colours in the same order. Secondly, the first row and third column have the same three colours, but in a different order. To correct both errors you would need an additional colour. The problem lies in the greedy approach to selecting colours. In the optimal solution posted by the other people, no colour is diagonaly adjacent to itslef. $\endgroup$
    – Minop
    Commented Sep 11 at 14:54
  • $\begingroup$ @Minop: I see now that the rules are ambiguous as to whether the 2 middle column+middle row being "251" is legal or not. i took it as legal, as all rows, columns and diagonals indeed have no repeating numbers in them individually. if that's not what you're reffering to, i'm unclear as to why my construction could be wrong when the answer it led me to was correct and the solution is in fact optimal. $\endgroup$
    – Themoonisacheese
    Commented Sep 11 at 15:03
  • $\begingroup$ @Themoonisacheese you are right. The rules are ambiguous. I interpreted them as no three sets of colours are allowed to be the same. The other solutions satisfy this stronger restriction. I tried to solve it with the same construction as you, but with this stronger restriction it does not lead to the correct answer. I misunderstood the question, sorry for bothering you. $\endgroup$
    – Minop
    Commented Sep 12 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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