プロフィール

mathnegi

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

カレンダー

06 | 2018/07 | 08
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ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

京大特色入試のコインの問題

2015.12.03 12:19|大学入試問題
どもども。

先日行われた京大の特色入試。
 「意欲的でとがった人材」が欲しいらしく今年から導入されました。
理学部では4時間で数学の問題4問を解くというスタイルだったようで,
(ほかに口頭試問があるほか,センターの得点も一定基準以上取らなきゃダメです)
数学科だけにとどまらず理学部なら共通でこの試験内容のようです。
数学が著しく得意な人が有利かもしれませんね~
他の学部の試験内容とかも京大のサイトで見ることが出来ますが,理学部の数学4時間がやはり際立っています~
そしてその問題というのが実に難しい~

面白い試みだと思うので今後も期待です。
どこの大学でもAO入試や推薦入試のようなものはぬるいものでなく
一般入試と同等以上に過酷なものであって欲しいものです~

そんな特色入試ですが,問題がムズい!ていうのが新聞記事化されて話題になっていました。
「こんな問題が出題されてましたよ」っていうことで,コインの問題が記事に載せられていたのですが
今回はそれについてちょっと眺めてみます。


【問題】
n を3以上の整数とし, k を自然数とする。表裏の区別のつく n 枚のコインを用いて1人で以下のゲームを行う。
まず,ゲームの初期状態として, n 枚のコインを円周上に等間隔に並べる。各コインは表または裏である。
以下の操作を何回か繰り返す。
操作…並べたコインの中から連続する k 枚を選び,選んだコインをすべてひっくり返す。
この操作を何回か行った結果,すべてのコインを表にすることができれば,ゲームは終了する。

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

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

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

c15_20151203100133e0b.jpg



1人でこんなゲームをして遊ぶ人なんてこの世界にどれくらいいるのでしょう。
では考えてみます~
【問1】は7角形状に並んだパターンです。 k=3 なので一度に3枚の連続するコインを
ひっくり返すことが出来ます。ひっくり返す操作を反転と呼ぶことにします~
既に3枚のコインが表になっています。残り4枚も表に出来ればよいのですが,
表になってるコインに挟まれてたりするので,反転操作をすることによって,
せっかく表になっていたコインが裏に反転されてしまうような事態が起きたりします~
とりあえずこういうのは実験してみることが大事ですね。
試行錯誤してみると,例えば次のように反転操作を繰り返すと4回でゲーム終了に持ち込めます~

c1_201512030216289e1.jpg

少なくとも4回の操作で終了が可能であることが分かったので,最小回数は4以下ということになります。
果たして3回以下の操作で終えることが出来るでしょうか。

【問1】~【問3】全てで共通して言えることですが,ポイントは初期状態で表になっているコインは偶数回,
裏だったコインは奇数回反転されれば全てのコインが表になる
ということです。
ちなみに,重要なのは回数であって順番ではありません。どういう順序で反転させても結果は同じです。
ここで以下のようにコインに(1),(2),…,(7)と番号をつけていきます。
c2_20151203021629470.jpg


2を法とする合同式を利用してみることにします。
例えばコイン(1)は偶数回反転されれば良いので,これは 
という条件式で表せます。他のコインについても同様であり,  に関する
連立合同方程式が立ちます。それを満たす  があるかどうかを見ていけばよいですね。

c3_20151203021629019.jpg

c4_201512030216309dc.jpg


これをみると,最小回数4以外にもその次に可能なのが6回であるとか,どの連続3枚を何回反転させれば良いかなど
色々なことが読み取れますね。

【問2】について考えていきます~

さっきと同じように,コインに番号をつけて合同式を立ててみましょう~
mod 2 の下では,  でなければならないのですが,
別の観点から  でなければならないという式も出てきてしまいます。
これは不合理ですね。つまり,条件を満たす  が無いのでゲーム終了が出来ません~

c5_20151203021630408.jpg



では厄介そうな【問3】について考えます~

とりあえず合同式を立てるところまではさっきまでと同様です~


c6_201512030216317c5.jpg

