12
$\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$
0

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$
20
$\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$
0
9
$\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$ block will provide the required $3×3$ array. All such blocks are identical except for the way the colors are labeled. But 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 pandiagonal Latin square of order $N$, $N+1$, $N+2$ or $N+3$.

Note also that with order five there is just one pandiagonal square, as above, plus its mirror image; but for higher orders, the number of possible pandiagonal Latin squares grows exponentially, 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$ Commented Sep 11, 2024 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$ Commented Sep 11, 2024 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$ Commented Sep 9, 2024 at 20:36
  • $\begingroup$ Fyi, my tool of choice to draw solutions for this kind of puzzles is Penpa. $\endgroup$ Commented Sep 10, 2024 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$ Commented Sep 11, 2024 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$ Commented Sep 11, 2024 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$ Commented Sep 12, 2024 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.