14
$\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 plane geometry.)

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).

$\endgroup$
  • $\begingroup$ "...consider a plain represented..." — by any chance do you mean plane? Or is this an alternate spelling of which I am unaware? $\endgroup$ – Hugh Jan 21 at 21:48
  • 5
    $\begingroup$ @Hugh: Where else would armies encamp but on a plain? $\endgroup$ – Quuxplusone Jan 21 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 Jan 26 at 0:15
  • 2
    $\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 Jan 26 at 0:22
  • 2
    $\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 Jan 29 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.