便宜上,数列  の添字は mod n の下で考えておきます~
そうすると例えば, n=3 のときは



のような計算が出来ます。添字部分は mod 3 で,足し算部分は mod 2 で考えているので混同しないようにしましょう~
さて,ここから3つの場合に分けて論じていきます。

まずは k が偶数の場合を考察してみます~

c7_201512030217309c3.jpg

k が偶数だとゲーム終了出来ない場合が存在するようです。

では, k が奇数だったらどうでしょう。
n と k が互いに素 かどうかで場合分けします。

c8_20151203021731c0d.jpg

ここで, n×k=k×n であることに着目します。

 という和を考えてみると,
これは  として捉えると,
 と合同で,
また,  
として捉えると,今度は A と合同になります。
n と k の最大公約数を d とすれば,  はすべて添字が mod d の下で
1と合同になるものばかりです。つまり,いずれも d で割ったときに1余るような番号を持つコインの反転回数なので,
余りが1でないものは含まれていません。
 でなければならないということは,添字を d で割ったときの余りが
1でないような  の値(例えば )を調整してやれば不合理な例が作れてしまうということです。
初期状態次第で A の値は0にも1にもなりますからね。
さっきの【問2】の流れなんかが具体例と言えるでしょう。


c16_20151204110317d89.jpg


最後に, k が奇数であって,なおかつ n と k が互いに素である場合について考えます。

この場合,実は特定の1枚のコインだけ表裏を逆にするという動作が可能です。
ということは,初期状態で裏になっているコインが1枚しかなければ当然ゲーム終了に持ち込めますし,
もし複数枚あったとしても,1枚ずつ反転させる操作を繰り返し行えば最終的にゲーム終了に持ち込めます。
したがって,どんな初期状態にも対応できるので,求めるべき必要条件が
 k が奇数であって,なおかつ n と k が互いに素であることと結論付けられることになります。

ではどうして,特定のコインだけ表裏を逆にすることができるのでしょうか。
2x+3y=1,5x+7y=1など,互いに素な自然数 p ,q に対して不定方程式 px+qy=1 を考えると
例えばユークリッドの互除法を使ってその解を少なくとも1個発見できます。
それを利用して無数にある解の一般形を作ることが出来るのでした。
2x-3y=1 なども 2x+3z=1 (ただし z=-y) のように考えれば上のパターンに帰着できます。
いま, 2n と k は互いに素なので,不定方程式 (2n)x-ky=1 は無数の解を持ちます。
特に x>0, y>0 であるような解も持つので,そのうち1組  をとってきましょう~

いまからコインの番号は mod n の下で考えることにします。
はじめに,  の連続 k 枚を反転させ,
次に  の連続 k 枚を反転させ,
次に  の連続 k 枚を反転させ,その調子で続けていって,
 の連続 k 枚を反転させるところまで
進めたとしましょう。これは結局  から  まで順番に反転を施したことと同じです。
このとき (1),(2),(3),...(n-1) は  回反転され(つまり偶数回の反転だから表裏が変わらない!), 
(n) だけ  回反転されます(つまり奇数回の反転だから表裏が逆になる!)。
こうして番号が (n) のコインだけ表裏が逆になるのです。


c10_20151203021732d86.jpg
c11_20151203021733697.jpg


c12_201512030217330f9.jpg



裏になってるコインを1枚ずつ表にしていくのを繰り返すことで解決はするのですが,
多分その方法では操作回数が無駄に多くなってしまいがちです。
最小回数を目指すならやはり連立合同方程式  にも目を向けておきたいところです。
不定方程式の解としてとってきた  を利用して具体的な初期状態が与えられたときの  たちの取り方,
つまり連立合同方程式  の解も見つけられます。

 という和を
 として捉えるのと
 
捉えるのとで比較するとよいです~


c14_20151203021756e97.jpg



c13_201512030217557dc.jpg




なお,高校範囲を越えると,連立合同方程式 を行列を用いて表してそれを解くという方針でも解けます。
巡回行列式の計算の知識などがあればいけます~



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

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

コメント

