【層とホモロジー代数】2017.11.15

○日時
2017.11.15 (水) 20:00〜22:00

○参加者
A, K

○発表者
A

○概要
第3章 ホモロジー代数 3.3 導来関手 命題3.33から命題3.36まで

○内容

  • 右完全関手Fによる左導来関手LnFの特徴付け
  • F非輪状対象とF非輪状分解の定義
  • F非輪状分解から左導来関手が計算できること

○板書
(無し)

○次回
2017.10.?
第3章 ホモロジー代数 3.3 導来関手 命題 3.37〜

※テキスト
志甫淳, 層とホモロジー代数, 共立出版

広告

【層とホモロジー代数】2017.10.2

○日時
2017.10.2 (月) 20:00〜22:00

○参加者
A, K

○発表者
A

○概要
第3章 ホモロジー代数 3.3 導来関手 命題3.31から定義3.32まで

○内容

  • アーベル圏の間の加法的関手F: ABに対して、射影的分解を使い導来関手LnF: ABが定義できること。
    • LnFの関手性
    • 導来関手の族(LnF)nが、関手SES(A) → ES(B)を定めること。
    • A ∈ Ob Aが射影的ならばLnF(A) = O (∀n ≧ 1)となること。
    • 自然変換τ: L0F → Fがあること。Fが右完全なら自然同値になること。
    • Fが完全ならLnF(A) = O (∀n ≧ 1, ∀A ∈ Ob A)となること。

○板書

Screen Shot 2017-10-02 at 22.41.13

Screen Shot 2017-10-02 at 22.41.31

Screen Shot 2017-10-02 at 22.42.02

Screen Shot 2017-10-02 at 22.42.16

○次回
2017.10.?
第3章 ホモロジー代数 3.3 導来関手 命題 3.33〜

※テキスト
志甫淳, 層とホモロジー代数, 共立出版

【層とホモロジー代数】2017.9.11

○日時
2017.9.11 (月) 20:00〜22:00

○参加者
A, K

○発表者
K

○概要
第3章 ホモロジー代数 3.2 射影的分解と単射的分解 命題3.22から注3.30 (3.2の終わり) まで

○内容

  • 複体がよい性質を持つ二重複体に分解できること (左カルタン-アイレンバーグ分解)
    • アーベル圏の全ての対象の射影的分解が、ある添字より小さいところで消えている場合、先程の二重複体はあるところから左が消えていることになる。
  • 定義3.24〜注3.30は定義3.17〜注3.23の双対。

○板書

Screen Shot 2017-09-11 at 21.58.16
Screen Shot 2017-09-11 at 21.58.27
Screen Shot 2017-09-11 at 21.58.40
Screen Shot 2017-09-11 at 21.58.49

○次回
2017.9.?
第3章 ホモロジー代数 3.3 導来関手〜

※テキスト
志甫淳, 層とホモロジー代数, 共立出版

【層とホモロジー代数】2017.8.25

○日時
2017.8.25 (金) 20:00〜22:40

○参加者
A, K, S

○発表者
A

○概要
第3章 ホモロジー代数 3.2 射影的分解と単射的分解 命題3.21の証明まで

○内容

  • 射影的分解の定義
  • 充分射影的対象を持つアーベル圏では、任意の対象の射影的分解が存在すること
  • 対象Mの射影的分解 (P●, d●) → M は複体の射を引き起こし、別の複体の射 (Q●, e●) → N について、f: M → N から複体の射 f●: P● → Q● が誘導されること
    • 誘導される射はホモトピックを除いて一意であること
  • 短完全列 0 → L → M → N → 0 に含まれる対象 L, N の射影的分解 (P●, d_P●), (R●, d_R●) から M の射影的分解 (Q●, d_Q●) が構成でき、0 → P^-n → Q^-n → R^-n → 0 が標準的包含および標準的射影による完全列になること
    • 2行の短完全列からなる可換図式から、1つ前の命題と同じ構成で可換図式が構成できること (1つ前の命題では2次元の可換図式ができたが、この命題では3次元の可換図式ができあがる)

○板書
Screen Shot 2017-08-25 at 22.39.29

