プロフィール

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

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

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

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

なかなか難しい問題ですが,ぜひ正解を目指して考えてみてください~
非公開コメント

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