No title

本問について質問です.巡回行列式を用いて解く場合,
Aを巡回行列とするとき,
detA=
k (nとkが互いに素)
0 (nとkが互いに素でない)
となるのは計算で分かったのですが,(1のn乗根を利用する方法です.他にありますでしょうか?)
これをどう利用するのでしょうか?
Aの余因子行列をA'とするとき,
(i)nとkが互いに素かつkが奇数である場合
ks=A'a となり,mod.2で見れば s≡A'aとなるため,A'の成分が整数であることと合わせて,sについて必ず解けることがわかるので,nとkが互いに素であるなら操作によってすべて表にすることができるのはわかりますが,
(ii)nとkが互いに素かつkが偶数である場合
は,mod.2で見て
A'a≡0 となり,
また
(iii)nとkが互いに素でない場合も
A'a=0となるので,A'a≡0です.
これらはいかなるaについても成り立たなければならず,A'≡零行列(mod.2)でなければ,矛盾することとなり示せるのですが,Aの余因子行列が果たして本当にゼロ行列にならないのか?がわかりません.
それとも,
そもそもA'自体はmod.2で見れば,nとkが互いに素かつkが偶数のときやnとkが互いに素でないときは零行列であって,こちらは別の議論をしなければならないのでしょうか?

例えばnとkが互いに素でない場合は,
As=a の両辺に基本行列をかけることによって (rankがn未満の階段行列)s=Pa (Pは基本行列の積)
となり,もしこれがs,aが実ベクトルであれば次元の違いでAsによって全てのaを表現できない,という議論もできると思うのですが,mod.2で見たとき,果たしてPaの次元は元のままなのか? という疑問があります.(Pの下二行がすべて0になってしまうことはないのか?ということです)

わかりづらくなってしまって申し訳ないのですが,要するに,detAの値のみを用いて議論を完成させることはできないのか?ということです.ご回答頂ければ幸いです.宜しくお願い致します.

No title

コメントありがとうございます~

巡回行列式の計算では1のn乗根を使った手法がよく知られているので
それが多分一番無難な流れなんだと思います。他にも何か知られた手法があるのかもしれませんが
自分はあまりよく知らないです~
確かに detA= k (nとkが互いに素) ,0 (nとkが互いに素でない)
になりますね。Z/2Zが表す体の上で解いていくことになるので更に
detA= 1 (nとkが互いに素 かつ kが奇数) ,
0 (「nとkが互いに素でない」または「nとkが互いに素 かつ kが偶数」)
に発展します。
As=a が任意のaに対して解けるかという問題は,正方行列Aが定める線形写像が
上への写像になるかどうかという点に帰着され,それは結局Aが正則行列であるかどうかで
判断ができるので, detA= 1となる「nとkが互いに素 かつ kが奇数」で解決だと思います。
ks=A'a という変形はAが正則行列のときには正しいですが,
Aが正則行列でない場合は必ずしも正しくはないです。
AA'=A'A=(detA)E (Eは単位行列)は常に成り立つので,
この事実を経由してA^{-1}=(1/detA)A'というおなじみの式が出てきたり,
今回のks=A'aという関係式が出てきたりしますが,detA=0のときはAA'=A'A=0
になってしまい,ks=A'a に到達できません。
はじめのうちは実数体R上で考えておいて,ks=A'aに到達してからZ/2Zに切り替えようとすると
おかしなことになります。
「n=3,k=2」や「n=4,k=2」などの具体的な場合で実験としてみるとよいと思います~
基本変形を施していってもAs=aからA'a=0に辿り着かないはず。

仰る通りですね…基礎的なことで勘違いをしておりました。ありがとうございました。m(_ _)m

No title

自分も結構見落としや勘違いやケアレスミスなどやらかします~
まぁ楽しむことが何よりなのでほのぼの頑張りましょう~

No title

正解はわかりませんが、自分の解き方の3問目の結果は
n≠k かつ n≠2k

ちなみに、1を表とする、0を裏面とする。n=7,k=6 でも解があります。

サンプル
1010100

1101011

0000100

