OMC012(F) - アーカイブ

※かつて公式解説が存在しなかったときのものです

　$2047$ を一般に $n \ge 1$ とおき，仮定の置き方を $a_n$ 通りとして，これを求める．

• 石のない列が存在するとき．
  　黒石を固定したとき，白石の並べ方の総数は攪乱順列と同じ$$．よって，求める場合の数は $$\left(n+1\right)! \times n!\sum_{k=0}^n\frac{\left(-1\right)^k}{k!}.$$
• 全ての列に少なくとも一方の石があるとき．
  　$n = 1$ では $2$ 通り．$n \ge 2$ の場合，白石のみの列の白石を固定すると，残りの石の並べ方の総数は $n - 1$ の場合と同じ*．よって $a_0 = 1$ とすれば，求める場合の数は $n \left(n + 1\right) a_{n-1}$ 通り．

　したがって $$a_n = n \left(n + 1\right) a_{n-1} + \left(n+1\right)! \times n!\sum_{k=0}^n\frac{\left(-1\right)^k}{k!}$$ であり，帰納的に $$a_n = n! \left(n + 1\right)! \sum_{k=0}^n\frac{\left(n - k + 1\right)\left(-1\right)^k}{k!}$$ を得る．よって $S = 2045!\sum\limits_{k=0}^{2045}\dfrac{\left(2048 - k\right)\left(-1\right)^k}{k!}$ とおくと $$N = a_{2047} = 2047! \times 2048! \left(\frac S{2045!} + \frac2{2046!} - \frac1{2047!}\right) = 2048! \times \left(2047 \times 341 \times 6S + 4093\right)\mathclose{}.$$ $S$ は整数であるから，Legendre の定理より $a = 2047,\, b = 1019$ が得られ，求める数値は $ab = \mathbf{2085893}$．

*　白石のみの列およびその列の白石のある行を考え，その行と列以外の石を並べてから，残りの黒石 $1$ つを適切な場所におけばよい．