文献あり

OMCの技simasima specialを一般化してみた

798

はじめに

この記事は simasima specialの記事の前編をもとに作られています。まだ見ていない人は先に見ることをおすすめします(一応この記事だけ見ても理解できるようにはなっていますが)。
この記事では従来のsimasima specialを拡張し、それを用いてOMC024-Dを鮮やかに解きます！他の問題にも適用できる有用な手法なのでぜひご覧ください。
また厳密な議論には群論の知識を要しますが、この記事では高校数学の範囲内で説明していきます。高校範囲の言葉で語る以上、厳密性が損なわれている箇所があるのはご了承ください。厳密な議論はこちらから。

裏話的ななにか

この記事で紹介する手法は、もともと群論を用いてsimasima specialを記述し直すという Lim_Rim_さんのアイディアに負の個数を持つ集合を加えてsimasima specialを拡張させるという私自身のアイディアの融合によって生まれています。simasimaさんとLim_Rim_さんに感謝申し上げます。思いついた時は去年の夏くらいだったんですが、修論が忙しかったので世に出すのがこんな時期になりました。

京大の作問サークルではこういう議論もしていたり楽しいので、ぜひ入部してね！~~部誌や自作模試もboothで販売しているよ！~~

前置きはこれくらいにして早速みていきましょう！！

集合の演算

まずこの記事の前提知識となる集合の演算について軽く触れておきます（知っている人は飛ばしても大丈夫です）。
集合 $X$ に対して、その要素の個数を $|X|$ で表します。
また要素の個数が有限個の集合を有限集合といいます。そのままですね。
$X$ の部分集合 $A$, $B$ に対して
$A \setminus B = \{x \in A \mid x \not\in B\}$
と定めます。つまり $A$ に属していて $B$ に属していない要素全体の集合です。

次に $X$ の部分集合 $A_1, A_2, \ldots, A_n$ に対して
$A_1 \times \cdots \times A_n = \{(a_1, \ldots, a_n) \mid a_1 \in A_1, \ldots, a_n \in A_n\}$
と定めます。つまり $A_1, A_2, \ldots, A_n$ の要素の組全体の集合です。
特に $A = A_1 = A_2 = \cdots = A_n$ のとき、$A^n = A_1 \times \cdots \times A_n$ と表現します。

simasima specialの復習

議論を簡単にするために、確率の問題は扱わず、場合の数の問題だけ扱います。
確率の問題も守備範囲ではあるのですが、話が難しくなるので…

というわけで、まずは場合の数を扱った通常のsimasima specialの問題を解いていきましょう！(simasima special を使いこなしている方は飛ばしてもok)

さいころを$5$回続けて投げるとき、出た目の和が$5$で割り切れる場合の数を求めよ。

まず、さいころの出た目を並べた $(a_1, a_2, a_3, a_4, a_5)$ を考えます。さいころの出た目として考えられる $X = \{ 1, 2, 3, 4, 5, 6\}$ をつぎの二つの集合に分割します。
$A = \{1, 2, 3, 4, 5\}$, $B = \{ 6 \}$
このとき $(a_1, a_2, a_3, a_4, a_5)$ をそれぞれが属する集合に変換します。例えば
\begin{align*} (1, 3, 6, 4, 6) &\to (A, A, B, A, B) \\ (5, 1, 2, 2, 3) &\to (A, A, A, A, A) \\ (6, 6, 6, 6, 6) &\to (B, B, B, B, B) \end{align*}
のような感じです。
ここで $(A, A, B, B, B)$ に変換されるもののうち、和が$5$で割り切れるものが何個あるか調べてみましょう。
$(A, A, B, B, B)$ に変換される $(a_1, a_2, a_3, a_4, a_5)$ を任意に一つ取り出そう。このとき $a_2, a_3, a_4, a_5$ によらず $(1, a_2, a_3, a_4, a_5), (2, a_2, a_3, a_4, a_5), \ldots, (5, a_2, a_3, a_4, a_5)$ のうちただ一つだけが、その和が$5$の倍数になっています！
よって $(A, A, B, B, B)$ に変換されるもののうち、和が$5$で割り切れるものは $|A|^2|B|^3/5$ 個あることになります。

この議論は $(A, B, A, A, B), (B, B, A, B, A)$ など $(B, B, B, B, B)$ 以外に変換されるものであれば、成立しています。
$(B, B, B, B, B)$ に変換されるものは $(6, 6, 6, 6, 6)$ のみであり、これは和が$5$で割り切れています。それ以外に変換されるものは$1/5$ずつになっていることは既にみました。