1111111

No title

コメントありがとうございます~


正解は「kと2nが互いに素」のようなので
残念ながら「n≠k かつ n≠2k 」とは異なります~
1010100

1101011

0000100

1111111
の流れはサンプルとしては正しいですが,
正解へ辿り着くための論理には修正が必要な箇所があるみたいです。

No title

よく考えたら、確かに必要条件で十分じゃないですね

どこかの条件は甘いかもです。

ありがとうございました

No title

そうですね,必要条件止まりになっています~
もう少し必要性に関して詰めていくと良いのではないでしょうか。

なかなか難しい問題ですが,ぜひ正解を目指して考えてみてください~

誤植?の報告と質問

恐らくこれは誤植なんじゃないかと思うのですが、(3)の最大公約数dが出てきたあとに「~a[i]の値を調整してやれば不合理な例が作れてしまうということです。」とあるのですがこのa[i]はa[d]ではないでしょうか?またそこから11行上の「~a[(n-1)k+1]と等しく」のところは等しい、ではなく合同ではないでしょうか?これは比較的些細なことですが直ぐ下に「Aと合同になります。」とあるので、混乱する人が出てきてしまうかもしれないので一応報告します。

で、この問題についてなのですが、mathnegiさんはこの問題を見てからこの合同式でやるやり方でいこう、と直ぐ思いましたか?僕はどうもこういった組み合わせ数学が苦手で(それ故今まで避けてきて悪循環なのですが、、、)、愚直にひっくり返していく方法しか考えてませんでした、、、。それでも(2)までいけたもんですから「なんとかこんな感じで頑張れば(3)もいけるんじゃね?」なんてそのまま行って詰みました、、、orz。

やはりあの方法は(3)まで見越して(1)に手をつける前から考え始めたのでしょうか?それとも、巧い方法を探すことを念頭に置きながら始めは愚直にやっていってその中で思い付いた感じでしょうか?元々知っていた、という可能性もありますが、、、。

やはり僕自身の組み合わせ数学への苦手意識もあいまって、巧い方法を考えるのにどれくらい時間をあてたらいいのか、というのは非常に悩みます。つまりは沢山時間かけて有益なことがなにもでなかったときのことを考えると恐ろしい、という気持ちと、愚直な方法でアタックする方がむしろ時間の浪費になるかも、、、(解き終わらない、という意味で)という気持ちが葛藤を起こすわけです。この辺りmathnegi さんのご意見を聞いてみたいです。

またこの問題にかけられる時間は単純計算で4h/4=1h。仮にあの巧い方法がサッと思い付いたとして、すると(2)まではさらっといくでしょうから答案に書く時間も含めてここまでで多分残り40分くらい。問題の(3)はまず答えを予想するのに時間がそれなりにとられ、「互いに素」から直ぐ一次不定方程式が連想されるのは良いとして、それを具現化するのにまぁまぁ時間がとられ、そして答案を書き上げるのにもまたまぁまぁ時間がとられると思います。本番でこんな感じにいけたらかなり順調なはずですがそれでもどうにも1hは余裕で越えそうに思います。普通はそんな順調にいかない、もっといえば僕みたいに愚直なやり方でアタックしてタイムロスなんかすればとても時間内に解けたものではないと思います。そこでお聞きしたいのですが、mathnegi さん自身はどれくらい時間がかかったのでしょうか?覚えている範囲内でいいので教えて下さい。また本番だったら貴方ならどういう風な戦略を採られるでしょうか?

Re: 誤植?の報告と質問

コメントありがとうございます~

「a[i]はa[d]ではないでしょうか」のくだりはa[i]で大丈夫ですね。
添字のiはdで割ったときの余りが1以外のものならなんでもOKで,その代表例として下の手書き部分ではa[d]を
採用したということになっています~
一応わかりやすくすために少し文章を修正しておきます~
「~a[(n-1)k+1]と等しく」の部分は確かに「合同」の方がわかりやすいので修正しておきます~
ご指摘ありがとうございました~

