OMCの技 simasima special 解説 (前編)

5303

はじめに

simasima special は筆者が発見した競技数学の技です。数え上げや確率・期待値の問題で有用です。漸化式や多項式での考察をスキップする事が出来ます。中々文字で説明するのは難しいので具体例をたくさん持ってきました。早速見てみましょう。

(余談:simasima specialのネーミングセンスの元ネタがヤジリンのテクニックである厚揚げスペシャル(青い厚揚げ氏)と最近分かった)

この記事で出てくる $n$ 面サイコロは $1$ から $n$ までの目が等確率で出るサイコロの事を指します。
$n$ にサイコロではありえない自然数が入る事がありますが、気にしないでください。

対称性を見つけよう

まずは簡単な問題から始めましょう。

丁半

$2$ つの $6$ 面サイコロ $a_{1}, a_{2}$ を振る時、出た目の和が奇数になる確率を求めよ。

出目の偶奇のパターンは $4$ パターンあります。

$a_{1}$	$a_{2}$	和	確率
奇数	奇数	偶数	$\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$
奇数	偶数	奇数	$\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$
偶数	奇数	奇数	$\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$
偶数	偶数	偶数	$\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$

和が奇数になる確率は $\frac{1}{4} + \frac{1}{4} = \frac{1}{2}$ です。
次の問題も解いてみましょう。

変な丁半

$6$ 面サイコロ $a_{1}$ と $7$ 面サイコロ $a_{2}$ を振る時、出た目の和が奇数になる確率を求めよ。

7面サイコロは厄介ですね。
今回も出目の偶奇のパターンは $4$ パターンあります。

$a_{1}$	$a_{2}$	和	確率
奇数	奇数	偶数	$\frac{1}{2} \times \frac{4}{7} = \frac{2}{7}$
奇数	偶数	奇数	$\frac{1}{2} \times \frac{3}{7} = \frac{3}{14}$
偶数	奇数	奇数	$\frac{1}{2} \times \frac{4}{7} = \frac{2}{7}$
偶数	偶数	偶数	$\frac{1}{2} \times \frac{3}{7} = \frac{3}{14}$

和が奇数になる確率は $\frac{2}{7} + \frac{3}{14} = \frac{1}{2}$ です。
これを見て何か気付かないでしょうか。
上二行と下二行を比べてみましょう。
$a_{2}$ が奇数の時、 $a_{1}$ が偶数であれば和の条件を満たします。逆に $a_{1}$ が奇数であれば和の条件を満たしません。
$a_{2}$ が偶数の時、 $a_{1}$ が奇数であれば和の条件を満たします。逆に $a_{1}$ が偶数であれば和の条件を満たしません。
$a_{1}$ が偶数か奇数かは $\frac{1}{2}$ で等確率なので、 $a_{2}$ がどんな確率であれ、対称性から結局和が奇数になる確率は $\frac{1}{2}$ になるのです。

この考え方にピンとこなかった人は別の考え方をしましょう。
$7$ 面サイコロを先に振り $6$ 面サイコロを後に振る事にします。

$a_{2}$	$a_{1}$	和	確率
奇数	奇数	偶数	$\frac{4}{7} \times \frac{1}{2} = \frac{2}{7}$
奇数	偶数	奇数	$\frac{4}{7} \times \frac{1}{2} = \frac{2}{7}$
偶数	奇数	奇数	$\frac{3}{7} \times \frac{1}{2} = \frac{3}{14}$
偶数	偶数	偶数	$\frac{3}{7} \times \frac{1}{2} = \frac{3}{14}$

この時 $7$ 面サイコロの出目がどうであれ、 $6$ 面サイコロの偶数と奇数の内一方が出れば和が奇数になり、もう一方が出れば偶数になります。
なので確率は結局 $\frac{1}{2}$ になります。

結局 $6$ 面サイコロ $a_{1}$ が存在することで、他のサイコロに関係なく確率が $\frac{1}{2}$ になってしまうのです。

補足

後に振るという考え方の方が分かりやすいのですが、この後の拡張の導入として考えると、対称性の考え方も重要です。

3の倍数

$6$ 面サイコロ $a_{1}$ と $7$ 面サイコロ $a_{2}$ を振る時、出た目の和が $3$ の倍数になる確率を求めよ。

対称性から答えは $\frac{1}{3}$ になります。
$a_{2}$ を先に振ると考えても、結局 $a_{1}$ の出目で決まるので $\frac{1}{3}$ になりますね。

OMC165-Eの最後の部分の考察

数列 $b_{1}, b_{2}, . . . b_{7}$ ( $b_{i} \in {0, 1}$ )と $k \in {0, 1, 2, 3, 4}$ の組であって、 $b_{1} + b_{2} + . . . b_{7} + k$ が偶数になるものは何通りあるか。

これは数え上げの問題ですが、同じように考えます。
$b_{1}$ の偶奇の場合の対称性により、 $640$ 組のうち丁度半分が条件を満たします。
$320$ が答えです。

1000個のサイコロ