以上から
$$ 1 + \frac{6^5 - 1}{5} = \frac{6^5 + 4}{5} $$
が求める答えになります。

このようにsimasima specialとは全体の集合 $X$ を対称性を生み出す部分 $A$ とそれ以外の部分 $B$ にわけることにより、場合の数（確率）の問題を解く方法になっています。

負のsimasima special導入編

まず次の問題を考えます。

京都大学前期文系問題4（1994年改題）

さいころを$n$回続けて投げるとき、出た目の和が$7$で割り切れる場合の数を求めよ。

先ほどと同じように対称性を作ろうとしても中々うまくいかない。
なら無理矢理作ろうということで
$A = \{1, 2, 3, 4, 5, 6, 7\}$, $B = \{7\}$
$S = \{ (a_1, a_2, \ldots, a_n) \in A^n \mid a_1 + a_ 2 + \cdots + a_n \equiv 0 \pmod 7\}$
とします。これにより
$$ \{1, 2, 3, 4, 5, 6 \} = A \setminus B $$
と分解することができます。
また、求めたい場合の数は $|(A \setminus B)^n \cap S|$ に一致します。
ここで次の定理を用います。

$A$ を有限集合、$B$ を $A$ の部分集合とし $S$ を $A^n$ の部分集合とする。
ここで $(a_1, \ldots, a_n)$ が $S$ に属するなら、その任意の並べ替え $(a_{\sigma(1)}, \ldots, a_{\sigma(n)})$ も $S$ に属するとき、次の等式が成立する。
$$ |(A \setminus B)^n \cap S| = \sum_{k = 0}^n (-1)^k { n \choose k } |(\underbrace{A \times \cdots \times A}_{n - k \text{個}} \times \underbrace{B \times \cdots \times B}_{k \text{個}}) \cap S| $$

ここでは詳細な証明は省きますが、$n = 1, 2$ の場合を見ると理解しやすいと思います（包除原理と似た考えです）。
$$ |(A \setminus B) \cap S| = |A \cap S| - |B \cap S| $$
\begin{align*} |(A \setminus B)^2 \cap S| &= |A^2 \cap S| - |(A \times B) \cap S| - |(B \times A) \cap S| + |B^2 \cap S| \\ &= |A^2 \cap S| - 2 |(A \times B) \cap S| + |B^2 \cap S| \end{align*}
これを用いることを考えましょう。 $k \neq n$ ならば $|(\underbrace{A \times \cdots \times A}_{n - k \text{個}} \times \underbrace{B \times \cdots \times B}_{k \text{個}}) \cap S|$には通常のsimasima specialが適用できますね。
次のようになります。
\begin{align*} |(\underbrace{A \times \cdots \times A}_{n - k \text{個}} \times \underbrace{B \times \cdots \times B}_{k \text{個}}) \cap S| &= |\underbrace{A \times \cdots \times A}_{n - k \text{個}} \times \underbrace{B \times \cdots \times B}_{k \text{個}}|/7 \\ &= |A|^{n- k} |B|^k/7 \end{align*}
よって二項定理から
\begin{align*} |(A \setminus B)^n \cap S| &= (-1)^n |B^n \cap S| + \sum_{k = 0}^{n - 1} (-1)^k { n \choose k } |A|^{n- k} |B|^k/7 \\ &= (-1)^n + \frac{|A \setminus B|^n - (-1)^n |B^n|}{7} \\ &= (-1)^n + \frac{6^n - (-1)^n}{7} \\ &= \frac{6^n + 6(-1)^n}{7} \end{align*}
と答えが求められます。

負の個数をもった集合

従来のsimasima specialと前節のsimasima specialを統一的に扱いたいというモチベーションのもとで、負の個数を持った集合を考えます。

先ほどの問題

京都大学前期文系問題4（1994年改題）

さいころを$n$回続けて投げるとき、出た目の和が$7$で割り切れる場合の数を求めよ。

を再び考えましょう。ここでは厳密性を忘れてお気持ちだけ理解してください。

先ほど考えていた集合$B$の代わりに$7$という要素を$-1$個もった仮想的な集合 $B'$ を考えます（これを $B' = - \{ 7 \}$ と表すことにする）。
また仮想的な演算 $|B'| = - 1$, $A + B' = \{1, 2, 3, 4, 5, 6 \}$ が成立しているとします（$7$が $A$ の$1$個と $B'$ の $-1$個で相殺されるイメージ）。

