京大特色入試, コインの問題を解く (その2)

この記事は日曜数学 Advent Calendar 2015の16日目の記事です. 7日目の記事である京大特色入試, コインの問題を解くの続編でもあります. (既にインターネッツでは旬を過ぎてしまいましたが, 気にしない!)

昨日の記事はsimizut22さんによるオイラー標数を使って数える話でした.

再掲, 超難問

前回は問1を解くところまで行きました. その方法は, コインの状態とコインの操作をベクトルと行列で表し, それらを使って立てた方程式を行列の計算で解くという手法でした.

しかし, これで全て上手く行くわけではありません. 問2がこの解法をはばむ壁として立ち塞がります. それを解決して先に進んでも, さらに問3が求める一般的な解答を導き出すところが壁となり, 解決はできたものの (今のところ) 泥臭い解法になってしまっています. それでも, ベクトルと行列を使った線型代数の視点から問題を眺めることに意義はあるはずです. それを一緒に感じ取れたら嬉しいです.

最初の壁, 問2

おさらいも兼ねて, 問1を解いた方法で問2も解いていってみましょう.

一番上の表になっているコインから始めて, 右回りにc1, c2, c3, c4, c5, c6と名前を付けます. c1, c4, c5が表になっているので, 初期状態はこんなベクトルで表されます.

Initial2

ここからgという操作をした結果, 全てのコインが表になる, という事実はこんな方程式で表されます.

Problem2

さて後はこの方程式を解けば良いだけです.

前回と同じように左辺のベクトルを移項して操作行列の逆行列を掛けて, あれ……

NoInverse

_人人人人人人人人_
> 逆行列が無い <
 ̄Y^Y^Y^Y^Y^Y^Y ̄

実はn=6, k=3の操作行列には逆行列が無いのです. さてこの状況で, どうやったら解けるのでしょうか!?

ひとまず掃き出し法を使って操作行列の逆行列を求めようとしてみましょう. 操作行列の右に単位行列をくっ付けるところからスタートです.

SweepOut1

これを行の基本変形でいじっていき, 左半分を単位行列にすることを目指します. 結果は

SweepOut2

_人人人人人人_
> んんん?? <
 ̄Y^Y^Y^Y^Y ̄

となりますが, 下2行が何か変ですね. 左上の角から右下へ向かって45度のラインに1が6つ並んでいて欲しいのですが4つしか並んでいません. 仕方無いので今のところは, この結果の右半分を逆行列の変わりに使いましょう.

SweepOut3

やっぱり何か変ですね. 気付きましたか?

おかしな箇所は下から2行目です. 左辺の掛け算を計算するとgがどんなベクトルであっても, 下からの2つ目は0です. しかし右辺は1です. つまり絶対に両辺は等しくなりません. このせいで問2の配置から全てのコインを表にすることはできないことが分かります. 問1と同様に, ちゃんと方程式を立てて解いていったので, 絶対に解が無いことが示せました.

壁の観察

受験問題の解答としてはここまででも十分なのですが, 今ぶつかった壁をもうちょっと細かく観察してみましょう. 問2の問題を拡張して「k=6, n=3のときに解ける配置は何か?」を調べます. 解くべき方程式は上のと同じで

GeneralizedEquation

という形になります. この式をよく見ると,「操作を表すベクトル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つの操作の結果が何もしなかった場合と同じになります.

Kernel

それはこのベクトルに操作行列を掛けてみれば分かるので, ぜひ計算してみてください.

『何もしない』という操作も含めて4通りの「コインの状態を変えない操作」があるために, コインの操作のパターン数 (64通り) に対し, 結果のパターン数が1/4の16通りに減ってしまっていたのでした. 逆に,「コインの状態を変えない操作」が『何もしない』しかなければ, 結果のパターン数が減ることはなく, どんなコインの状態でも全て表にできることになります. このことから問3を解くためには「『何もしない』という操作と, 同じ結果になる操作があると」必要十分条件を求めれば良いことになります.

さてそれでは問3を解いていきましょう. 操作行列は一般には

OperationMatrix

のような形をしています (1や”…”が無いところは全て0). なのでコインの操作の方程式は

GeneralEquation

となります.

