5
$\begingroup$

Here is a very interesting question that my professor and I came up with today. We came up with it while discussing another problem, and I'm very curious to see how this pans out!

Question: Suppose that you have 32 chess sets and a 32 x 32 board. The chess sets are standard, consisting of 16 white pieces (8 pawns, 2 castles, 2 knights, 2 bishops, 1 queen and 1 king), and 16 black pieces (same as white) each. How many ways can you arrange the pieces on the board so that all of the rows and columns form chess sets?

Thoughts: Clearly, the number of ways that you can arrange the pieces in the first row is $$\frac{32!}{(8!(2!)^3)^2}$$

The second row is also relatively easy, as the only restriction is that you cannot have two kings or queens of the same colour in the same column. After that it gets a bit tricky, because there is no guarantee that there are already two castles, knights or bishops in the same column. Obviously, as you work down the columns it becomes more probable that there are already the sufficient number of any given piece in the columns. However, the complexity that immediately arises from this method begs the question of whether or not multiplying out the number of arrangements for each row is the most efficient way of approaching this problem. I'm quite a beginner at combinatorics, and simply thought that it would be an interesting problem to give to this community, as well an opportunity to open my eyes to an area unfamiliar to me.

$\endgroup$
  • 2
    $\begingroup$ I would try placing the kings and queens first, then knights, rooks and bishops, because then the places for the pawns are set. If you organise it by piece type rather than by row, the problem you describe won't happen. It still doesn't look very easy though. $\endgroup$ – Mark Bennet Feb 6 '15 at 14:41
  • $\begingroup$ I don't understand what you mean by "complete sets in the columns" $\endgroup$ – Andrew Szymczak Feb 7 '15 at 2:27
  • 1
    $\begingroup$ This is also known as the number of $(8,8,2,2,2,2,2,2,1,1,1,1)$-frequency squares, or, equivalently, the number of decompositions of $K_{32,32}$ into two $8$-regular spanning subgraphs, six $2$-regular spanning subgraphs, and four $1$-regular spanning subgraphs. Any answer is likely to consist of stating: (a) there's a lot, (b) it's not going to be possible to compute the exact answer, and (c) we can get a (crude) lower bound by identifying symbols in Latin squares of order $32$. $\endgroup$ – Rebecca J. Stones Feb 7 '15 at 3:57
  • 1
    $\begingroup$ @eloiPrime for some value of "rescue" :-) $\endgroup$ – Joffan Feb 7 '15 at 5:36
  • 1
    $\begingroup$ As it stands, I'd say undergraduate. For this, and the enumeration of frequency squares in general, most methods I've seen used a combination of elementary techniques (i.e., no mathematical machinery), and computer enumeration (requiring some skill in programming). That being said, the obvious enumeration problems are open problems, and have been for a long time. $\endgroup$ – Rebecca J. Stones Feb 9 '15 at 2:40

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.