Colouring maps
Sorry for the lack of puzzle last time — I was flying to Pusan (Korea) and didn't get time to put anything together.
Anyway, there's always some interest when somebody posts not only a puzzle, but also offers a cash reward for solving it. This is what is happening over at the Computational Complexity blog where there's $289 for managing to solve a graph colouring problem.
This sort of map colouring problem is quite well known in many computer circles as the original four colour problem was the first major mathematical proof that was conducted with the help of a computer program.
We can represent the four colours by the numbers zero to three and simplify the problem somewhat
If we start off with a 1 x 1 grid then we only need 1 colour. A 2 x 2 grid requires 2 colours (the squares in opposite corners aren't adjacent so can have the same colour). As the we increase the size of the grid then the number of colours we need should go up, but will never exceed four.
Write a program that can colour a n x m grid.
The output of the program should be m lines of n digits that represent the colours that are used. I.e. for the 2 x 2 case we can have:
0 1 1 0
Write a program that can colour a n x m grid cycling through the colours one at a time.
I.e. the program starts by placing colour 0 somewhere, then it places colour 1, then colour 2 etc. When it's placed colour 3 it needs to place 0 again. If n x m is divisible by four then there should be equal numbers of each colour. For 2 x 2 we might have:
0 1 2 3
If we interpret each line as a number and sum the numbers we get for the rows, write a program that colours the squares with the minimum sum.
I.e. the above solution produces a total of 24 (1 + 23), but if we move the digits around a bit we can get:
0 3 1 2
This produces a sum of 15 so is better.
What are the lowest sums you can get for a 5 x 5, a 10 x 10 and a 20 x 20 grid?
Just posting the sums is enough.