この問題は当時,新聞に記事として載っていたりもしたこともあり,特色入試の問題の中で一番多くの人の目に触れた
ものだと思います。それゆえ,当時から多くの人がブログなりツイッターなりで解説記事を書いたりしていましたが
合同式を用いない解答が多かった記憶があります~
実際に最初に解いてみたときから自分は合同式で攻めていましたが,そのあと記事化する前に,
合同式を使わない解答も見かけて,「うん,まぁそっちのほうがシンプルだよねぇ」と思いつつも
まぁ同じ解答例でも面白くないし,そこでわざと自分は合同式を使った解答で記事化してみようということに
したような気がします~

自分は数式化せずにひっくり返す操作のイメージだけを膨らましていくような系統がどちらかと言うと苦手ですね~
今回のような「~~~というルールでゲームをする」系の問題は苦手です~
あとはゲームの必勝法を考えろ,みたいな問題とかですかね~
法則性・規則性を数式化してみてようやく「ああ,そういうことか」って思えるタイプですかね。
だから最初から合同式を使う方向に走ったような気がします。

最近は東大生のクイズ対決だとか偏差値の高い戦いをテレビで見かけることが多いですが
自分はそういった卓越した能力の持ち主ではなかったので,18歳頃当時の状況では特色入試あたりのレベルは
歯が立たない感じだったんじゃないでしょうかね~
時間無制限で考えてみてようやく解けたり解けなかったり,みたいな。

大体このような試験問題は「あるポイント」に着眼できれば突破口が一気に開けるというものが多いかと思います。
法則性・規則性がぼんやりとしたものから明確にみえるようになるところまでが大変だと思います。
ぼんやりした考察をしているうちは暗中模索状態が続くことでしょう。
とはいえ,最初はぼんやりした考察から始まるものです。愚直な思考もあるでしょう。
具体例などを通して,どこに本質があるのかを意識して一生懸命見い出すことが大切かなぁと自分は思います~

実際に試験を受けた受験生はどれくらいの得点率だったんでしょうね。
「解けること」だけでもハードルが高いですが,「短時間で解けること」は更にハードルが高いです。
「短時間で解いて整理して答案をまとめること」はもっと更にハードルが高いです。
単純計算で4h/4=1hということなら,多少表現が雑でも伝わればOKくらいの割り切りで答案を書かなきゃいけないですかね。
それでも十分評価してもらえると思います~

Re:Re: 誤植?の報告と質問

仰る通りでした、失礼しましたm(__)m。

調べてみるとこの問題は解説サイトが色々とあるようですね。そちらにも目を通してみようと思います。

mathnegi さんは現役のときからなんでも解けたんだろうなぁ、と思っていたので意外でした。文面だけだと僕の状況とそっくりですが恐らく格が違うのでしょうね笑。精進します。

具体例を迅速に次から次へと処理していくのが重要かなと感じました。頭の回転が遅いのかついノロノロ考えてしまうようなタイプなもので、、、。

京大は採点の厳しさで有名ですが、この問題を時間内に解ききる難易度などを考えると特色入試に関しては、その意図もあってか、採点が緩めになるのでしょうかね。とがった才能をとりたいみたいですし。雑な答案であっても本質的にこの問題を時間内に解ければそれはとがった才能でしょうし。

Re: Re:Re: 誤植?の報告と質問

この問題に限らず特色入試の問題を解説しているサイトがいくつか探せば見当たると思います。
自分と違う解法だったりすると面白いなあとか思ったりします~

現役の時から数学は大好きっ子でしたが決して神童とかではなかったですよ~
格の違いとかもないと思いますよ~

最近の京大入試は,問題の難易度はそこそこ,採点は厳しめ,ていう話をよく聞きますが,
特色入試の場合ではどこまで厳しいんでしょうね。
難易度は鬼ですし,そもそも元々ある程度のハイレベルな受験者層ですから,完成度よりも発想力の豊かさのほうが
重視されることを期待したいですよね。
もちろん,多少雑でも,といっても限度はありますが~
数学科志望者限定の試験だったら厳しめであっても分からんでもないですが~
非公開コメント

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