モスクワ数学オリンピック第29回 Tour 2 Grade 9-11 問5

モスクワ数学オリンピック第29回 (1966) Tour 2 Grade 9-11 問5. $11 \times 11$マスのチェッカーボードのうち$22$マスにマークがおいてあり，各行・列に丁度2つのマークが並んでいる．2つの並べ方が同値であるとは，片方のチェッカーボードに行・列の入れ替えを有限回だけ施してもう一方のチェッカーボードの並べ方に等しくなることをいう．互いに同値でないマークの並べ方は何通りあるか．

解答

$2\times 2$マスだと次の並べ方しかない．

$3\times 3$マスだと次のみ．

以上の並べ方を一般化して，次のような並べ方を既約な並べ方と呼ぶ．

$L(n)$で$n\times n$マスからなる既約な並べ方を表すものとすると，任意の並べ方は行・列を並べ替えて次のような形にできる．
\begin{align}
\begin{bmatrix}
L(n_1) & & & \\
& L(n_2) & & \\
& & \ddots & \\
& & & L(n_k)
\end{bmatrix}
\end{align}
ただし
\begin{align}
\begin{array}[c]
\ 2 \leq n_1\leq n_2\leq\cdots\leq n_k\\
n_1+n_2+\cdots+n_k=n
\end{array}
\end{align}
とする．この並べ方が完全代表系になることを示す．$\{L(m_i)\}_{i=1,\ldots,k}$，$\{L(n_j)\}_{j=1,\ldots,l}$をそれぞれ対角に並べて作ったチェッカーボード$K_1$, $K_2$が同値になったとする．$m_1\leq n_1$と仮定しても一般性を失わない．$K_1$から$m_1$行$m_1$列をうまく選んで部分チェッカーボードを作るとまたどの行・列にも$2$つのマークがあるようにできる．（$L(m_1)$のことである．）この性質は$K_2$においても成り立つ．$K_2$の既約な部分チェッカーボード$L(n_j)$の任意の行か列を1つ選んでそこから$2$つのマークが並ぶよう行や列を増やしていくと，$L(n_j)$のすべての行・列が選ばれてしまう．よって$L(m_1)=L(n_1)$である．帰納法より一般のサイズのチェッカーボードで$K_1=K_2$が従う．
従って答えは$11$を$2$以上の整数で分割する場合の数に等しい．これは$14$通りある．