24

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

mathlander
  • 1,231
  • 1
  • 8
  • 31
Quuxplusone
  • 1,792
  • 11
  • 24
  • 1
    "...consider a plain represented..." — by any chance do you mean plane? Or is this an alternate spelling of which I am unaware? – user46002 Jan 21 '19 at 21:48
  • 11
    @Hugh: Where else would armies encamp but on a plain? – Quuxplusone Jan 21 '19 at 22:37
  • Ah, I see. Clever wordplay :D – user46002 Jan 21 '19 at 22:50
  • 1
    Is this not the Peaceable Queens problem discussed by N.J. Sloane in http://www.ams.org/journals/notices/201809/rnoti-p1062.pdfhttp://www.ams.org/journals/notices/201809/rnoti-p1062.pdf? – Bernardo Recamán Santos Jan 26 '19 at 00:15
  • 3
    @BernardoRecamánSantos: This is the continuous version of the discrete problem that led to OEIS A250000. I found that out as part of https://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. – Quuxplusone Jan 26 '19 at 00:22
  • @Brandon_J: MAJOR SPOILER ALERT! My best solutions for 2,3,4,5 armies are diagrammed in this blog post. https://quuxplusone.github.io/blog/2019/01/21/peaceful-encampments-round-2/ – Quuxplusone Jan 26 '19 at 00:27
  • Yeah, I ended up finding that via google - great entry, btw! Also, quick note: If the soldiers are actually point-sized, then the size of the encampments don't matter - both of your above pictures hold an infinite number of soldiers. Just being nit-picky :) @Quuxplusone – Brandon_J Jan 26 '19 at 00:39
  • For two armies, couldn't you put a red soldier on all points (a, b) such as a and b are rationals, and a green soldier in those where both a and b are not rationals? – Masclins Jan 28 '19 at 10:21
  • @Masclins: Yes, but that violates the "(No Cantor sets or anything, okay? Just normal plane geometry.)" condition. I don't know the right wording to rigorously nail it down, but the intent is to end up with a finite number of (convex, polygonal) encampments such that we can sum the areas of those encampments to calculate the total size of the army. – Quuxplusone Jan 28 '19 at 15:28
  • 3
    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))) – hexomino Jan 29 '19 at 21:45
  • @hexomino: yikes, good catch! Masclins' point and my rebuff do still apply to constructions like "red on (a,b) such that a and b are both rational; green on (a,b) such that a, b, a−b, and a+b are all irrational." (And to Brandon_J's point: in such an engagement the green army would absolutely trounce the red army, yeah? ;) – Quuxplusone Jan 30 '19 at 01:08
  • If you're still around, perhaps you could self-answer this question? – Brandon_J Jun 01 '19 at 16:09

1 Answers1

10

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

Quuxplusone
  • 1,792
  • 11
  • 24
  • 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.) – Quuxplusone Jun 05 '19 at 13:00