この集合もどき $A$, $B'$ に従来のsimasima specialを適用することを考えます。
さいころの目を並べた $(a_1, a_2, \ldots, a_n)$ をそれらが属する集合（もどき）に変換します。 $(A, A, \ldots, A), \, (A, B', A, \ldots, A), \ldots$ のように。

$(B', B', \ldots, B')$ になる場合は$7$の目が $n$ 個出てくるので、目の和は7で割り切れる。このときの場合の数は$|B'|^n = (-1)^n$.
それ以外の場合は対称性から全体の $1/7$ ずつになるので
\begin{align*} (-1)^n + \frac{|A + B'|^n - |B'|^n}{7} &= (-1)^n + \frac{6^n - (-1)^n}{7} \\ &= \frac{6^n + 6(-1)^n}{7} \end{align*}
となんと先ほどの答えと一致します。

この結果は偶然ではなく、負の個数を持った集合を考える妥当性を裏付けているのです！この結果が偶然ではないことをもう少し見ていきましょう。前節までは $A + B'$ の代わりに $A \setminus B$ を考えていました。前節の最後の式に現れた
$$ |(A \setminus B)^n \cap S| = (-1)^n + \frac{|A \setminus B|^n - (-1)^n |B^n|}{7} $$
という式は先ほどの式
$$ (-1)^n + \frac{|A + B'|^n - |B'|^n}{7} $$
と綺麗に対応していることがわかります！

しかし負の個数を持った集合なんてどうやって正当化するんだ？と思う人もいると思います。詳細は次回にまわすとして、そういった人のためにここでは簡単な説明だけ扱っておきます。
通常の意味での集合 $A$ を任意に取ります。$A$ の通常の意味での部分集合 $B$ は $a \in A$ に対して
$$ f(a) = 1 \, (a \in B), \quad 0 \, (a \not\in B) $$
となる写像 ( なんすか？写像ってという方は関数みたいなものと思ってください) と対応させることができます。
この$1$や$0$というのは部分集合 $B$ に含まれているそれぞれの要素の個数と捉えることができます。すなわち$7$が$-1$個ある集合とは $a \in A$ に対して
$$ f(a) = - 1 \, (a = 7), \quad 0 \, (a \neq 7) $$
となる写像と捉えることができます。次回はこうしたことを掘り下げていきます。

余談ですが、確率を考える際はサイコロの場合であればそれぞれ$1/6$個ずつあると考えるとうまくいきます。

一般化simasima special

次のような問題形式に適用することを考えます（一般にはこれにあてはまらない問題にも適用できますが、それは次回にまわすことにします）。

$m_1, \ldots, m_k$ を正の整数とする。各成分が整数である $k$ 次元ベクトルからなる有限集合 $X$ から要素を取り出して戻す操作を $n$ 回繰り返す。このとき取り出した全てのベクトルの和 $(a_1^{(n)}, \ldots, a_k^{(n)})$ について $a_1^{(n)} \equiv 0 \pmod {m_1}, \ldots, a_k^{(n)} \equiv 0 \pmod {m_k}$ を満たす場合の数を求めよ。

そのままだとわかりにくいと思うので、いくつか具体例をみてみましょう。例えば先ほどの問題であれば $k = 1$, $m_1 = 7$, $X = \{1, 2, 3, 4, 5, 6\}$ となります。

また目標のOMC024-Dもこの問題形式に帰着できます。

OMC024-D (改題)

$13$以下の素数 $2n$ 個からなる順序付いた組 $(a_1, a_2, \ldots, a_n)$ であって、それらすべての積が平方数であるものの個数を求めよ。

$13$以下の素数は$2, 3, 5, 7, 11, 13$になります。
ここで $(x_1, x_2, \ldots, x_6)$ を $2^{x_1}3^{x_2}5^{x_3}7^{x_4}11^{x_5}13^{x_6}$ に対応させます。
例えば $n = 2$ のとき $2, 5, 5, 11$ の積は
$$ (1, 0, 0, 0, 0, 0) + (0, 0, 1, 0, 0, 0) + (0, 0, 1, 0, 0, 0) + (0, 0, 0, 0, 1, 0) = (1, 0, 2, 0, 1, 0) $$
に対応します。また積を取った数が平方数であることは $x_1, \ldots, x_6$ が全て偶数であることと同値ですね。
以上から$k = 6$, $X = \{(1, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0), \ldots, (0, 0, 0, 0, 0, 1) \}$ とし、$m_1 = m_2 = \cdots = m_6 = 2$
とすれば上記の問題形式に帰着できることがわかります。

このとき
$X = A_1 + A_2 + \cdots + A_k + B$ と分割できるとします。ただし $A_1, \ldots, A_k$, $B$ は負の個数をもった集合でも問題ありません。
ここで負の個数をもった集合の要素とは含まれている個数が0でない要素のことを表すものとします。例えば前節の$7$を$-1$個持った集合 $B' = - \{7\}$ であれば $B'$ の要素は$7$のみ（これを $7 \in B'$ と表すことにする）。

ここで各 $i = 1, 2, \ldots, k$ に対して
$$ A_i' = \{(\overline{x_1}, \ldots, \overline{x_n}) \mid (x_1, \ldots, x_n) \in A_i\} $$
とします。ただし $i = 1, 2, \ldots, k$ に対して $\overline{x_i}$ とは $x_i$ を $m_i$ で割った余りです。
例えば $k = 2$, $m_1 = 3$, $m_2 = 5$ であれば
$$ (\overline{2}, \overline{7}) = (\overline{2}, \overline{2}),\quad (\overline{4}, \overline{-1}) = (\overline{1}, \overline{4}), \quad (\overline{-5}, \overline{7}) = (\overline{10}, \overline{-8}) $$
となります（第1成分は$3$で割った余り、第2成分は$5$で割った余り）。

また $(x_1, \ldots, x_n), (y_1, \ldots, y_n) \in A_i$ に対して
$$ (\overline{x_1}, \ldots, \overline{x_n}) \pm (\overline{y_1}, \ldots, \overline{y_n}) \coloneqq (\overline{x_1 \pm y_1}, \ldots, \overline{x_n \pm y_n}) $$
と定めます。
例えば $k = 2$, $m_1 = 3$, $m_2 = 5$ であれば
$$ (\overline{2}, \overline{4}) + (\overline{0}, \overline{3}) = (\overline{2}, \overline{2}), \quad (\overline{1}, \overline{2}) + (\overline{2}, \overline{3}) = (\overline{0}, \overline{0}), \quad (\overline{2}, \overline{3}) - (\overline{1}, \overline{4}) = (\overline{1}, \overline{4}) $$
となります。

いよいよ大詰めです！分割 $X = A_1 + A_2 + \cdots + A_k + B$ がさらに次の条件を満たしてるとしましょう。

$i = 1, 2, \ldots, k$ に対して、任意の $(\overline{x_1}, \ldots, \overline{x_n}), \, (\overline{y_1}, \ldots, \overline{y_n}) \in A_i'$ に対して $(\overline{x_1}, \ldots, \overline{x_n}) \pm (\overline{y_1}, \ldots, \overline{y_n}) \in A_i'$ となる。
$i = 1, 2, \ldots, k$ に対して $|A_i| = d_i h_i$ となる整数 $d_i, h_i$ が取れて以下の条件を満たす。
$i = 1, 2, \ldots, k$ に対して、任意の $(x_1, \ldots, x_n) \in A_i$ に対して $(\overline{x_1}, \ldots, \overline{x_n}) = (\overline{y_1}, \ldots, \overline{y_n})$ となる $(y_1, \ldots, y_n) \in A_i$ の個数は $d_i$ 個。
相異なる $i, j = 1, 2, \ldots, k$ に対して $A_i' \cap A_j'=\{(\overline{0}, \ldots, \overline{0})\}$ となる。
$i = 1, 2, \ldots, k$ に対して $B$ の任意の要素の第 $i$ 成分は $m_i$ で割り切れる。

追記：4つめの条件が抜けていたので修正しました。

このとき、求めたい場合の数は次のように表されます。
(ただし、$\sum$の下の添え字はそれぞれ $1 \leqq i \leqq k$, $1 \leqq i < j \leqq k, \ldots$ を満たす整数（の組）を全て代入して足し合わせるという意味で、$\prod$の記号は $1 \leqq i \leqq k$ を満たす整数を代入して掛け合わせるという意味です）
$$ \prod_{i} \left(1 - \frac{1}{h_i}\right) \left\{ |B|^n + \sum_{i} \frac{|A_i + B|^n}{h_i - 1} + \sum_{i < j} \frac{|A_i + A_j + B|^n}{(h_i - 1)(h_j - 1)} + \cdots \right\} $$ 証明は次回にまわします。この定理はかなり有用なので、その凄さを実感してみましょう！

まずはこれを用いて先ほどのサイコロの問題

京都大学前期文系問題4（1994年改題）

さいころを$n$回続けて投げるとき、出た目の和が$7$で割り切れる場合の数を求めよ。

を解いてみましょう。
$X = \{1, 2, 3, 4, 5, 6\}$, $A = \{ 1, 2, 3, 4, 5, 6, 7 \}$, $B = - \{7 \}$
(つまり $B$ は$7$を$-1$個持った集合)
とし $k = 1$, $m_1 = 7$ とします。
このとき $d_1 = 1$, $h_1 = 7$ とすると実際に上記の4つの性質を満たしています。よって先ほどの定理から
$$ \left(1 - \frac{1}{7}\right)\left\{ (-1)^n + \frac{6^n}{6}\right\} = \frac{6^n + 6(-1)^n}{7} $$
と求められます！

それではいよいよOMC024-Dを解きましょう！

OMC024-D (改題)

$13$以下の素数 $2n$ 個からなる順序付いた組 $(a_1, a_2, \cdots, a_n)$ であって、それらすべての積が平方数であるものの個数を求めよ。

$k = 6$, $X = \{(1, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0), \ldots, (0, 0, 0, 0, 0, 1) \}$ とし、$m_1 = m_2 = \cdots = m_6 = 2$ としていたことを思い出しましょう。ここで
$A_1 = \{ (0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0)\}$,
$A_2 = \{ (0, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0)\}, \ldots,$
$A_6 = \{ (0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 1)\}$,
$B = - 6 \{(0, 0, 0, 0, 0, 0)\}$
($B$ は $ (0, 0, 0, 0, 0, 0)$ を$-6$個もった集合)
とすると $X = A_1 + \cdots + A_6 + B$ と分割できます。
また $d_1 = \cdots = d_6 = 1$, $h_1 = \cdots = h_6 = 2$　となり
これを上の式に適用すると
\begin{align*} &\left(1 - \frac{1}{2}\right)^6 \left\{(-6)^{2n} + { 6 \choose 1 } (-4)^{2n} + { 6 \choose 2 }(-2)^{2n} + { 6 \choose 4 } 2^{2n} + { 6 \choose 5 } 4^{2n} + 6^{2n} \right\} \\ &= \frac{6^{2n} + 6 \cdot 4^{2n} + 15 \cdot 2^{2n}}{32} \end{align*}
となる！

説明の都合上ベクトルで表記していますが、実用上は
$X = \{2, 3, 5, 7, 11, 13\}$, $A_1 = \{1, 2\}, \, A_2 = \{1, 3\}, \ldots, A_6 = \{1, 13\}$, $B = - 6\{ 1 \}$
と表記してもなんら問題はないです。

最後に練習問題をつけたので自力で解いてみてください。

$1$から$7$の面がある$7$面さいころを $n$ 回投げるとき、出た目の積が平方数となるような場合の数を求めよ。

クリックして解答をチェック

先ほどと同じように
$(x_1, x_2, x_3, x_4)$ を $2^{x_1}3^{x_2}5^{x_3}7^{x_4}$ に対応させます。また
$k = 4$, $X = \{(0, 0, 0, 0), (1, 0, 0, 0), (0, 1, 0, 0), (2, 0, 0, 0), (0, 0, 1, 0), (1, 1, 0, 0), (0, 0, 0, 1)\}$
とし $m_1 = m_2 = m_3 = m_4 = 2$ とします。
このとき
$A_1 = \{ (0, 0, 0, 0), (1, 0, 0, 0), (0, 1, 0, 0), (1, 1, 0, 0)\}$
$A_2 = \{ (2, 0, 0, 0), (0, 0, 1, 0) \}$
$A_3 = \{ (0, 0, 0, 0), (0, 0, 0, 1) \}$
$B = - \{ (0, 0, 0, 0)\}$
とし、$d_1 = d_2 = d_3 = 1$, $h_1 = 4$, $h_2 = h_3 = 2$
とすることで上の定理が使える形になりました。よって
\begin{align*} &\left( 1 - \frac{1}{4}\right) \left( 1 - \frac{1}{2}\right)^2 \left\{ (-1)^n + \frac{3^n}{4 - 1} + \frac{1^n}{2 - 1} + \frac{1^n}{2 - 1} + \frac{5^n}{(4 - 1)(2 - 1)} + \frac{5^n}{(4 - 1)(2 - 1)} + \frac{3^n}{(2 - 1)(2 - 1)} + \frac{7^n}{(4 - 1)(2 - 1)^2}\right\} \\ &= \frac{6 + 3 (- 1)^n + 4 \cdot 3^n + 2 \cdot 5^n + 7^n}{16} \end{align*}
と求められます。

この問題でも実用上は
$X = \{ 1, 2, 3, 4, 5, 6, 7\}$, $A_1 = \{ 1, 2, 3, 6\}$, $A_2 = \{4, 5\}$, $A_3 = \{1, 7 \}$, $B = - \{ 1 \}$
として大丈夫です。