Today (January 10th) is Donald Knuth’s 81st birthday. Happy birthday, Dr. Knuth!

Readers of this blog will already know Donald Knuth as the primary author of TeX, Metafont, and WEB; the author of the ongoing “Art of Computer Programming” (TAOCP) series; and one of the two Dons behind the 1998 collaboration that produced a translation of Adventure into a CWEB “literate program.” The beautiful (and fairly informative, and fairly entertaining) result is here, and is also included as pages 235–395 of Knuth’s Selected Papers on Fun & Games (2011).

I met Dr. Knuth a couple of times in real life. The first time was at the Martin Gardner Celebration of Mind at UC Berkeley in 2014. (In those days ambigram expert Scott Kim, familiar to readers of Douglas Hofstadter’s Gödel, Escher, Bach, did a new logo for the Celebration of Mind every year. See “Scott Kim’s rotational ambigrams” (2020-10-18).)

Knuth’s pet puzzle of the day, that day, was a sort of continuous version of a nonattacking queens problem which he called “Peaceful Encampments.” Paraphrased by me:

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.

Back in 2014, I went and wrote a JavaScript visualizer for the problem, and — purely by noodling around, no rigor at all — came up with a few solutions, such as the following five. I conjectured the bottom-right one to be the best possible solution.

I wrote at the time:

The square in the upper left-hand corner has a side of \(a = \left(1 - {1\over\sqrt{3}} \right)\) and the big right isosceles triangle wedged into the lower left corner has a side of \(b = 1 - {a\over 2}.\) This maximizes the size of the (equal) armies, which is \(b^2 - a^2 = \left(1 - {\sqrt{3}\over 2}\right) \approx 0.13397\).

My description of the puzzle continues:

Once you’ve solved that, the next puzzle is to peacefully encamp three armies, four armies, etc… all the way to infinity. Knuth had a raggedy-looking conjectured solution for three armies, and nothing for four or higher.

I’d be interested to know if any further progress has been made on this problem since 2014.

UPDATE, 2019-01-21: My conjectured solution above is not the best possible. I’ve found a better solution with armies of size approximately 0.1458.