4
$\begingroup$

This is a sort of a sub-problem of the open puzzle Peaceful Encampments, for high numbers of armies.

Consider a chessboard with an astronomically large number of vanishingly small squares, on which we place six contiguous armies of queens — a red army, a green army, a blue army, a magenta army, a yellow army, and a cyan army — such that no queen is ever threatened by a queen of any other color. Here are four possible ways those armies could appear on the board:

Consider the upper-left image here. Scan it from left to right; you encounter the armies in the order "G-R-B-M-C-Y". Scan it from top to bottom: "M-R-G-Y-C-B". Scan it backslashwards from upper left to lower right: "G-R-M-B-C-Y". Scan it slashwards from lower left to upper right: "B-G-R-C-Y-M".

I claim that these four scans uniquely identify this particular arrangement of armies. So the four arrangements in the picture above can be summarized as:

Upper left: GRBMCY MRGYCB GRMBCY BGRCYM.
Upper right: GRBMCY MRYGCB RGMBYC BGRCYM.
Lower left: RGBMYC RMGYBC RGMBYC BGRCMY.
Lower right: RGBMYC MRYGCB RMGYBC BGRCYM.

So my combinatorial puzzle is:

How many different ways are there to arrange six armies on the board?

It would be reasonable to rearrange the colors so that the encoding always begins with, say, RGBCMY. I was a bit too lazy to do that when making these diagrams. But if we do that, we get these four encodings:

Upper left: RGBCMY CGRYMB RGCBMY BRGMYC.
Upper right: RGBCMY CGYRMB GRCBYM BRGMYC.
Lower left: RGBCMY RCGMBY RGCBMY BGRYCM.
Lower right: RGBCMY CRMGYB RCGMBY BGRYMC.

Daniel Mathias adds these, one of which is "simple" and the other five of which are rotations of just one part of my first solution:

RGBCMY RGBCMY RGBCMY RGBCMY (the "simple" solution).
RGBCMY CGRYMB GRCBMY BRGMYC.
RGBCMY CRGYMB RGCBMY BGRMYC.
RGBCMY CRGYMB RGCBMY BRGMYC.
RGBCMY CGRYMB RGCBMY BRGMYC.
RGBCMY CGRYMB GRCBMY BRGMYC.
(And so on...)

Images of the solutions above

$\endgroup$
  • 1
    $\begingroup$ My final answer is 1990 distinct arrangements of camps. See edited answer. $\endgroup$ – Daniel Mathias Feb 8 at 0:02
5
$\begingroup$

Preface: As this is primarily an exercise in counting, and not a puzzle per se, there are no spoiler tags in this post, which aims to provide a method for counting the number of distinct arrangements of six camps. My initial comments, which prompted an edit to the question, have been removed.


As Ben Barden pointed out, for any given left-to-right order, each of the $6!$ permutations is a valid top-to-bottom order. Of course, not all of these permutations give a unique arrangement of camps. The two permutations show in the first image give arrangements that are reflections across the upward diagonal. This first step in counting the total number of solutions requires us to find each unique solution to 'six non-attacking rooks on a 6x6 board.'

enter image description here

For each unique solution found in the first step, we need to find the number of ways the camps can be ordered along the diagonals. We do this by passing a diagonal line across the field, noting the order in which the camps are encountered. For this first example, there is a unique ordering along each diagonal, giving exactly one solution for this arrangement.

enter image description here

Now let's consider another arrangement:

enter image description here

This arrangement has multiple camps on the same diagonal, and these camps can be encountered in any order. For example, we could have RBGYCM-GRMCBY or BRCYGM-GRCMBY. For the order along the downward diagonal, (R,B),(G,C,Y),M gives us $2!\cdot3!\cdot1=12$ possible orders, while G,R,(C,M),B,Y gives us $2$ orders along the upward diagonal. This gives us a combined $24$ possible orders along the diagonals, but the inherent symmetry of this arrangement means that only $12$ of these are distinct.

enter image description here

Solving the first step (the non-attacking rooks) is simple (there are 115 distinct solutions), but determining the number of unique solutions overall requires more work. There are a total of 1999 distinct camp arrangements. Previous counting errors have been corrected. The image below shows each of the 115 base arrangements, along with the number of distinct camp arrangements associated with each. The arrangements with the darker border have rotational symmetry which has been specifically accounted for. The others are counted using only the method described above, taking into account the mirror symmetry where applicable. Note that while the arrangements are distinct, some have only trivial variations (such as those I previously mentioned) that will not affect the size of the camps.

enter image description here

$\endgroup$
  • $\begingroup$ This does not actually answer the question. You have to find out how many arrangements there are, not just one that differs from the four examples. $\endgroup$ – Jaap Scherphuis Feb 4 at 16:40
  • 2
    $\begingroup$ @JaapScherphuis Given related information not presented in the question, I suspect that the solution is not yet known by Quuxplusone. This answer is only my initial observation, and provides insight to a possible solution. Downvoting the answer just because you don't understand it is not appreciated. (Your comment without downvote would have been more appropriate. $\endgroup$ – Daniel Mathias Feb 4 at 16:51
  • 1
    $\begingroup$ Given that it's a sub-problem to an open puzzle, it is highly likely that the solution is not yet known. Also, the provided new solution can be mirrored top-to-bottom for a trivial variation. $\endgroup$ – Ben Barden Feb 4 at 17:11
  • $\begingroup$ @BenBarden: If someone can figure out wording to disallow completely trivial variations (mirroring, 90-degree rotating of the whole solution), I'll adopt it into the problem statement! Daniel is correct that I don't know the solution, btw. $\endgroup$ – Quuxplusone Feb 4 at 17:28
  • 1
    $\begingroup$ @Quuxplusone There are five errors in my counts. Here are your solutions:1999 distinct camps $\endgroup$ – Daniel Mathias Feb 18 at 20:26
1
$\begingroup$

I note that the "peaceful encampments" aspect can be trivially ignored for the question here. There's no reason why we'd have to make any of them larger than a point. (Or, alternately, we can solve for point-source armies, and then trivially expand into available space as necessary). Thus, any arrangement of right-to-left can go with any arrangement of top-to-bottom. My intuition is that the first diagonal can be ordered at will so long as (A is down from B) and (A is left of B) always implies (A is diagonally down/left of B). The second diagonal has that limit, but my intuition is that there is also a further limit based on the first diagonal on combination with the top-to-bottom and right-to-left status.

...or, to put it another way...

  • start with a set of six points.
  • each point has an X and a Y.
  • no two points may have identical X, Y, (X+Y), or (X-Y)
  • Label the points A through F, ordered by X coord.
  • Produce an ordering for those letters via Y coord, (X+Y), and (X-Y)
  • how many distinct ordering sets are there?

/************/

For any two points...

  • if (Xa > Xb) && (Ya > Yb) -> (X+Ya > X+Yb)
  • if (Xa > Xb) && (Ya < Yb) -> (X-Ya > X-Yb)
  • ???

I'm not sure if there is a further constraint beyond that.

if ord(X) == ord(Y) then ord(X+Y) is fully constrained, and ord(X-Y) is fully unconstrained. The opposite occurs if ord(X) is the inverse of ord(Y). I m unclear about the non-degenerate cases, though.

$\endgroup$

Your Answer

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

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