ここでnとkが等しいかどうかで場合分けをしましょう.

n=kの場合

g1, g2,…, gnのうち1のものが偶数個ならば方程式が成り立ちます. この問題ではn≧3なので, g1=g2=1でそれ以外は全て0とすることができ, 常にこの方程式を満たす操作ベクトルgがあることが分かります. このケースはこれで完了です.

n>kの場合

ここからの計算がしやすいように, 操作行列を少し加工しましょう. (実は, 操作行列に行の基本変形を行っても必要十分条件には影響が無いのですが, その説明はこの記事では省略します.「おまけ」の節からリンクを張った解説ではきちんと示しておきます.)

第2行を第1行に加え, 第3行を第2行に加え, この調子でを繰り返して, 最後に第n列を第n-1列に加えると, 操作行列は次のような形になります.

ModifiedOperationMatrix

コインの操作の方程式もこんなふうに変わります.

ModifiedGeneralEquation

左辺を展開して連立方程式の形で書いてみましょう.

SimultaneousEquation

式を整理して

SimultaneousEquation2

こんなふうにしておきます. (ここでも1+1=0を使っています.) ここから

ChainedEquation

こんなふうに, 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を使っています.)

ChainedEquation2

として, この式に出てこない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) が 6の倍数であることを証明せよ

※文中の数式はYusuke TeradaさんのTeX2imgを使って作成しました.「突然の死」のAAは突然の死ジェネレータを使って作成しました.

広告

京大特色入試, コインの問題を解く

この記事は日曜数学 Advent Calendar 2015の7日目の記事です.

昨日の記事はキグロさんによる3点を通る円がただ1つだけ存在することの証明でした.

超難問

先週あたり, 京大の特色入試の問題 (理学部) が超難問だと話題になっていました. 確かに大学受験でこの問題を解けと言われたらかなり難しく,「五輪級」(数学オリンピック本選あたりかな?) というのも納得です.

既にこの問題を解いている人はいます. 問1については実際の手順を示すことで解答としているようですが, ここではn=7, k=3の場合について一般的に解きたいと思います. 一般的に解くことで, 示す手順が最小の手順だということも証明します.

記法

問1の表になってるコインのうち, 一番上にあるものから時計回りにc1, c2,…, c7と名前を付けます. (「コイン (coin)」のcを使いました.) コインが表の状態を0, 裏の状態を1で表します. さっきの名前を変数名として使って「コインc1が表であること」を「c1の値が0であること」で,「コインc1が裏であること」を「c2の値が1であること」で表すことにします.

問1のコインの状態はこんなふうに表せます.

CodeCogsEqn(12)

_人人人人人人人人人_
> 突然のベクトル <
 ̄Y^Y^Y^Y^Y^Y^Y^Y ̄

突然ベクトルが出てきて驚いたかもしれませんが, ベクトルで書く方が便利な理由があるんです. それについては後で分かるので, ひとまず今のところは,「7つの式を1つにまとめて書くため」くらいに思っておいてください.

次にどのコインをひっくり返すかの操作にも名前を付けましょう. ちょっと恣意的なのですが, c6, c7, c1のコインをひっくり返す操作をt1と書くことにしましょう.(「裏返す (turn)」のtを使いました.) t1から時計回りにズラしていって, c7, c1, c2をひっくり返す操作をt2とし, c1, c2, c3をひっくり返す操作をt3等々としていきます. そして各操作がひっく返すコインを1, ひっくり返さないコインを0で表すと, こんなふうにベクトルで書けます.

_人人人人人人人人人_
> 再度のベクトル <
 ̄Y^Y^Y^Y^Y^Y^Y^Y ̄

CodeCogsEqn

ひっくり返されるコインの位置が1つずつズレているのが分かると思います.

ここでわざわざベクトルで書いてきた利点を説明します.

CodeCogsEqn(13)

というc1, c4, c6のコインが表になっていて, 残りが裏になっている状態で操作t1を行うとc6, c7, c1のコインがひっくり返るのでc4, c7のコインだけが表になっていることになります. これをベクトル計算で書くとこうなります.

CodeCogsEqn(14)

_人人人人人人人人_
> 突然の足し算 <
 ̄Y^Y^Y^Y^Y^Y^Y ̄

