24
$\begingroup$

This math puzzle is due to Donald Knuth (as far as I know; maybe he got it from someone else) circa 2014.

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.

(No Cantor sets or anything, okay? Just normal polygons.)

I have a conjectured answer but I don't know if it's really the optimum. If this would be more on-topic for math.SE or something, please comment and let me know!

I have written a little Javascript program to help visualize solutions. You can find it here.

Here are two examples of ways to peacefully encamp armies of sub-maximum size. The total size of each army in the first solution is 1/9; the total size of each army in the second solution is 1/8.

example1 example2

Once you’ve solved that, the next puzzle is to peacefully encamp three armies, four armies, etc... all the way to infinity.

My own candidate solutions have army size $\frac{7}{48} \approx 0.1458$ (for 2 armies), $\sim 0.0718$ (for 3 armies), $0.05$ (for 4 armies), and $\sim 0.0311$ (for 5 armies).

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ "...consider a plain represented..." — by any chance do you mean plane? Or is this an alternate spelling of which I am unaware? $\endgroup$
    – user46002
    Commented Jan 21, 2019 at 21:48
  • 11
    $\begingroup$ @Hugh: Where else would armies encamp but on a plain? $\endgroup$
    – Quuxplusone
    Commented Jan 21, 2019 at 22:37
  • 1
    $\begingroup$ Is this not the Peaceable Queens problem discussed by N.J. Sloane in ams.org/journals/notices/201809/rnoti-p1062.pdfhttp://…? $\endgroup$
    – Bernardo Recamán Santos
    Commented Jan 26, 2019 at 0:15
  • 3
    $\begingroup$ @BernardoRecamánSantos: This is the continuous version of the discrete problem that led to OEIS A250000. I found that out as part of puzzling.stackexchange.com/questions/78727. ("It was added to the OEIS in 2014 by Donald E. Knuth...") Thanks for the "construction found by Benoît Jubin" — it matches my best attempt for 2 armies — but that reference doesn't go so far as to claim it's absolutely optimum for 2 continuous armies (can that be proven?). Also, A250000 doesn't address the $k$-army problem for $k > 2$, at all. $\endgroup$
    – Quuxplusone
    Commented Jan 26, 2019 at 0:22
  • 3
    $\begingroup$ Also, @Masclins there are many examples where a red soldier attacks a green soldier in that example (for instance (1/2, 1/2) and (1/sqrt(2), 1/sqrt(2))) $\endgroup$
    – hexomino
    Commented Jan 29, 2019 at 21:45

1 Answer 1

Reset to default
10
$\begingroup$

My best solution for two equal-sized armies gives each army an area of exactly $\frac{7}{48} \approx 0.1458$.

https://quuxplusone.github.io/blog/images/2019-01-21-1458.png 3

I am not aware of any proof that this is the best solution for two armies. However, you can approximate our point-sized soldiers with regular chess queens on an NxN board, and it turns out that many provably best solutions to that discrete problem for increasingly large N end up looking suspiciously similar to this arrangement of armies, and suspiciously dissimilar to anything else. For example.

Another suspiciously similar diagram appears as Figure 4 of Notices of the AMS, volume 65, number 9, in an article on OEIS sequence number A250000:

Notices of the AMS screenshot

(Thanks to this commenter for the link!)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Previously the last sentence of this answer, now moved into a comment since it's not directly relevant to the 2-army question: My best solutions for 3, 4, 5, 6, 7, 8 armies are available on my blog at "Peaceful Encampments, round 2." (I'll update the linked post if I ever improve these solutions.) $\endgroup$
    – Quuxplusone
    Commented Jun 5, 2019 at 13:00

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