読者です 読者をやめる 読者になる 読者になる

shaitan's blog

長文書きたいときに使う.

京大特色入試と聞いて、を読んで

nloglogn.hatenablog.com


いつもの別解です。
なんかちゃんとした答案を書けなくなってるので概略のみ。コインの番号とかいい感じになってると思って下さい。


【問3】
操作の順序は関係なく、同一の操作の回数も偶奇しか関係ない。n種の操作のそれぞれを高々一回行うかどうかの2^n通りの一連の操作だけ考えればよい。
初期状態は2^n通りなので、「終了させられない初期状態が存在する」と「同一の初期状態を終了させる相異なる一連の操作A,Bが存在する」が同値。
さらに「その前後で状態が変化しないような一連の操作C(何の操作もしないものを除く)が存在する」とも同値(AとBのXORがC)。
Cは隣接した二枚のコインを裏返す回数の偶奇が等しいことが必要なので、i番目のコインからi+k-1番目のコインをひっくり返す操作(M[i]とする)が含まれるとすれば、M[i+k],M[i+2k],...,M[i+(n/m-1)k]も含まれる(mはkとnの最大公約数)。
これらn/m回の一連の操作を行うことをN[i]と書くと、CはN[i]を組み合わせた一連の操作である。
m>2のとき、N[0]とN[1]は相異なり、いずれもすべてのコインをk/m回ずつひっくり返す操作なのでAとBの条件を満たす。
m=1のとき、N[i]はどれも同じ(以下、単にNと書く)なので、Cが存在するとしたらNである。
Nはすべてのコインをk回ずつひっくり返す操作なので、kが偶数ならばこれはCの条件を満たし、kが奇数ならば満たさない。

以上をまとめて、求める必要十分条件はkが2nと互いに素であること。

【問2】
ある一連の操作とN[0]とN[1]のXORをとったものは異なる一連の操作でありいずれも結果は同じ。
N[1]とN[2]の場合、N[2]とN[0]の場合も同様なので、終了させられる初期状態は高々2^6/4=16通り。
以下、終了させられる初期状態を列挙する。
すべて表の状態およびすべて裏の状態(2通り)
すべて表の状態からM[i]を行ったもの(6通り)
すべて表の状態からM[i]とM[i+1]を行ったもの(3通り)
すべて表の状態からM[i]とM[i+2]を行ったもの(3通り)
すべて表の状態からM[i],M[i+1],M[i+2]を行ったもの(2通り)
これらは相異なり、図2はこれらのいずれとも異なるので終了させられない。

【問1】
7と3は互いに素なので終了できる。
(a)必要な操作の最小回数は高々7回。
(b)1回の操作により、隣り合うコインの表裏が異なるようなコインの隙間は高々2だけ増減するが、
初期状態はそのような隙間が6箇所あるので3回以上の操作が必要。
(c)リンク先と同様の議論により偶数回である。
(d)6回で終了できるのは連続する3枚のコインのみが表の状態であり、所与の初期状態とは異なる。
以上より4回。


問2の別アイデアはこちら。
shaitan.hatenablog.com