8
$\begingroup$

Here's a map, which I found here:

enter image description here

Your challenge is to four-color this map while minimizing your use of the fourth color.

More specifically, color the map with four colors so each region is a different color from all of its neighboring regions. Your score is the number of regions colored in your least-used color.

For instance, if you colored the map red, blue, green, and yellow, using red 30 times, blue 28 times, green 26 times, and yellow 28 times, your score would be 26.

The lowest score wins. Proofs that it is impossible to achieve a smaller score are also welcome.

I have achieved a score of

8

and I believe that is the lowest possible score, but feel free to try to outdo me.

$\endgroup$

1 Answer 1

6
$\begingroup$

I know it is optimal:

First picture:
1: Each pink tile is surrounded by 5 tiles, such a pink tile and its neighbors contain all 4 colors
2: The yellow, green, purple, and red group all contain four colors.
Second picture:
3: The only way to allocate more than 3 pink tiles a minimal-used-color tile -black- is to use the big areas. A 7th black tile is needed for the top pink, thus 7 is only possible if the red-group black tile is adjacent to the bottom pink.
4: However the pinks in the center allow only only way for the yellow group to have a black tile at the outside (the orange tile). With this the only possible black 'outside' green tile is the dark green one, the only black 'outside' purple one is the dark purple one, and the only black 'outside' red one is the dark red one. This is not adjacent to the pink tile so an 8th black tile is required.
Third picture:
Using the 'efficient' tiles for the minimal-used-color, coloring is almost automatic from any position, only around the bottom pink one needs to be careful: the adjacent yellows are both next to black and light gray, so must be white and dark grey. Therefore the red tile must be black, and the pink tile white for a correct solution scoring 8. enter image description here

$\endgroup$

Your Answer

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

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