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