$1000$ 個の $6$ 面サイコロ $a_{1} . . ., a_{1000}$ を振る時、出た目の和が $2$ の倍数になる確率を求めよ。

$a_{1}$ を見ても $a_{1000}$ を見てもいいですね。
いずれにしろ、答えは $\frac{1}{2}$ になります。

1001個のサイコロ

$1$ 個の $6$ 面サイコロ $a_{1}$ と $1000$ 個の $7$ 面サイコロ $b_{1} . . ., b_{1000}$ を振る時、出た目の和が $2$ の倍数になる確率を求めよ。

$a_{1}$ が一個あるだけで、他が何であろうと、対称性から答えは $\frac{1}{2}$ になります。

対称性を勝手に作ろう

5個の変なサイコロ

$5$ 個の $7$ 面サイコロ $a_{1} . . ., a_{5}$ を振る時、出た目の和が $2$ の倍数になる確率を求めよ。

$6$ 面サイコロが無くなっちゃいました。対称性が使えません。困った。
ここで $6$ 面サイコロを勝手に作り出します。でも、どうやって？
$7$ 面サイコロの出目を二つの集合に分けます。
$A = {1, 2, 3, 4, 5, 6}$ $B = {7}$
ここで出た目の組( $a_{1}, a_{2}, a_{3}, a_{4}, a_{5}$ )をその目が属する集合で変換してみましょう。
$(2, 3, 4, 5, 7)$ → $(A, A, A, A, B)$
$(2, 7, 4, 6, 6)$ → $(A, B, A, A, A)$
$(7, 7, 7, 7, 7)$ → $(B, B, B, B, B)$
ここで、変換後の列が $(A, A, B, A, A)$ だった時、出た目の和が $2$ の倍数になる条件付き確率を求めてみましょう。
$A$ は実質 $6$ 面サイコロです。対称性が使えます！
何とこれは、 $\frac{1}{2}$ ではありませんか！
他の組についても $A$ が一つ以上含まれていれば、 $\frac{1}{2}$ になります。
$\frac{1}{2}$ にならないのは $(B, B, B, B, B)$ の時のみで、この場合は自明に $0$ です。(誤植を修正しました)
これを基に全体の確率を簡単に計算できます。
$\frac{7^{5} - 1}{7^{5}} \times \frac{1}{2} + \frac{1}{7^{5}} \times 0 = \frac{1}{2} - \frac{1}{2 \cdot 7^{5}}$

OMC148-D (300点)

　 $13$ 以下の素数の組 $(a_{1}, a_{2}, . . . a_{2022})$ であって，　 $\prod_{k = 1}^{2022} a_{k} \equiv 1 (m o d 3)$ をみたすものは $N$ 個存在するので， $N$ を素数 $2017$ で割った余りを求めてください．

$3$ は $a$ に入りません。無視します。
$3$ 以外の $13$ 以下の素数を二つの集合に分けます。
$A = {2, 5, 7, 13}$ $B = {11}$
$A$ には $\mod 3$ で $1$ になる素数が $2$ 個、 $2$ になる素数が $2$ 個含まれています。先ほどと同じように考えると対称性から $A$ が一つでも含まれた組は丁度半分が条件を満たします。全部 $B$ の場合は条件を満たします。
$(5^{2022} - 1) \times \frac{1}{2} + 1 = \frac{5^{2022} + 1}{2}$ ( $2017$ で割るパートは割愛)

応用

さいころの目の積が平方数になる確率

　 $6$ 面サイコロを $n$ 個振ったとき, 出目の積が平方数になる確率 $p_{n}$ を求めてください.

これは有名問題で、湧水さんの記事でも取り上げられています。
今回は漸化式も関数も使わずに解いてみましょう。
$6$ 面サイコロの出目を二つの集合に分けます。
$A = {1, 2, 3, 6}$ $B = {4, 5}$
$A$ に含まれる出目は $2, 3$ の素因数の数の偶奇にのみ干渉します。
$B$ に含まれる出目は $5$ の素因数の数の偶奇にのみ干渉します。
ここで、先ほどと同様に変換後の組について出目の積が平方数になる条件付き確率を求めてみましょう。
$A$ には対称性があり、 $A$ が一つでも含まれれば、 $2, 3$ の素因数の数がどちらも偶数になる確率は $\frac{1}{4}$ になります。
$B$ にも対称性があり、Bが一つでも含まれれば、 $5$ の素因数の数が偶数になる確率は $\frac{1}{2}$ になります。
そしてこの二つはちゃんと独立です。(重要)
$A, B$ がどちらも含まれている場合は確率 $\frac{1}{8}$
$A$ のみ含まれている場合 $\frac{1}{4}$
$B$ のみ含まれている場合 $\frac{1}{2}$
よって求めるべき確率は
$(1 - (\frac{4}{6})^{n} - (\frac{2}{6})^{n}) \times \frac{1}{8} + (\frac{4}{6})^{n} \times \frac{1}{4} + (\frac{2}{6})^{n} \times \frac{1}{2} = \frac{1}{8} + \frac{1}{8} (\frac{2}{3})^{n} + \frac{3}{8} (\frac{1}{3})^{n}$