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

(2015年11月に行われた特色入試の問題です。2016年に行われた特色入試の問題はこちら

問題編

問題

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に関する必要十分条件を求めよ。

【広告】
本書は「超」公式集です。最強の公式だけを集めました。
『数学I・A』はたった14個、『数学II・B』はたった11個の少数精鋭です。
なぜ、こんなに少ないのか?
それは、一つ一つが基本的なのに、あなたの数学を変えてしまうくらいに深いからです。
お読みいただければわかるのですが、基本的とは簡単なことではありません。しかし、この、I・A、II・Bあわせて(たった)25個の公式をマスターした後に、あなたの目の前には新しい地平が広がっているはずです。これらの公式を九九のように覚えてしまうことによって、あなたの思考は気持ちが良いほどに身軽に、そして自由になるのです。 さあ、ぜひ本書を読んで、どんどんクリアーになっていく新しい世界をお楽しみください。
著者:松野陽一郎
出版社:旺文社
発売日:2021-09-16
ページ数:224 ページ
値段:¥1,430
(2021年09月 時点の情報です)

考え方

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

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

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

1 2