○次回
2017.9.?
第3章 ホモロジー代数 3.2 射影的分解と単射的分解 命題3.22〜

※テキスト
志甫淳, 層とホモロジー代数, 共立出版

イベントの組み立て方

なぜ書こうと思ったのか

最近いくつかのイベントに参加したり運営として関わったりしてみて, 思ったよりも行き当たりばったりでイベントが作られているのかもしれないと感じました. そこでまずイベントの組み立て方について自分の知っていることを公開して, それに対する反応をもらったり, 議論のきっかけになったりしたらいいなと思い, この記事を書いています. 参加者も運営も幸せなイベントが増える方が嬉しいので.

この記事で言うイベントは

  • 比較的短期 (1日〜数日)
  • 当日のみ関わる参加者と事前準備をする運営がいる
  • イベント当日は皆が同じ場所に集まる

という形式を前提とします.

要約 (TL;DRあるいは今北産業)

書くとは言いましたが, たぶんけっこう長くなるので要約を最初に書いておきます.

  1. 「イベントが終わったときの参加者の内的状態 (心と思考の両方含んだ精神の状態) がどうなっていて欲しいか」をまず考えよう. これが最初です. 絶対に!
  2. 次に, その狙いを達成するための手段を各種制約の中で組み立てる.
  3. そしてイベント終了後すこし間を置いてから, 最初の狙いに照らして「狙い通りだったこと」「狙いが達成できなかったこと」「意外と上手く行ってしまったこと」などの点を振り返り分析する.

本文

この記事では「イベントを作るときに常に意識していること」について書いていきます. ここで言うイベントは, 大勢で集って飲み会をしたり, 何かの勉強会で発表をしたり, キャンプに行ったりなどけっこう広い範囲のことを想定しています.

