Consider a plain represented by the unit square. On this plain we want to “peacefully encamp” two armies of point-sized soldiers — one army red and one army green. Each soldier “attacks” chess-queen-wise: horizontally, vertically, and diagonally in all directions. The puzzle is to maximize the size of the equal armies (equivalently, maximize the size of the smallest army), given the constraint that no pair of opposing soldiers can be placed attacking each other.
Previously on this blog: Back in 2014 I had conjectured that the optimum solution for two armies was the following. (Each region has size .) This morning I learned that I was very wrong about that!
Last night I was noodling on this problem again (for the more-than-two-army case) and came up with this knight’s-move-inspired solution for 4 armies. Each home-plate-shaped region has size exactly 0.05.
In the above image, I used two colors to illustrate the four-army solution — so the four-army solution (also here) happens to double as a two-army solution of size 0.1. But what if we take that solution and rearrange the colors so that the friendly armies are next to each other instead of diametrically across the board from each other? I expected a modest increase, but after making the switch and jiggling it a bit, I arrived at this interesting configuration!
The vertical lines divide the unit square into fourths; the slashing lines divide the sides of the unit square at the 1/3 and 2/3 marks. So each home-plate-sized region has size , and each slashing region has size , for a total army size of . Wow!
If we take the same four-army solution and color just two armies with the same color, then we get a three-army version. Jiggling that version arrives at these two solutions for three armies. The left-hand solution has army size ; the better right-hand solution has army size . I have not yet done the math to describe this solution algebraically.
Here are two solutions for five armies. On the left, encampments of size ; on the right, encampments of size . Thanks to Benoît Jubin for doing the math on the latter! Benoît also informs me that you can very slightly widen the central encampment here to achieve encampments of size .
Here are four solutions for six armies, of sizes , , , and (my best attempt) , respectively. Again I haven’t done the math to describe these algebraically.
For seven armies, a solution of size .
My best solution for eight armies is based on a solution to the eight queens puzzle; specifically, arrangement number 10 on Wikipedia’s list of the 12 distinct arrangements that solve the puzzle. Solutions based on the other 11 arrangements are available on my GitHub in a rough, unfinished form. This solution has armies of size .