47

OMCの技 simasima special 解説 (前編)

5289
0

はじめに

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

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

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

対称性を見つけよう

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

丁半

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

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

a1a2確率
奇数奇数偶数12×12=14
奇数偶数奇数12×12=14
偶数奇数奇数12×12=14
偶数偶数偶数12×12=14

和が奇数になる確率は 14+14=12 です。
次の問題も解いてみましょう。

変な丁半

6面サイコロa17面サイコロa2を振る時、出た目の和が奇数になる確率を求めよ。

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

a1a2確率
奇数奇数偶数12×47=27
奇数偶数奇数12×37=314
偶数奇数奇数12×47=27
偶数偶数偶数12×37=314

和が奇数になる確率は 27+314=12 です。
これを見て何か気付かないでしょうか。
上二行と下二行を比べてみましょう。
a2 が奇数の時、a1が偶数であれば和の条件を満たします。逆にa1が奇数であれば和の条件を満たしません。
a2 が偶数の時、a1が奇数であれば和の条件を満たします。逆にa1が偶数であれば和の条件を満たしません。
a1 が偶数か奇数かは12で等確率なので、a2がどんな確率であれ、対称性から結局和が奇数になる確率は12になるのです。

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

a2a1確率
奇数奇数偶数47×12=27
奇数偶数奇数47×12=27
偶数奇数奇数37×12=314
偶数偶数偶数37×12=314

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

結局6面サイコロa1が存在することで、他のサイコロに関係なく確率が12になってしまうのです。

補足

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

3の倍数

6面サイコロa17面サイコロa2を振る時、出た目の和が3の倍数になる確率を求めよ。

対称性から答えは13になります。
a2を先に振ると考えても、結局a1の出目で決まるので13になりますね。

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

数列b1,b2,...b7(bi{0,1})とk{0,1,2,3,4}の組であって、b1+b2+...b7+kが偶数になるものは何通りあるか。

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

1000個のサイコロ

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

a1を見てもa1000を見てもいいですね。
いずれにしろ、答えは12になります。

1001個のサイコロ

1個の6面サイコロa11000個の7面サイコロb1...,b1000を振る時、出た目の和が2の倍数になる確率を求めよ。

a1が一個あるだけで、他が何であろうと、対称性から答えは12になります。

対称性を勝手に作ろう

5個の変なサイコロ

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

6面サイコロが無くなっちゃいました。対称性が使えません。困った。
ここで6面サイコロを勝手に作り出します。でも、どうやって?
7面サイコロの出目を二つの集合に分けます。
A={1,2,3,4,5,6} B={7}
ここで出た目の組(a1,a2,a3,a4,a5)をその目が属する集合で変換してみましょう。
(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面サイコロです。対称性が使えます!
何とこれは、12ではありませんか!
他の組についてもAが一つ以上含まれていれば、12になります。
12にならないのは(B,B,B,B,B)の時のみで、この場合は自明に 0 です。(誤植を修正しました)
これを基に全体の確率を簡単に計算できます。
75175×12+175×0=121275

OMC148-D (300点)

 13 以下の素数の組 (a1,a2,...a2022)であって, k=12022ak1(mod3)をみたすものは N 個存在するので,N を素数 2017 で割った余りを求めてください.

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

応用

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

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

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

To Be Continued

まだ、この技の半分未満くらいしか見せられていませんが、長すぎて疲れてしまったので後編に続きます。
後編では、値の打ち消しや高度なグループ分けなどを取り扱い、OMC024-Dがいい感じに倒せ次第書き始める予定です。

投稿日:202379
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

simasima
simasima
195
31801
OMC橙(2499/5位)OMC030,034,036,038優勝/OMC015,OMC032単独writer/AtCoder橙

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 対称性を見つけよう
  3. 対称性を勝手に作ろう
  4. 応用
  5. To Be Continued