自分の経験から事例を拾ってくると, 学部4回生での卒業ゼミの発表だったり, 数学カフェでの発表や数学茶屋の運営, YMCAでの (運営側である) リーダーとしての活動というものがあります. 公益財団法人YMCA (http://www.ymcajapan.org/) とはキリスト教を基盤として社会活動を行う団体です. この団体が開催していたキャンプに参加者としてお世話にもなったし, 大学生のときに運営側もやっていました. 4回生のときの卒業ゼミでは数学的な内容の指導以外に発表の方法の指導も受けました.

主にこのYMCAと卒業ゼミで身に付けたものをこれから書いていきます. 実践のみで身に付けたので理論面は雑かもしれませんが悪しからず.

狙いの設定

まず狙いの設定とその狙いを運営全員で共有することが一番大事です.

要約でも書いたように, 狙いとは「参加者にどんな状態で帰ってもらいたいか」ということです. たいていの場合

  • 参加者のイメージ
  • どんな気持ちになったり, どんな影響を受けたりして欲しいか

をセットで考えることになるでしょう. それはこの両者を1つずつ決めるには, もう一方が決まってないと判断が難しいからです. ちなみに私は後者のことを「おみやげ」と表現することが多いです. 参加者の方々にイベントの「おみやげ」として, 何らの気持ちや心境の変化を持ち帰ってもらうイメージです. (これは確か卒業ゼミで先生が仰っていた表現だった記憶がありますが, うろ覚えです.)

狙いとしては, 例えば数学のイベントであれば

  • 数学の理解レベルはどんな人を対象とするのか
  • 数学とどういう付き合い方をしている人を対象とするのか
  • どういう雰囲気の数学イベントを求めている人を対象とするのか
  • 終わったときにどんな感想を持って欲しいのか
  • 「数学する仲間と知り合えて良かった」なのか
  • 「知識が増えて嬉しい」なのか
  • 「全然分からなかったけどそれが刺激になった」なのか

のように考えられるパターンはけっこう多いです. そしてこの中から運営の方々のそれぞれの想いに近いものを拾い, それぞれの想いを伝え合い (ときにはぶつけ合って) 運営としての「狙い」を固めていきます.

なぜ必ずこれを最初にやらないといけないかと言うと,

  • 狙いが先に決まっていないと, イベントで実際にやることを決めるための基準が定まっていないために, 何をやるかの判断がブレる
  • 当日, 臨機応変な対応が求められる場面でちぐはぐな対応になってしまう
  • 事後の振り返りで, 何を良かったと評価し, 何を反省すればいいかがあやふやになる

など何のためのイベントか分からなくなり, 参加者も運営も幸せになりません.

逆の言い方をすると, 狙いを最初に定め運営で共有しておくことで,

  • イベントの内容を決める基準が固定されているので議論しやすくなる
  • 当日の突然のアクシデントにも運営が連携して対処でき, 参加者が感じる違和感も少なく済む
  • 基準に照らして振り返りをするため, 良かったところや悪かったところを客観的に評価でき, 今後のイベント運営に活かせられる

といういいことがあるということです.

また, この段階では具体的にやることには踏み込まず, 想いや気持ちのようなふわふわしているもので狙いを表現します. というのはその狙いを達成する手段というのは無数にあり, さらに会場の物理的な制約なども含めると検討するにはパターンが多過ぎるからです. まずは指針となるものを先に決めるのが大事です.

手段の組み立て

では狙いが設定されたということで, 具体的にどんな活動をするかという「手段」の部分について考えていきましょう. ここでは狙いよりも具体的かつ技術的なことについて書いていきます.

前提として, イベント当日には参加者と運営が一堂に会しているとします. 加えて参加者の中には初対面どうしの人もいる, ということにしておきましょう. その状態から全体を「1つの集団」にしていくことを目指します. (もし既に全員が知り合いだった場合でも, ここで説明する流れをアレンジして, お互いの知らなかった側面を見付けられるようなイベントにしてもいいかもしれません.)

導入

初対面の人どうしがいるのでまずはそこにある壁をどうにかしていきます.

参加者にいきなり隣りにいる初対面の人と話せとか, 前に出て長時間スピーチをしろとかはハードルが高過ぎるので, まずは集団に埋没したままできる簡単なことをしてもらいます. 例えば, 進行役vs.参加者でじゃんけんをして最後まで勝ち残った人が優勝というゲームとか, 順々に簡単な質問に答えてもらうとか (Yes/Noで答えられるものや「ごきげんよう」のサイコロトークみたいなイメージ) から始めます. とにかく参加者に声を出したり身体を動かしたりしてもらうのが大事です. これをすることで参加者の意識を「離れて見てる人」から「このイベントの一部」へ変えます.

この段階では各参加者と進行役が1対1でつながっている状態が作れれば十分です. 参加者からは「私は今この人の話を聞けばいいのか」と思ってもらい, 進行役からは「今私はこの人達に話し掛けているんだ」という雰囲気が出ていれば成功です.

ここで気を付ける必要があるは, 既に知り合いである参加者どうしがいるパターンです. 一見イベントの雰囲気にプラスなように思えますが, 意外と雰囲気作りの障害になることがあります. 知ってる人どうしで固まってしまい, (本人たちにはその意識は無いものの) それ以外の人達に疎外感を与えることも起き得るからです. そのため参加者に知り合いどうしがいることには一切触れず, 全員に平等に話し掛けることが進行役にとって大事なことです.

関係の移行

各参加者と進行役の間の関係が築けたところで, 段々とそれを参加者どうしの関係へ移行していきます.

運営は導入の部分で参加者がどんな人なのかを少しは知っているはずです. そこで参加者と参加者の間に入って同じ話題を振って会話するように促したり, 両者の情報交換の仲立ちをします. 具体的にやるならグループディスカッションやチーム対抗の競技などになります. その際, 各グループに運営が付きコミュニケーションを促すことになると思いますが, メンバーの年齢や個々人の性格によって状況は様々ですので臨機応変にコミュ力を振り絞って頑張りましょう(笑)

この時点で運営が参加者を観察するポイントとしては

  • 参加者ごとの発言回数, 特に極端に発言回数が少ない参加者がいないか
  • 参加者どうしの発言回数

です. そして発言回数が少ない人が発言しやすい状況を作ったり, あまり話していない参加者どうしの間に立って会話をしたりして, 参加者どうしの関係に濃淡を作らないようにします.

ここまで書いた関係の移行のやり方は勉強会の発表などには当て嵌まりづらいですが, 役割としては質疑応答の時間が相当すると思います. 受けた質問を発表者が聴衆全員に対して復唱することで質問者のことを皆に知ってもらうことができます. 実際に会話はしないものの, 同じ聴衆にいる人に目が向くことで参加者どうしの関係ができていくはずです.

集団の完成

関係の移行を色々な組み合わせや色々なサイズの集団で行っていき, 参加者と運営の全員がお互いのことを知り, 全体が1つの集団になればイベント自体は完了です. 運営の手助け無しに各所で会話が自然発生するような雰囲気になっていると思います. 勉強会の発表の例で言うと, 発表が終わった瞬間に聴衆どうしで自然と感想を言い合ったり, 分からなかったところを質問したりしていれば大成功です. ここまで到達できれば, もう運営がやるべきことはあまりありません. 運営も参加者としてイベントを楽しみましょう.

あまり頑張らなくてもこういった良い雰囲気になってるかもしれませんが, それは運営が参加者に助けられていただけですので, あくまで運営が狙いを定めてイベントを進めることが大事です.

振り返り

さて無事イベントも終わって, ここまでの準備を思い出しているところです. このときだいたいの人はやや興奮ぎみにイベントの成功を喜んでいるでしょう. 苦労して準備したことが報われた気持ちになっているでしょう. これはごく普通なことですし, それだけ頑張ったのだから存分にそのいい気分にひたりましょう.

イベントの振り返りを行うのはその熱狂から醒めてからです. イベント終了直後の高揚した状態ではポジティブな評価ばかり出てくるでしょう. ネガティブな評価が無ければ振り返りとして片手落ちです.

どんなイベントにも

  • 狙いどおり上手く行ったところ
  • 狙いは良かったが失敗したところ
  • 対処できた想定外なこと
  • 対処できなかった想定外なこと
  • 予想外に上手く行ってしまったこと
  • そもそも狙いが良くなかったと感じた瞬間

があると思います. それらが元々の狙いに照らして良かったことなのか悪かったことなのかを評価しましょう. 別に失敗したことは問題ではありません. それを次の改善につなげられないことが問題なのです. 誰かを責めるでもなく, 責任逃れをするでもなく振り返りの話し合いができると良いと思います. そして次のイベントでこの振り返りを活かしていきましょう!!

いくつか補足

ここまででほとんどの内容について書き終わりました. 最後に「私がどういうイベント運営が良いと考えているのか」をはっきりさせるため, いくつか思うところを書き出してみます.

参加者を想定しないと何がマズいのでしょうか? それは, つまらなそうにしていた参加者がいたり, イベント後に不満が出たときに「あの人はこのイベントが対象としていなかったから仕方無い」という言い訳が簡単にできてしまうことです. 本当に想定外の人だったのであれば

  • 今後そういう人も対象にするかどうか
  • 広報でイベントの狙いが上手く伝えられていたか

を考えるべきです.

イベントの狙いを定めておくと運営以外にもよい影響があります. (振り返りの内容を公開する前提を置きますが) 振り返りの内容を知ることで, 先行事例としてどういうイベントをやるとどんな効果があるのかを他の人も知ることができます. その人が別のイベントを開いたとすると, 元の運営は2つのイベントに対して良いことをしたことになります.

狙いの方向性が一致しない場合はどうしたらいいでしょうか? その場合は諦めましょう. それぞれの信念の不一致ですので距離を置いて棲み分けましょう. そしてそれぞれ別のイベントを開く方が平和だと思います.

では手段の方向性が一致しない場合は? 手段の話まで進んでいるなら狙いの方向性では一致しているはずです. その合意した狙いを基準にして手段の善し悪しを評価しましょう. 基準が決まっている議論であればそこまで荒れないはずです.

この記事を書いていて思い出したこと.「キャンプが参加者にどう影響したのかは, 次にキャンプに来たときに分かる」とYMCAのスタッフから言われたことがあります. たかだか数日の時間ですぐに変わるわけではなく, そこで得た何かの影響が少しずつ現れてきて, 次に会ったときに目に見える変化になっている. という意味だと思っています.

私は数学茶屋というイベントで運営だったのですが, 実はここに書いたことを考えながらイベントの準備と進行をしていました. ここまで観察されていることを気持ち悪く思うかもしれませんが, イベントを良いものにするためだったので, ご勘弁ください.

そして数学茶屋で一緒に運営をやった方々は, イベントの組み立て方への私の強いこだわりを知ってるんじゃないかと思います. その裏にはこんなことがあったんだよ, というネタばらしの記事でした.

めっちゃ長くなってしまいましたが, ここまで読んでくださってありがとうございました.

√2の話の本歌取り 〜 プログラマのための数学勉強会第6回より

発端

第6回 プログラマのための数学勉強会 (とぎゃったは 『第6回 プログラマのための数学勉強会』のまとめ #maths4pg) という楽しそうな会が行われていました. その中のLT発表者が

ということをつぶやいていたので,「じゃあ自分なりの√2が導入できることのすごさを説明したい」と思い立って, この記事を書いています. 決して勉強会に参加できなくて羨しかったわけではありません!!

@taketo1024さんの発表資料はこちらです. 面白い内容ですので, ぜひ一度目を通しておいてください.

有理数しか知らない人に√2を説明する

LTの本歌取りということで, いったん@taketo1024さんの意図は敢えて見ないことにして, 自分が√2を説明するとしたらどうなるかを書いていこうと思います.

まず説明する相手は「数と言えば有理数で全てだ」と信じている人 (名前はQさん) とします. 現代ではそういう考えは少数派だと思いますが, ある時代では「数と言えば有理数」というのが常識でした. まぁ今回は「√2という有理数でない数もあるんだ」と主張しても, 相手を怒らせて殺されるようなことは無いとします. 詳しくは「ピタゴラス教団とヒッパソス」の話を調べてみてください.

私「ひとまず

root2

となる数があったとしましょう. 定義はこの式だけで計算は有理数と同じようにします. これの名前を√2としましょう.」

Qさん「√2なんて無いよ. ほら√2が数 (有理数) じゃないことが証明できるよ.」

私「まぁまぁ, すぐには信じられないかもしれないけど, √2で計算するとどうなるか眺めていってみようよ. 面白いことが見られるよ!」

私「じゃあ, まず足し算は

addition

みたいな感じで, 引き算は

subtraction

みたいな感じです.」

Qさん「みたいな感じ, って適当だなぁ. ところでその3とxを並べたものは何ですか?」

私「あぁ, これは3とxを掛け算したものです. もうちょっと複雑な掛け算のパターンだと

multiplication

みたいになります. この計算で初めて

root2

ってルールを使ってます.」

Qさん「うーん, ここまではまぁ分かるけど割り算は無理じゃないですか?」

私「実はなんと上手くできるんですよ. 例えば,

division

みたいに計算できます. これで加減乗除の全てが揃いました. これだけできれば数と認めてもいいでしょう?」

Qさん「むむむ. でも具体的にどんな数なのか全く分かってないんじゃ?」

私「graphのグラフとx軸が交わるところが√2です.」

Qさん「それじゃ, 該当する場所が2箇所ありませんか?」

私「ぐっ, そ, その2つはroot2からだけでは区別が付かないので, 正の方を√2, 負の方を-√2とします. 具体的な値の計算には, 二分法, ニュートン法, 連分数展開などがあります.」

Qさん「理論的には?」

私「さっきまで話していた方法は代数拡大を使うもので@taketo1024さんのLTはこれを使ってます. 他にはデデキント切断もあります.」

LTの資料だけでは詳しい部分が分からないかもしれないので, @taketo1024さんのこちらのシリーズを読んでください.

  1. 数とは何か?
  2. 群・環・体の定義
  3. 有理数を作ってみよう
  4. 時計の世界の「環」
  5. 小さな「体」を作ろう
  6. 多項式は整数によく似てる
  7. 代数拡大で数を作ろう!

京大特色入試, コインの問題を解く (その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は突然の死ジェネレータを使って作成しました.