京都大学 理学部特色入試 2016年度 第3問 解説

問題編

問題

nを3以上の整数とし、kを自然数とする。表裏の区別のつくn枚のコインを用いて1人で以下のゲームを行う。

  • まず、ゲームの初期状態として、n枚のコインを円周上に等間隔に並べる。各コインは表または裏である。
  • 以下の操作を何回か繰り返す。
    (操作)並べたコインの中から連続するk枚を選び、選んだコインをすべてひっくり返す。
  • この操作を何回か行った結果、すべてのコインを表にすることができれば、ゲームは終了する。

ゲームの初期状態の例(黒丸:コインの表、白丸:コインの裏)

kyoto-u-t-2016-3-01
kyoto-u-t-2016-3-02

以下の設問に答えよ。

(1) $n=7、k=3$ とする。初期状態が図1のとき、このゲームを終了させることができることを示せ。また、すべてのコインを表にするまでに必要な操作の最小回数を求めよ。

(2) $n=6、k=3$ とする。初期状態が図2のとき、このゲームを終了させることはできないことを示せ。

(3) どのような初期状態であっても必ずこのゲームを終了させることができるための、n、kに関する必要十分条件を求めよ。

【広告】

考え方

問1は、できるかどうかを考えるだけなら簡単ですね。試行錯誤すれば、何とか答えにたどり着けるはずです。問題はそれが最小であることを示すことです。操作の制限から、「それより少ない回数ではできない」ということを示していきます。

問2は、「終了できないこと」なのでよりハードルが高いです。これも、操作の制限から「できない」ことを示していきます。問3はそれの一般化なので、問2をヒントに解いていきます。

よく考えると、「連続するk個」を2回ひっくり返すと元に戻るので、同じk個のコインを2回以上ひっくり返すことに意味はありません。つまり、1回ひっくり返すかそのままかしかありません。とすると、実は操作は最大でn回しかなく、考えるべき条件はかなり限られます。