OMCの技 simasima special 解説 (後編)
はじめに
この記事は後編です。先に 前編 を読むことをオススメします。
対称性で消して周期を見つける
バイナリ列$a_1,a_2,...a_{100}$($a_i\in\{0,1\}$)であって、総和が$3$の倍数になるものはいくつ存在しますか？
元が$2$つしかないのでグループ分けで解くのは難しそうです。別のアプローチをしてみましょう。
数列$a_1,a_2,...a_{n}$($a_i\in\{0,1\}$)であって、総和が$3$の倍数になるものの総数を$x_n$、総和が$3$で割って$1$余るものの総数を$y_n$、$2$余るものの総数を$z_n$とします。試しに、$x_n,y_n,z_n$の値を計算してみましょう。
$x_n,y_n,z_n$の値は$x_{n-1},y_{n-1},z_{n-1}$の値から求められます。
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|---|---|
| $x_n$ | $1$ | $1$ | $1$ | $2$ | $5$ | $11$ | $22$ | $43$ |
| $y_n$ | $0$ | $1$ | $2$ | $3$ | $5$ | $10$ | $21$ | $43$ |
| $z_n$ | $0$ | $0$ | $1$ | $3$ | $6$ | $11$ | $21$ | $42$ |
$n$が同じ時の$x_n,y_n,z_n$の差は$1$未満になっていそうですね。この差を詳しく見てみたいですね。
ここで、前回の内容の確認も兼ねて、次の問題を考えてみましょう。
数列$a_0,a_1,a_2,...a_{n}$($a_0\in\{0,1,2\}$,$a_i\in\{0,1\}(0< i))$)であって、総和が$3$の倍数になるものはいくつ存在しますか？
これは前回もやりました。この問題の場合のそれぞれの総数$x'_n,y'_n,z'_n$を考えてみましょう。
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|---|---|
| $x'_n$ | $1$ | $2$ | $4$ | $8$ | $16$ | $32$ | $64$ | $128$ |
| $y'_n$ | $1$ | $2$ | $4$ | $8$ | $16$ | $32$ | $64$ | $128$ |
| $z'_n$ | $1$ | $2$ | $4$ | $8$ | $16$ | $32$ | $64$ | $128$ |
一度$x_n=y_n=z_n$になるとずっと$x_n=y_n=z_n$になります。当たり前ですね。
ここで、元の問題について前回と同様に対称性を無理やり作り出す事を考えます。
$n=2$の場合、$x_2=1,y_2=2,z_2=1$となっていますが、これを$Ax_2=1,Ay_2=1,Az_2=1$と$Bx_2=0,By_2=1,Bz_2=0$の二つに分けます。どうなるか実際に計算してみましょう。$x_n,y_n,z_n$の計算と同じように前の値から計算していきます。
| $n$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|
| $Ax_n$ | $1$ | $2$ | $4$ | $8$ | $16$ | $32$ |
| $Ay_n$ | $1$ | $2$ | $4$ | $8$ | $16$ | $32$ |
| $Az_n$ | $1$ | $2$ | $4$ | $8$ | $16$ | $32$ |
| $n$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|
| $Bx_n$ | $0$ | $0$ | $1$ | $3$ | $6$ | $11$ |
| $By_n$ | $1$ | $1$ | $1$ | $2$ | $5$ | $11$ |
| $Bz_n$ | $0$ | $1$ | $2$ | $3$ | $5$ | $10$ |
この時、線形性から$Ax_n+Bx_n=x_n,Ay_n+By_n=y_n,Az_n+Bz_n=z_n$になることが分かります。
$Ax_n=Ay_n=Az_n$は常に成り立つので、$x_n,y_n,z_n$間の差を考えるには、$Bx_n,By_n,Bz_n$だけ考えれば良いです。
ここで、$n=4$の場合を見ると、$Bx_4=1,By_4=1,Bz_2=2$となっていますが、これはさらに$ABx_4=1,ABy_4=1,ABz_4=1$と$BBx_4=0,BBy_4=0,BBz_4=1$の二つに分けられます。$x_n,y_n,z_n$間の差を考えるには、$BBx_n,BBy_n,BBz_n$だけ考えれば良いです。
まとめると、$x_n,y_n,z_n$の値から途中で同じ値を引いても$x_n,y_n,z_n$の差には支障がないという事ですね。
これを踏まえて、$x_n,y_n,z_n$を求めてみましょう。
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|---|---|
| $x_n$(差分) | $1$ | $1$ | $1\rightarrow 0$ | $0$ | $1\rightarrow 0$ | $1$ | $2\rightarrow 1$ | $1$ |
| $y_n$(差分) | $0$ | $1$ | $2\rightarrow 1$ | $1$ | $1\rightarrow 0$ | $0$ | $1\rightarrow 0$ | $1$ |
| $z_n$(差分) | $0$ | $0$ | $1\rightarrow 0$ | $1$ | $2\rightarrow 1$ | $1$ | $1\rightarrow 0$ | $0$ |
$n=0$の場合と$n=6$の場合で値が一致したので、この数列の周期は$6$である事が分かりました。
よって、$n=100$ の場合の差分は$x_{100}=0,y_{100}=0,z_{100}=1$と分かります。ところで、バイナリ列全体の数を考えれば、$x_{100}+y_{100}+z_{100}=2^{100}$と簡単に分かります。
あとは和差算のようなことをやれば、$x_{100}$の値が分かります。
$$x_{100}=\frac{2^{100}-0-0-1}{3}+0=\frac{2^{100}-1}{3}$$
答えを求めることが出来ました！
ちなみに、差分計算について負の数を用いてこのような解釈もできます。
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|---|---|
| $x_n$(差分) | $1$ | $1\rightarrow 0$ | $-1\rightarrow 0$ | $0\rightarrow -1$ | $0\rightarrow 0$ | $1\rightarrow 0$ | $0\rightarrow 1$ | $1\rightarrow 0$ |
| $y_n$(差分) | $0$ | $1\rightarrow 0$ | $0\rightarrow 1$ | $1\rightarrow 0$ | $0\rightarrow 0$ | $0\rightarrow -1$ | $-1\rightarrow 0$ | $1\rightarrow 0$ |
| $z_n$(差分) | $0$ | $0\rightarrow -1$ | $-1\rightarrow 0$ | $1\rightarrow 0$ | $-1\rightarrow 1$ | $1\rightarrow 0$ | $-1\rightarrow 0$ | $0\rightarrow -1$ |
こう見ると、$n=1$の時点で既に周期$6$であることが見えますね！
実践しよう
前編では漸化式の遷移に対称性を見出すだけでしたが、今回からは漸化式の値にも対称性を見つけることが出来るようになりました。これで似たような設定の問題はほとんど倒すことが出来ます。
早速見てみましょう。
バイナリ列$a_1,a_2,...a_{39305}$($a_i\in\{0,1\}$)であって、総和が$4$の倍数になるものはいくつ存在しますか？
これも先ほどと同じように差分を計算して考えてみましょう。
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 総和$0(mod4)$ | $1$ | $1$ | $1$ | $1\rightarrow 0$ | $0$ | $1\rightarrow 0$ | $4$ | $12\rightarrow 8$ | $16$ | $24\rightarrow 16$ | $32$ |
| 総和$1(mod4)$ | $0$ | $1$ | $2$ | $3\rightarrow 2$ | $2$ | $3\rightarrow 0$ | $0$ | $4\rightarrow 0$ | $8$ | $24\rightarrow 16$ | $16$ |
| 総和$2(mod4)$ | $0$ | $0$ | $1$ | $3\rightarrow 2$ | $4$ | $3\rightarrow 4$ | $4$ | $4\rightarrow 0$ | $0$ | $8\rightarrow 0$ | $0$ |
| 総和$3(mod4)$ | $0$ | $0$ | $0$ | $1\rightarrow 0$ | $2$ | $1\rightarrow 4$ | $8$ | $12\rightarrow 8$ | $8$ | $8\rightarrow 0$ | $16$ |
$n=1$の値と$n=3$の値を比べてみましょう。値がずれながら$2$倍になっています。$n=5,7,9$の場合も値がずれながら$2$倍になっています。このことから$n=39305$の時の差分の値は、$2^{19652},2^{19652},0,0$となります。
また、総和が$2^{39305}$であることから、答えの値はこのように求まります。
$$\frac{2^{39305}-2^{19652}-2^{19652}-0-0}{4}+2^{19652}=2^{39303}+2^{19651}$$
$\{1,2,3,...,2000\}$の部分集合であって要素の総和が$5$の倍数であるものはいくつあるか。
3Blue1Brownの動画内では多項式が使われていますが、今回は使わずに解いていきます。
今回は毎回同じ遷移をしているわけではないことに注意してください。
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|---|
| 総和$0(mod5)$ | $1$ | $1$ | $1\rightarrow 0$ | $0$ | $0\rightarrow 1$ | $2$ | $2$ |
| 総和$1(mod5)$ | $0$ | $1$ | $1\rightarrow 0$ | $0$ | $-1\rightarrow 0$ | $0$ | $2$ |
| 総和$2(mod5)$ | $0$ | $0$ | $1\rightarrow 0$ | $-1$ | $-1\rightarrow 0$ | $0$ | $0$ |
| 総和$3(mod5)$ | $0$ | $0$ | $1\rightarrow 0$ | $0$ | $-1\rightarrow 0$ | $0$ | $0$ |
| 総和$4(mod5)$ | $0$ | $0$ | $0\rightarrow -1$ | $-1$ | $-1\rightarrow 0$ | $0$ | $0$ |
周期が$5$で$2$倍になっているのがわかります。(ちなみに$5$だけではなく一般の奇素数$p$についていちいち遷移を考えなくても計算できるのですが、それはまた別の機会に)
$n=2000$ の時は$2^{400},0,0,0,0$ となり、その総和は$2^{2000}$なので答えの値はこのように求まります。
$$\frac{2^{2000}-2^{400}}{5}+2^{400}=\frac{2^{2000}+2^{402}}{5}$$
応用編
ここからはsimasima specialを応用して解けるOMCの問題を$2$問紹介します。どちらも最も上のクラスのコンテストで出題された超難問です。
なお、改題によって期待値の線形性を用いる部分が省かれています。
正二十面体の頂点のうち、一つを$R$とする。点$P$は最初$R$にある。点$P$が「辺で繋がった頂点$5$つの中から等確率に$1$つを選び移動する」という移動を$12$回行ったとき、点$R$と点$P$との距離の期待値を求めよ。(ここでは点$P$と点$R$との距離を、$P$から$R$まで辺に沿って辿るときに経由する辺の個数の最小値とする。一致する場合は$0$)
$n$回移動した後、距離が$0,1,2,3$になる確率を、$Z_n,S_n,D_n,T_n$と置きます。
この時、求めるべき値は$S_{12}+2D_{12}+3T_{12}$なので、高々$4\times12=48$回計算すれば求まるでしょう。しかし、これでは多くの時間がかかってしまい他の問題を解く時間が無くなってしまいます。試しに$Z_n,S_n,D_n,T_n$を計算してみましょう。
| $n$ | $0$ | $1$ | $2$ |
|---|---|---|---|
| $Z_n$ | $1$ | $0$ | $\frac{1}{5}$ |
| $S_n$ | $0$ | $1$ | $\frac{2}{5}$ |
| $D_n$ | $0$ | $0$ | $\frac{2}{5}$ |
| $T_n$ | $0$ | $0$ | $0$ |
求めたいのは期待値です。ここで、正二十面体の上下の対称性を考えると、$S_n=D_n,Z_n=T_n$なら、その後もずっと$S_n=D_n,Z_n=T_n$となり、期待値は$\frac{3}{2}$で不変になることが分かります。(下の図は例)
| $n$ | $0$ | $1$ | $2$ |
|---|---|---|---|
| $Z'_n$ | $0$ | $\frac{1}{5}$ | $\frac{4}{25}$ |
| $S'_n$ | $1$ | $\frac{4}{5}$ | $\frac{21}{25}$ |
| $D'_n$ | $1$ | $\frac{4}{5}$ | $\frac{21}{25}$ |
| $T'_n$ | $0$ | $\frac{1}{5}$ | $\frac{4}{25}$ |
なので、$S_n$と$D_n$は打ち消して最後に考えることが出来ます。
$Z_n,S_n,D_n,T_n$の差分は次のようになります
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|---|
| $Z_n$(差分) | $1$ | $0$ | $\frac{1}{5}$ | $0$ | $\frac{1}{25}$ |
| $S_n$(差分) | $0$ | $1$ | $\frac{2}{5}\rightarrow 0$ | $\frac{1}{5}$ | $\frac{2}{25}\rightarrow 0$ |
| $D_n$(差分) | $0$ | $0$ | $\frac{2}{5}\rightarrow 0$ | $0$ | $\frac{2}{25}\rightarrow 0$ |
| $T_n$(差分) | $0$ | $0$ | $0$ | $0$ | $0$ |
周期$2$でどんどん$\frac{1}{5}$倍されていきます。簡単ですね。
$n=12$の時の差分の値は$\frac{1}{5^6},0,0,0$になります。$\frac{1}{5^6}$の場合期待値は$0$、それ以外の$1-\frac{1}{5^6}$の場合は$\frac{3}{2}$なので、答えは$\frac{3}{2}(1-\frac{1}{5^6})$になります。
とてもスマートに解くことが出来ました。
$1$から$6$までの整数の書かれたボールが$6$個ずつ計$36$個のボールが入った箱の中から同時にランダムに$6$つのボールを取り出し、書かれている数の総和を$7$で割った値をスコアとする。同じ数が書かれたボールも区別する時取り出し方は${}_{36} \mathrm{ C }_6$通りある。そのスコアの総和を求めよ。
今回のラスボスです。Difficulty(難易度)は赤と最大で、正解者は僅かに$4$人という正真正銘の超難問です。公式の解説ではFPSを用いていますが、simasima specialを使っても倒せます。
まず、$36$個のボールを$\{1,2,3,4,5,6\},\{1,2,3,4,5,6\},...,\{1,2,3,4,5,6\}$という風に$6$つの集合$S_1,S_2,...S_6$に分けます。
それぞれの集合から選ばれるボールの個数を$a_1,a_2,...,a_6$とします。$a_1,a_2,...,a_6$を固定した時のスコアの総和を考えてみましょう。$a_x=0,1,2,3,4,5,6$の時、集合$S_x$からボールを選ぶ方法は${}_6 \mathrm{ C }_{a_x}$通りありますが、ボールに書かれた数の総和をそれぞれについてまとめると次のようになります。
| $a_x$ | $0,6$ | $1,5$ | $2,4$ | $3$ |
|---|---|---|---|---|
| $0(mod7)$ | $1$ | $0$ | $3$ | $2$ |
| $1(mod7)$ | $0$ | $1$ | $2$ | $3$ |
| $2(mod7)$ | $0$ | $1$ | $2$ | $3$ |
| $3(mod7)$ | $0$ | $1$ | $2$ | $3$ |
| $4(mod7)$ | $0$ | $1$ | $2$ | $3$ |
| $5(mod7)$ | $0$ | $1$ | $2$ | $3$ |
| $6(mod7)$ | $0$ | $1$ | $2$ | $3$ |
ここにsimasima specialを適用すると次のように綺麗になります。
| $a_x$ | $x$ |
|---|---|
| $0(mod7)$(差分) | $(-1)^x$ |
| $1(mod7)$(差分) | $0$ |
| $2(mod7)$(差分) | $0$ |
| $3(mod7)$(差分) | $0$ |
| $4(mod7)$(差分) | $0$ |
| $5(mod7)$(差分) | $0$ |
| $6(mod7)$(差分) | $0$ |
(これは偶然では無く、任意の素数$p$について成り立つ事が組合せ的な解釈に基づいて証明できますが、今回は愚直にやっても解けるので割愛します。)
$a_1+a_2+a_3+a_4+a_5+a_6=6$であることから、$(-1)^6=1$なので、差分の値は条件を満たす全ての組$(a_1,a_2,a_3,a_4,a_5,a_6)$について$1,0,0,0,0,0,0$になることが分かります。$a_1+a_2+a_3+a_4+a_5+a_6=6$を満たす$(a_1,a_2,a_3,a_4,a_5,a_6)$は${}_6 \mathrm{ H }_6=462$通りあるので、全体について差分の値は$462,0,0,0,0,0,0$になります。
$36$個のボールから$6$つ選ぶ方法は${}_{36} \mathrm{ C }_6$通りです。そのうち、$462$通りではスコア$0$、その他${}_{36} \mathrm{ C }_6-462$通りには、スコア$0,1,2,3,4,5,6$が同じ数だけ含まれています。
よって答えは次のようになります。
$$\frac{0+1+2+3+4+5+6}{7}\times({}_{36} \mathrm{ C }_6-462)=5841990$$
おわり らない 次回予告
これでOMCにあるsimasima specialが使えそうな問題を全て倒せる、と言いたいところですが、1問だけ残っています。OMC024-Dです。この問題はまだ筆者がいい感じに倒せていません。正確に言うとOMC024-D自体は倒せているのですが、変数を増やすと使えないAd-hocなものになっているので微妙です。変数が増えた設定の問題が解け次第新たに記事を書こうと思います。また、simasima specialを一般化して行列の対角化に持って行く話もあるのですが、筆者自身の線形代数の習熟度が足りないので半年くらい寝かせようと思います。それではまた次回。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
