この記事は日曜数学 Advent Calendar 2015の16日目の記事です. 7日目の記事である京大特色入試, コインの問題を解くの続編でもあります. (既にインターネッツでは旬を過ぎてしまいましたが, 気にしない!)
昨日の記事はsimizut22さんによるオイラー標数を使って数える話でした.
再掲, 超難問
[京都新聞]京大特色入試に超難問 数学の筆記試験“五輪級” ift.tt/1Ig4UlG https://t.co/aRhUauYONt—
京都新聞 (@kyoto_np) November 28, 2015
前回は問1を解くところまで行きました. その方法は, コインの状態とコインの操作をベクトルと行列で表し, それらを使って立てた方程式を行列の計算で解くという手法でした.
しかし, これで全て上手く行くわけではありません. 問2がこの解法をはばむ壁として立ち塞がります. それを解決して先に進んでも, さらに問3が求める一般的な解答を導き出すところが壁となり, 解決はできたものの (今のところ) 泥臭い解法になってしまっています. それでも, ベクトルと行列を使った線型代数の視点から問題を眺めることに意義はあるはずです. それを一緒に感じ取れたら嬉しいです.
最初の壁, 問2
おさらいも兼ねて, 問1を解いた方法で問2も解いていってみましょう.
一番上の表になっているコインから始めて, 右回りにc1, c2, c3, c4, c5, c6と名前を付けます. c1, c4, c5が表になっているので, 初期状態はこんなベクトルで表されます.
ここからgという操作をした結果, 全てのコインが表になる, という事実はこんな方程式で表されます.
さて後はこの方程式を解けば良いだけです.
前回と同じように左辺のベクトルを移項して操作行列の逆行列を掛けて, あれ……
＿人人人人人人人人＿ ＞ 逆行列が無い ＜ ￣Y^Y^Y^Y^Y^Y^Y￣
実はn=6, k=3の操作行列には逆行列が無いのです. さてこの状況で, どうやったら解けるのでしょうか!?
ひとまず掃き出し法を使って操作行列の逆行列を求めようとしてみましょう. 操作行列の右に単位行列をくっ付けるところからスタートです.
これを行の基本変形でいじっていき, 左半分を単位行列にすることを目指します. 結果は
＿人人人人人人＿ ＞ んんん?? ＜ ￣Y^Y^Y^Y^Y￣
となりますが, 下2行が何か変ですね. 左上の角から右下へ向かって45度のラインに1が6つ並んでいて欲しいのですが4つしか並んでいません. 仕方無いので今のところは, この結果の右半分を逆行列の変わりに使いましょう.
やっぱり何か変ですね. 気付きましたか?
おかしな箇所は下から2行目です. 左辺の掛け算を計算するとgがどんなベクトルであっても, 下からの2つ目は0です. しかし右辺は1です. つまり絶対に両辺は等しくなりません. このせいで問2の配置から全てのコインを表にすることはできないことが分かります. 問1と同様に, ちゃんと方程式を立てて解いていったので, 絶対に解が無いことが示せました.
壁の観察
受験問題の解答としてはここまででも十分なのですが, 今ぶつかった壁をもうちょっと細かく観察してみましょう. 問2の問題を拡張して「k=6, n=3のときに解ける配置は何か?」を調べます. 解くべき方程式は上のと同じで
という形になります. この式をよく見ると,「操作を表すベクトルgに操作行列を掛けることで, コインの状態を表すベクトルcと等しくなる」ということを語っています. 別の言い方をすれば,「操作行列は, 操作を表すベクトルから, コインの状態を表すベクトルへの対応付けを表現している」と言えます.
この「『操作』から『状態』への対応付け」という観点がとても大事なところです.
＿人人人人人人人＿ ＞ 操作→状態 ＜ ￣Y^Y^Y^Y^Y^Y￣
k=6の場合, 操作ベクトルは2の6乗で64種類あります. 状態ベクトルも同じく64種類あります. しかし必ずしも全ての状態ベクトルに操作ベクトルが対応付くわけではありません. k=6, n=3では, 操作ベクトルから対応付いている状態ベクトルは, 2の4乗の16種類しかありません. つまりコインを全て表にできるパターンは16種類しかないのです.
指数部分が6→4と2つ減っていますが, この2の由来はここまでの計算にあります. 上で操作行列に逆行列っぽいものを掛けたときに, 下2行の数字が全部ゼロになっていました. この「下2行の数字が全部ゼロ」というところから「2」という数字が求まっています.
もちろん逆行列が存在しているときは,「数字が全部ゼロの行」が無い, つまり0行なので, 指数部分は減らず「操作ベクトルの数」と「状態ベクトルの数」は同じになります.
ひとまずはn=6, k=3の場合は「行える操作の数に対して, その結果として取り得るコインの状態の数が少ない」と理解しておいてください.
最後の壁, 問3
さて「行える操作の数に対して, その結果として取り得るコインの状態の数が少ない」ということは,「操作としては別だけど, その結果のコインの状態が同じになることがある」ということです. そしてさらに「『何もしない』という操作と, 同じ結果になる操作がある」ということです. n=6, k=3の場合で言えば, 次の3つの操作の結果が何もしなかった場合と同じになります.
それはこのベクトルに操作行列を掛けてみれば分かるので, ぜひ計算してみてください.
『何もしない』という操作も含めて4通りの「コインの状態を変えない操作」があるために, コインの操作のパターン数 (64通り) に対し, 結果のパターン数が1/4の16通りに減ってしまっていたのでした. 逆に,「コインの状態を変えない操作」が『何もしない』しかなければ, 結果のパターン数が減ることはなく, どんなコインの状態でも全て表にできることになります. このことから問3を解くためには「『何もしない』という操作と, 同じ結果になる操作があると」必要十分条件を求めれば良いことになります.
さてそれでは問3を解いていきましょう. 操作行列は一般には
のような形をしています (1や”…”が無いところは全て0). なのでコインの操作の方程式は
となります.
ここでnとkが等しいかどうかで場合分けをしましょう.
n=kの場合
g1, g2,…, gnのうち1のものが偶数個ならば方程式が成り立ちます. この問題ではn≧3なので, g1=g2=1でそれ以外は全て0とすることができ, 常にこの方程式を満たす操作ベクトルgがあることが分かります. このケースはこれで完了です.
n>kの場合
ここからの計算がしやすいように, 操作行列を少し加工しましょう. (実は, 操作行列に行の基本変形を行っても必要十分条件には影響が無いのですが, その説明はこの記事では省略します.「おまけ」の節からリンクを張った解説ではきちんと示しておきます.)
第2行を第1行に加え, 第3行を第2行に加え, この調子でを繰り返して, 最後に第n列を第n-1列に加えると, 操作行列は次のような形になります.
コインの操作の方程式もこんなふうに変わります.
左辺を展開して連立方程式の形で書いてみましょう.
式を整理して
こんなふうにしておきます. (ここでも1+1=0を使っています.) ここから
こんなふうに, kの倍数だけズレた位置にあるgの要素の値は等しくなければならないことが分かります. (添字は実際にはnで割った余りを取ります.) 添字をkずつズラしていったときに, 全ての添字を渡る場合とそうでない場合があります.
kとnが互いに素 (最大公約数が1) のときは全ての添字を渡ることになり, g1=g2=…=gn となります. g1=0だと単に『何もしない操作』なのでg1=1の方を調べてみます. 連立方程式の一番下の式が成り立てば良いのでk=0が求める条件です. ただし1+1=0という計算ルールを使っているので, これは「kが偶数」ということを表しています.
kとnが互いに素でないときは, 全ての添字は渡りません. kとnの最大公約数をd (≧2) とすると, 辿った添字はdの倍数だけズレているもの全部になります. それなのでg1からスタートしたときに辿る添字と, g2からスタートしたときに辿る添字は, 絶対に重なりません. (ここの議論ではd≧2を使っています.)
として, この式に出てこないgiを0とすれば, 連立方程式の一番下の式の左辺は2k/d個の1の和になり, これは偶数なので2k/d=0と等式が成り立ちます.
長くなりましたが条件をまとめると
『何もしない操作』と結果が同じになる操作が存在する必要十分条件は「kとnが互いに素でない, または, kが偶数」
となります. これを逆にすると
『何もしない操作』と結果が同じになる操作が存在しない (つまりどんなコインの状態でも全て表にできる) 必要十分条件は「kとnが互いに素, かつ, kが奇数」
となり, ようやく問3が解けました.
おまけ
ここまではできる限り簡単な言葉で説明してきましたが, 通常の数学の文章による解答もここに置いておきます. → (ここにリンクが張られる予定)
余談
問3はかなり示すのに苦労したのですが, コインの操作の対称性を使うともっとスッキリ示せそうな気がします. 特に操作行列を変形するところが, すごく場当たり的な変形をやっているので, もっと綺麗な解答を考えたいです.
宣伝, 再び
実はここで説明した考え方や問題の解き方は, 私が『続・アルゴリズムを学ぼう』という本の「第2講 ライツアウトの数学」「第3講 続・ライツアウトの数学」で書いたことを応用したものです.
あるボタンを押すとその上下左右のボタンの点灯状態が反転するのがライツアウトですが, 問1はボタンが円環状に並んだライツアウトとも見れます. ライツアウトも数学という視点で見ると, ベクトルや行列で書かれた方程式になり, 答がバシッと求まるのです.
この記事で解説したような「数学という視点で見る楽しさ」が伝われば嬉しいです. (この記事で興味を持ってくれたなら, 本も手に取ってみてくださいな.)
アルゴリズムを学ぼう
ASCII MEDIA WORKS (現KADOKAWA) のページ: http://ascii.asciimw.jp/books/books/detail/978-4-04-886128-1.shtml
Amazon.co.jpのページ
達人出版会のページ: http://tatsu-zine.com/books/learnalgorithm
続・アルゴリズムを学ぼう
ASCII MEDIA WORKS (現KADOKAWA) のページ: http://ascii.asciimw.jp/books/books/detail/978-4-04-891394-2.shtml
Amazon.co.jpのページ
達人出版会のページ: http://tatsu-zine.com/books/learnalgorithm2
さて明日はkiguro_masanaoさんによる「数学の問題を解く動画」です. どんな内容なのでしょうか. 楽しみです.
(追記 2015/11/18) kiguro_masanaoさんの記事が公開されました. さて, どんな方法で証明するのでしょうか. mn(m+n)(m-n) が ６の倍数であることを証明せよ
※文中の数式はYusuke TeradaさんのTeX2imgを使って作成しました.「突然の死」のAAは突然の死ジェネレータを使って作成しました.
kinebuchitomo 