ひたすら受験問題を解説していくブログ
京都大学理学部2016年特色入試数学第?問
kyodai_2016_t_math_seisu.jpg
http://www.kyoto-np.co.jp/education/article/20151128000119より画像引用

解説


難しいです。そこまでではないですが東大の例のグラフの論証を思い出します。しかしながら,あのグラフの論証もそうですが,裏表だの返せる数が一定だのの時点で,大抵はその数で割れるか否かや共通の約数を持つか否かで考えていけばいいと推測できます。とりあえず,問1は簡単め,問2はまともに解けなくとも試行錯誤でどうにでも,問3は一気にレベルが変わって同値な条件を見つけたりしつつ整数の手法をうまく使わないと解けない難問で,これが解けたら一般入試余裕でしょう。

全体の設問構成は(1)偶奇性,(2)約数を持つ場合かつ操作の可換性や状態の重なり,(3) (1)及び(2)を元に推測して必要十分性を示す。という感じです。
(3)の必要性に関してももう少しややこしくなくユークリッド互除法な感じで行けないものかと思います。

(1)
裏表ということなので,偶奇性に着目します。まあ,その前に適当にいじってみて全部表にする方法を考えると(裏が黒丸,表が白丸とします),
kyodai_2016_t_math_aseisu_1.png

とりあえず4回で行けました。偶奇に着目した場合,k=3での操作は奇数個しか裏を変えられません(○○○に適用なら3つ,●○○なら1つの増減です)。したがって,もともと4つの裏を表にするためには偶数回の操作が必須になります。4が最小でないとすると2が最小になりますが,初めの段階で裏の減少が1の操作しかできず,できる図形も3減少の操作ができるところはないため,ありえません。したがって,4回が最小です。

(2)
コインの裏表する操作に関しては操作の順序は関係ないため,高々2の6乗とおりしか考える必要はありません。また,6は3で割り切れるので,すべて裏表が逆のものは同値です。すると,数え上げても行ける感じになります(同型出現を考慮して図を描けば61回も数えなくて終わります)。
それでは芸がないので,まずは以下のように変換します。
kyodai_2016_t_math_aseisu_2.png

これに何の意味があるかというと,もしこれを全部表にできるならば,一枚を裏返せることになり,任意のコインを裏返せるため任意の配置でクリア可能です。言い換えるならば,ある状態からすべての状態にすることが可能となります。

ここで取りうる状態が2の6乗であり,操作の数が2の6乗であることに着目すれば,同じ状態を示す異なる操作があればとりえない状況が存在することがわかります。3組の2回操作で全部ひっくり返すことが可能であることは自明なので,異なる操作で同じ状態になってしまいます。
したがって,ある状態からすべての状態にすることは不可能であり,コイン1枚だけを裏返す操作は存在しません。当然,同値である元の状態をすべて表にすることもできません。

(3)
試行錯誤の結果(最初は割り切れるで証明しようとした結果,互いに素が条件だと気づきました),nとkは互いに素かつkは奇数が条件だとわかります。

(i)必要性
”終了可能⇒nとkは互いに素かつkは奇数”の待遇をとると,”nとkは互いに素ではない,またはkが偶数⇒終了不可能”となります。

まずは簡単なkが偶数の時,(1)と同様の考え方で,k=が偶数ならば,行える裏の増減が偶数のみになります。したがって,奇数個が裏の場合には詰みます。

次に,kが奇数でnとkに共通の約数q(最大公約数)を持つ場合を考えます(n=kp-mq,k=rq,mとrは互いに素とします)。できるだけ裏を増やすように全部表から順繰りに裏返していきます(面倒なのでk=3っぽい感じで描いています)。

kyodai_2016_t_math_aseisu_3.png

一周すると開始地点からmqだけ表になります。これを黒の左端からまた初めて,同様のことを計r回繰り返せば,mrq個のみ表という状況が作れます(kが奇数⇒rが奇数なのでr回やると表がmrq個連続になります。左端は一番初めの操作開始点です)。ここまでに費やした操作の回数は1周がp回なので,rp回の操作でこのようになります。これにm回の操作を左端からしてやれば裏のみになりますが,一週目の開始点と左端が一致しているので,このm回の操作は初めにした操作のキャンセルになります(同じ位置に2回操作をすれば元に戻るのでなかったことと同じです)。したがって,全部裏はrp-m回の操作で達成可能です。

n=kp-mq=rpq-mq=(rp-m)q>rp-m
∵q≧2,かつ,裏があるなら操作がすべて打ち消されているわけではないのでrp-m≠0

したがって,少なくとも一か所は操作が行われていない個所があり,その箇所をずらして同様の操作をやれば異なる操作になりますが,ともに得られる状態はすべて裏になるため,(2)と同様に表せない状態が存在します。

(ii)十分性
nとkは互いに素なのでn=kp-m(mとkは互いに素とします)とおけます。(i)と同様の操作すると一周で連続したm個だけ表の状態が得られます。
mx+ky=1
となるものがkとmが互いに素なので,ユークリッド互除法から整数x及びyが定まるので,一個だけ表もしくは裏のものが作れます。1枚だけ裏の方は1枚のコインのみを裏返しているので,すべての状態を作れることと同値です。
一方,1枚だけ表のものは1つとなりで同じ操作をすれば2枚連続で裏のものができます。こんな感じでk+1回繰り返せば,kは奇数なのでk+1枚連続裏のものができます。このk枚を裏返してやれば1枚だけ裏のものが作れます。
スポンサーサイト

テーマ:大学受験 - ジャンル:学校・教育

コメント
コメント
コメントの投稿
URL:
本文:
パスワード:
非公開コメント: 管理者にだけ表示を許可する
 
トラックバック
トラックバック URL
http://jukenkaisetsu.blog.fc2.com/tb.php/593-2df68244
この記事にトラックバックする(FC2ブログユーザー)
トラックバック