なんとコインを操作した結果がベクトルの足し算で書けてしまいました. 実際にコインを動かして確認してみると

 ● ○ ← これがc1
    ●
○ ← これがc6
    ●
 ● ○ ← これがc4
※「○」が表,「●」が裏

↓操作t1を行う = c1, c6, c7をひっくり返すと,

 ↓これがc7
 ○ ●
    ●
●
    ●
 ● ○ ← これがc4

と, ちゃんとゲームのルールどおりに計算できていますね.

1+1=0なんて変な足し算をしてますが, 裏の裏は表ってことでそういう計算ルールだと思ってください. これでも立派な足し算になるんですよ. (勘の良い方はmod 2の計算だと気付いたんじゃないかな?)

こんなふうにコインの操作を足し算という計算で表せることが, ベクトルで表現した利点です. そしてそして, さらにさらに, 複数回の操作もこんなふうに書けてしまいます.

CodeCogsEqn(15)

そしてそして, こんなふうにも書けます.

CodeCogsEqn(16)

_人人人人人人人_
> 突然の行列 <
 ̄Y^Y^Y^Y^Y^Y ̄

新たに出てきた行列はt1, t2,…, t7を並べて作ったものです. ここまで複数回のコインの操作が行列を使って1つの式で書けました.

「t1とt4を行う」というコインのひっくり返し方は

CodeCogsEqn(6).gif

というベクトルで表されています. 行列とベクトルの掛け算を計算してみると, c+t1+t4の計算と同じことをしているのが分かるでしょう.

実は, このコインの操作を表す行列が今回の問題の核心部分なのです!! この行列を「操作行列」とでも呼んでおきましょう. (あ, これは一般的な名前ではなく, 今私が勝手に命名したものですよ.)

コインの操作の方程式

さて, コインの操作を式で書くことができたので, 問1を解くために未知数 (未知ベクトル?) を含んだ「コインの操作の方程式」を立ててみましょう.

CodeCogsEqn(17)

これで「初期状態のコインを, gという操作でひっくり返すと全て表になる」という事実が表現できました. 後はこの方程式を解いてgを求めるだけです! 細かい理屈は省いて (厳密な計算については別途まとめます) 計算の流れだけ追っていきます.

まず左辺の左側のベクトルを移項します.

CodeCogsEqn(18)

そして左から操作行列の逆行列を掛けると,

CodeCogsEqn(19)

と, あっさりgが求まってしまいました. (逆行列を求めるところでも1+1=0という特別ルールで計算しています.) どうやらt2, t3, t4, t5という操作をすると全て表になるようです. 実際に試してみましょう.

 ● ○
    ● ← これがc2
○
    ●
 ● ○
※「○」が表,「●」が裏

↓操作t2 = c7, c1, c2をひっくり返す

 ○ ●
    ○
○
    ● ← これがc3
 ● ○

↓操作t3 = c1, c2, c3をひっくり返す

 ○ ○
    ●
○
    ○
 ● ○ ← これがc4

↓操作t4 = c2, c3, c4をひっくり返す

 ○ ○
    ○
○
    ●
 ● ●
 ↑これがc5

↓操作t5 = c3, c4, c5をひっくり返す

 ○ ○
    ○
○
    ○
 ○ ○

無事全部のコインが表になりました!! しかもちゃんと方程式を立てて解いたので, これ以外に答が無いことが分かって, 問1が完全に解けました!

宣伝

実はここで説明した考え方や問題の解き方は, 私が『続・アルゴリズムを学ぼう』という本の「第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

解説がだいぶ長くなってしまったので, いったんここで一段落とします. (問2, 問3の解説は12/16の予定です.)

さて明日はtsujimotterさんによる「とあるニコニコの動画にインスパイアされた話を書きます」です. どんな内容なのでしょうか. 楽しみです.

(追記 2015/12/08) tsujimotterさんの記事が公開されました. 1つの問題を色んな方法で解く話です. 「3の100乗を19で割ったあまりは?」を4通りの方法で計算する

※文中の数式はCodeCogs(R)のEquation Editorを使って作成しました.「突然の死」のAAは突然の死ジェネレータを使って作成しました.