Richard Forster
Further to the my eight region strategy for the 5 colour case, here is a
modified version for a nine region 6 colour case:
> 1. Build three mutually touching regions - coloured A, B and C.
>
> Eg.
> AAC
> ABC
> BBC
>
> 2. Add a fourth region that touches all of the previous three and leaves A
> and B "open" - coloured D.
>
> Eg.
> DDD
> AACD
> ABCD
> BBCD
> DDD
>
> 3. Add a fifth region to touch D, so that it does not touch A or B and only
> connects to part of D's edge.
>
> Eg.
> DDD
> AACD
> ABCD5
> BBCD
> DDD
Case 1
======
Suppose region 5 is in colour C - add another region (no 6) touching 5 and D
(but not touching A and B and leaving some of D free) - ie. it can be coloured
A, B or a new colour E.
1a: If this region is coloured E we can surround the entire map with a 7th
region (forcing 6 colours with 7 regions), since it touches each colour must
be in colour 6.
1b: Suppose we colour region 6 in colour B (there is a parity issue here with
whether this region is "above" / "below" region 5 as compared to whether the
original region A is "above" / "below" B). We can now add another region
connecting D (but not all), 5, 6 and neither of the original As or Bs:
DDD
AACD
ABCDCC
BBCDBA
DDDAA
This can now be partially surrounded by an region that must be in colour E:
DDD
AACD
ABCDCCE
BBCDBAE
EDDDAAE
EEEEEEE
Since the outside of this map has A, B, C, D and E a sixth colour is needed
for a totally surrounding region - forcing 6 colours with 9 regions.
1c. Suppose we colour region 6 in colour A.
We add a seventh region that partially wraps the map and must be coloured with
a new colour:
EEEEE
EEDDDE
EAACDE
EABCDCC
EBBCDBA
DDDAA
Since the outside of this map has A, B, C, D and E a sixth colour is needed
for a totally surrounding region - forcing 6 colours with 8 regions.
Case 2
======
Suppose region 5 was coloured with (wlog) A. Aa new region 6 - touching part
of D, region 5 and not the original regions A or B (which has the opposite
"above"/"below" parity to the original A and B. This can be coloured B, C or
a new colour E.
DDD
AACD6
ABCDAA
BBCD
DDD
2a. If region 6 is coloured E we can surround the entire map with a region
which touches each colour - forcing 6 colours in 7 regions.
2b. Suppose the new region is in colour B. We can now add a new region touch
regions D (partially) 5 and 6 (but not the original A or B) which is either
coloured E (thus being in a similar situation to 2a allowing a surrounding
region to force 6 colours in 7 regions) or C. In this latter case we can add
a partially surrounding region which is forced to be coloured E:
EEEEE
EEDDDCC
EAACDBC
EABCDAA
EBBCD
DDD
This can be surrounded by a new region which must be in a sixth colour -
forcing 6 colours in 9 regions.
2c. Suppose the new region is in colour C - we can partially surround it
with a region that must be coloured E:
EEEEE
EEDDDE
EAACDC
EABCDAA
EBBCD
DDD
This can be surrounded by a new region which must be in a sixth colour -
forcing 6 colours in 8 regions.
-------------------------------------------------------------------------------
Outcome 1 leads to a 5-region solution:
(where number indicates order)
(where letter indicates color)
---------------------------
| |
---------------------- |
| | | | |
| 3C | 1A | 2B | |
| | | | |
¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬ |
| 4D | |
¬¬¬¬¬¬¬¬¬¬¬¬¬ 5E |
| |
¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬
Check:
Region 4 forces D since it touches A,B,C
Region 5 forces E since it tocuhes A,B,C,D
Outcome 2 leads to a 6-region solution:
(where number indicates order)
(where letter indicates color)
-----------------------------
| |
| |
| ----------------- |
| | | |
---------------------- | |
| | | | | |
| 3B | 1A | 2B | | |
| | | | | |
¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬ | |
| 4C | | |
¬¬¬¬¬¬¬¬¬¬¬¬¬ 5D | |
| | | |
| ¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬ |
| |
| 6E |
| |
¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬
Check
Region 4 forces C since it touches A,B
Region 5 forces D since it tocuhes A,B,C
Region 6 forces E since it touches A,B,C,D
Better?
M.
Michael J D Dufour
----------------------------------------------------------------
turns 1,2, and 3 are obviously different colors. If 4 or
5 contain the fourth color, then 6A is not performed, and 6B is performed,
and the game is over. If 4 and 5 are the same as 2 and 3, then 6A is the 4th
color, and 7 ends the game.
Tom Jolly
-----------------------------------------------------------------
After four regions like this:
.-~~-.
/` `\
( X )
.-~~-. .-~~-.
/` `\ `\
( 1 ) 2 )
\_ _/ _/
~-__-~ ~-__-~
( Y )
\. ./
`----'
if X and Y are different colors, we save a move. Otherwise,
force a fourth color:
_.------._
/` 4 `\
/` .-~~-. `\
| /` `\ |
| ( 3 ) |
\ .-~~-. .-~~-. /
/` `\ `\
( 1 ) 2 )
\_ _/ _/
~-__-~ ~-__-~
( 3 )
\. ./
`----'
Then the sixth move forces the fifth color.
_.------._
/` 4 `\
/` .-~~-. `\
| /` `\ |
| ( 3 ) |
./\ .-~~-. .-~~-. /\.
/ /` `\ `\ \
| ( 1 ) 2 ) |
| \_ _/ _/ |
\ ~-__-~ ~-__-~ /
\ ( 3 ) /
\ \. ./ /
\. `----' ./
\. 5 ./
`--------'
Skiddley-doodley, as Ned Flanders would say.
I think I've got a way to force N colors in 2^(N-2)+1 steps. It's
suboptimal for N=5, but I don't know about N=6.
Dan Hoey
-------------------------------------------------------------------
I found an even better solution for the 5 color that wins in 6 regions.
Label the 1st through 5th colors as A, E, I, O, & U. The solution is as follows:
1) Place three regions in a circular pattern such that each one must
necessarily be of the next color in the sequence:
AAAAAA
A A
A A
E I
E I
EEEIII
2) Now place another region in the center of this circle. If it is colored a
fourth color, the game is won on the next turn by choosing the rest of the
circle's interior as the last region. So the second player will obviously pick one
of the first three colors:
AAAAAA
A A
A AA A
E AA I
E I
EEEIII
3) The game is now won in 2 moves by placing a region that touches the center
region and the 2 outer regions of different colors followed by a region
consisting of the rest of the circle's interior:
AAAAAA
AUUUUA
AUAAUA
EUAAUI
EUOOUI
EEEIII
Thus, the 5 color game can be won in 6 regions. I believe this is minimal.
Clint Weaver
Ed,
This is going to be a long one. In response to Alexander Kovaldzhi's "Map
Coloring Game", I have found a strategy that wins against 5 colors in 7 regions
and 6 colors in 8 regions. Let us label the 1st through 6th colors A, E, I, O,
U, & Y. The strategy is as follows:
1) Start with your first 2 regions as parallel rectangles some arbitrary
distance apart. There are only 2 possible combinations of colors:
AAAAAAA AAAAAAA
or
AAAAAAA EEEEEEE
2) In the case of 2 identical regions, connect them with a single rectangular
region (necessarily color "E"). Then place small "L" shaped regions in
opposing corners. There are only 2 combinations of colors for the "L" shaped regions:
AAAAAAA AAAAAAA
EII EOO
EI EO
E E
E or E
E E
IE IE
IIE IIE
AAAAAAA AAAAAAA
3) These are won in 2 moves and 1 move respectively using the remaining
colors, thus winning in either 7 or 6 regions respectively:
AAAAAAA AAAAAAA
EIIO EOO
EIOO EO
EOO EU
EU or EU
EU EU
IEU IEU
UUIIEUUUU UUIIEUUUU
UAAAAAAAU UAAAAAAAU
UUUUUUUUU UUUUUUUUU
4) For the case in Step 1 involving 2 colors, the next step is to place 2
rectangle regions perpendicular to the previous two regions. These regions point
toward each other and almost touch. There are five possible combinations for
this:
AAAAAAA AAAAAAA AAAAAAA AAAAAAA AAAAAAA
I E I E I
I E I E I
I E I E I
or or or or
I I A A O
I I A A O
I I A A O
EEEEEEE EEEEEEE EEEEEEE EEEEEEE EEEEEEE
5) From each of these, a particular regions is placed that passes through the
middle gap. This region is necessarily of the next color in the sequence
(which wins with the last case for a total of 5 regions):
AAAAAAA AAAAAAA AAAAAAA AAAAAAA AAAAAAA
OI OEO I E UI
OI OEO I E UI
OI OEO I E UI
OOO or OOO or OOO or III UUU
IO I OAO A OU
IO I OAO A OU
IO I OAO A OU
EEEEEEE EEEEEEE EEEEEEE EEEEEEE EEEEEEE
6) From here, the other four can be won in 1 move, 1 move, 1 move, and 2 moves
respectively using the remaining colors, thus winning in 6, 6, 6, or 7 regions
respectively:
AAAAAAA AAAAAAA AAAAAAA AAAAAAA
OIU OEOU IU EO
OIU OEOU IU EO
OIUU OEOU IUU EOU
OOOU or OOOU or OOOU or IIIU
IOU IUU OAOU AUU
IOU IU OAOU AU
IOU IU OAOU AU
EEEEEEE EEEEEEE EEEEEEE EEEEEEE
7) Using the same strategy, a single extra move wins the 6 color game from
each of the afore mentioned final positions:
YYYYYYYYY YYYYYYYYY YYYYYYYYY YYYYYYYYY YYYYYYYYY YYYYYYYYY YYYYYYYYY
YAAAAAAAY YAAAAAAAY YAAAAAAAY YAAAAAAAY YAAAAAAAY YAAAAAAAY YAAAAAAAY
YYYYEIIOY YYYYEOOYY YYYOIUYYY YYYOEOUYY YYYYIUYYY YYYYEOYYY YYYUIYYYY
YEIOO YEO YOIU YOEOU YIU YEOY YUI
YEOO YEU YOIUU YOEOU YYIUU YEOU YUI
YEU or YEU or YOOOU or YOOOU or YOOOU or IIIU or YUUU
YYEU YEU YYIOU YYIUU YOAOU AUU YYOU
YYIEU YYIEU YIOU YIU YOAOU AU YOU
UUIIEUUUU UUIIEUUUU YIOU YIU YOAOU AU YOU
UAAAAAAAU UAAAAAAAU EEEEEEE EEEEEEE EEEEEEE EEEEEEE EEEEEEE
UUUUUUUUU UUUUUUUUU
That's my analysis of the problem. It takes 7 regions to win against 5
colors, and 8 regions to win against 6 colors. I have some color pictures of the 6
color final positions. If you would like to see them, just let me know. Also,
send my thanks to Alexander Kovaldzhi for a pretty neat puzzle.
Clint Weaver