Colourfields – Arthur O'Dwyer – Stuff mostly about C++

Colourfields

Over on the (inexplicably login-walled) site “NewEnigma,”<br>Keith Austin writes:

Draw a 4-by-4 grid. Colour each square red or blue. Select any square, S, and write 1 in it.<br>Then write 1 in every square you can reach from S by a series of moves, where each move is from<br>a square to an adjacent, horizontally, vertically, or diagonally, square of the same colour.

Select any empty square, T, and write 2 in it. Then write 2 in every square you can reach from T<br>by a series of moves. Repeat this procedure for 3 and then 4 and so on until every square has a<br>number. The last number you write down is called the “score” for that colouring. If we imagine<br>the grid is the map of a farm, then you have divided the map into fields, one field for each number.

(1) What is the largest score possible?

(2) If we work with a 5-by-5 grid, what is the largest score possible?

In brief: What is the maximum number of queenwise-connected monochromatic regions you<br>can make by coloring each square of an \(n\times n\) grid either red or blue? If we were asking about<br>rookwise-connected regions, the answer would obviously be \(n^2\). But queenwise-connected is<br>at least slightly less obvious!

For the 5-by-5 grid, the “obvious” answer is

rBrBr<br>BBBBB<br>rBrBr<br>BBBBB<br>rBrBr

for a total of 10 regions. But the answer for 4×4 is not simply

rBrB<br>BBBB<br>rBrB<br>BBBB

for a total of 5; you can in fact make 6 regions! (Once you’ve seen the trick it’s hard to unsee;<br>but I didn’t see it at first myself.)

Discussion on the SeqFan mailing list<br>tentatively produced the sequence: 1, 2, 5, 6, 10, 12, 17, 19, 26, (28?)… Here’s the pattern for<br>odd \(n\), and a conjectured pattern for all even \(n>4\).

For odd \(n\): \(\lceil n/2\rceil^2 + 1\) regions.<br>For even \(n>4\): \(\lceil n/2\rceil^2 + 3\) regions.

Posted 2026-08-05

math

puzzles