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

この記事は日曜数学 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は突然の死ジェネレータを使って作成しました.

広告

京大特色入試, コインの問題を解く」への2件のフィードバック

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中