プロフィール

mathnegi

Author:mathnegi
ゆる~い人間です(*´ヮ`*)
宮城県在住~

カレンダー

07 | 2017/08 | 09
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

最新記事

全記事リスト

全ての記事を表示する

最新コメント

月別アーカイブ

カテゴリ

閲覧者数

検索フォーム

RSSリンクの表示

リンク

ブロとも申請フォーム

この人とブロともになる

QRコード

QR

電卓だよん♪

電 卓

お問い合わせはこちらまで~♪

名前:
メール:
件名:
本文:

受験ブログ 大学受験(指導・勉強法)へ

スポンサーサイト

--.--.-- --:--|スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2016年京大特色入試第3問

2017.01.13 20:08|大学入試問題
どもども。

昨年の京大特色入試の第3問を眺めてみます~ ぺんぎんmini


問題: A,B の2人が次のゲームを行う。初期状態として,台の上に n 個の石が置いてある。最初に A,次に B の順で交互に,台から1個以上の石を取り除いていく。ただし一度に取り除く個数は自然数の2乗でなければならない。台の上に石がない状態にした方を勝者として,そこでゲームを終了する。
 このゲームが先手必勝であるとは,A が自分の番で取り除く石の個数を適切に選択していけば,B がいかなる選択を行っても,必ず A が勝利できることとする。同様に,このゲームが後手必勝であるとは,B が自分の番で適切に選択を行っていけば,A がいかなる選択を行っても必ず B が勝利できることとする。
 例えば, n=10 のとき,最初に A が取り除ける石の個数は 1,4,9 のいずれかである。
A が1個取り除くならば,残りの石の個数は9 となる。この状態において B が取り除ける石の個数は1,4,9 のいずれかである。 B が9個取り除くという選択を行うと B が勝利する。
A が9個取り除くならば,残りの石の個数は1となる。次に B が1個取り除いて B が勝利する。
A が4個取り除くならば,残りの石の個数は6 となる。この状態において B が取り除ける石の個数は 1,4 のいずれかである。 B が4個取り除くという選択を行うと,残りの石の個数は2となる。この状態において A が取り除ける石の個数は1 のみであり,その次に B が1個取り除いて B が勝利する。
したがって, B が自分の番で取り除く石の個数を適切に選択していけば,必ず B が勝利できるので, n=10 のときのゲームは後手必勝である。
 以下の設問に答えよ。
(1) どの自然数 n に対しても,このゲームは先手必勝または後手必勝のいずれか一方であることを示せ。
(2)  n=456 のとき、このゲームは先手必勝であることを示せ。
(3) このゲームが後手必勝となる n は無限に多く存在することを示せ。




まず第一に,問題文が長い…

問題文が長いと,その時点で意欲を消耗しますね。まぁでも,この程度で萎えるようなやつは要らんということでしょうから
頑張って取り組んでみましょう~ eto_uma.gif
ゲームに関する大問は前回の特色入試にもありましたね。この手の問題は好き嫌いが分かれそうです。

(1)はこのゲームが先手必勝または後手必勝のいずれか一方であることを示すものです~
このゲームは引き分けがないので,最終的にAかBかのどちらかが勝ちます。
はじめの石の個数が n であったとき,考えられる状況としては「先手必勝」「後手必勝」「どちらでもない」
だと思いますが,「どちらでもない」とは一体どういうことでしょう。
相手の石のとり方次第で勝つか負けるかが変わってしまうということですね。
ということは相手の意思に(ダジャレではないよ)委ねられてしまうのだから確率の問題になってしまいます。
ここで示さなければいけないのは,ゲームの結果が確率に支配されるものではないということです。

はじめの石の個数 n に関する数学的帰納法を用いて証明していくとよいでしょう~ hikari_pink.gif
n=1,2,3,…,k の場合に「先手必勝」か「後手必勝」かが決まっているとしたら,
n=k+1 の場合でも,先手Aが何個か石を取った後でなら,残りの石の個数は k 以下なのだから
後手Bにとっては自分が必勝か否かの運命が既に決まっていることになりますね。
先手Aにとってははじめの一手で後手Bを必敗の運命に陥れることが出来るかどうかで必勝か否かが決まります~ kaeru_en1.gif


ddd26.jpg

ddd27.jpg


今回のゲームに限らず,結果が確率に支配されないゲームでは必ず「先手必勝」か「後手必勝」かのどちらかになります。

では具体的に n=456 の場合に「先手必勝」と「後手必勝」のどちらなのかを判定せよ,というのが(2)です。
試しに n=1,2,3,…,15 の場合について「先手必勝」か「後手必勝」か判定してみましょう。



ddd28_20170113140529bb8.jpg


ddd29.jpg


この調子で n=456 まで調べていくのは骨が折れます。
しかし, n=456 のとき,先手Aがはじめに441個の石を取ってしまえば後手Bは残り15個の状況に
追い込まれます。上で見たように n=15 の場合は後手必勝なので,残り15個の状況にあるBは必敗です m_0194.gif



ddd30.jpg



今回の「平方数を取り除いていく」というゲームはあまり馴染みが薄いかもしれないですが
どうやら「Subtract a square」という項目でWikipediaのページが存在する程度には知られているようです。
https://en.wikipedia.org/wiki/Subtract_a_square
このWikipediaのページ内のリンクから,後手必勝な石の個数の列が挙げられているページに飛べます。
https://oeis.org/A030193
2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, 52, 57, 62, 65, 67, 72, 85, 95, 109, 119, 124, 127, 130, 132, 137, 142, 147, 150,
170, 177, 180, 182, 187, 192, 197, 204, 210, 215, 238, 243, 249, 255, 257, 260, 262, 267
が挙げられていますが,見方を変えると,それ以外だと先手必勝だということです。
つまり,圧倒的に先手必勝の n の方が多いんです mush.gif

ところが,後手必勝の n は決して有限個ではなく,無数に存在します。
それを示すのが最後の(3)の設問です。
背理法で示していくことが出来ます~

後手必勝の n が有限個であったなら矛盾が生じることを確認していきましょう。
隣り合う平方数どうしの間隔はどんどん大きくなっていくことがポイントです。
後手必勝の n の中で最大のものが M だと仮定します。
n を十分大きくすると,はじめに何個石を取っても残った石の数が M 個より多い状態に出来ます。
すると後手Bは必勝個数で自分に回ってくるため M が最大だという仮定が崩れてしまいます mug.gif




ddd31.jpg






   
関連記事
スポンサーサイト

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

コメント

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。