第464回 シーズン47 エピソード4

思いがけない順序（後編） ただいま無料

好評発売中！ 『AIと生きる／対話から始まる成長の物語』

僕の部屋

トーナメント

僕「だから、 第3位決定戦でBとCのどちらが勝つかで新たにわかることは違うんだ」

• Bが勝ったなら、C→Bと第1試合のB→AからC→Aがわかる。
  これは新たにわかること。
• Cが勝ったなら、B→Cと第2試合のC→DからB→Dがわかる。
  でもこれは、第1試合のB→Aと決勝戦のA→Dからすでにわかっていたこと。

ユーリ「ぐえ。ほんとだ」

僕「だから、ユーリが作ってくれた総当たりの表でも、 第3位決定戦の後でハテナ（？）が減る場合と減らない場合がある」

第3位決定戦で総当たり表はどうなった？

ユーリ「ちょっと待って。 もともとB→AとA→Dから、B→Dはわかってた。 てことは、 第3位決定戦でBが勝った場合、 C→BとB→AからC→Aがわかる。 だったら、総当たり表は全部うまる！」

僕「確かにそうだね。 でも……」

ユーリ「でも、第3位決定戦でCが勝った場合、 どーしてもハテナが残っちゃう！　ぐぬぬ」

僕「ハテナが残るの、ユーリは嫌なんだね」

ユーリ「別にそーゆーんじゃないけど、 気になるじゃん」

僕「でも、この総当たり表は便利だよ。 消したいハテナマークを見れば、誰と誰を戦わせればいいかすぐにわかるからね」

ユーリ「おっ、たーしーかーに！」

僕「AとCのどちらが強いか決まってないから、そこにハテナがついている。 《決まってない》というのは、直接勝負していないし、 推移律からも決まらないという意味だよ」

ユーリ「そんなの、いまさら言わなくてもわかってるって」

僕「だから、総当たり表は便利」

ユーリ「んー、でもね、総当たり表を見ても 順位はすぐにはわからないよね？」

僕「なるほど。それはそうだね。たとえばこれを見ても順位はわかりにくい。 それは確かにそう」

ユーリ「……あっ、でもDが最強なのはすぐわかる！ だってDは縦にマルが並んでるもん。全員に勝つ！」

僕「鋭い！」

ユーリ「そして、Cが最弱。だってCは縦にバツが並んでる……あれ？　マルがひとつある。 あ、自分自身だ」

僕「そうだね。反射律を表すつもりでA→A, B→B, C→C, D→Dを入れたけど、 総当たり表が読みにくくなった。じゃあテン（・）で消しておこう。 そうすると、Cが最弱なのが、縦にバツが並ぶことで見てとれる」

ユーリ「全員に負ける……」

僕「……」

ユーリ「お兄ちゃん、何考えてんの？」

僕「トーナメント図に、さっき矢印を描いてたよね」

ユーリ「こーゆーの？」

僕「そう。この二つの図はそっくりだけど、 状況はずいぶん違う」

ユーリ「Cが勝ったときはハテナが残る」

僕「この二つの図で、二つに分かれているDをまとめて、矢印を少し整理するとこうなる」

ユーリ「そっくり」

僕「このままだとそっくりだ。 そこで、Bが勝った左の図で、 推移律からわかる矢印を消してしまう。 つまりC→Dの矢印」

ユーリ「ほーん……で？」

僕「左の図はC→B→A→Dと一本道になる。 でも右の図はBからAとCの二つに分岐して、AとCからDに合流する。 この二つはもうそっくりじゃない。明らかに違うよね！」

ユーリ「ほーほーほー！　確かに違う！」

僕「第3位決定戦でBが勝った左では、一本道になった。 つまりそれは第1位のD、第2位のA、第3位のB、そして第4位のCまで全員の順位が決まったことになる」

ユーリ「……」

僕「でも、第3位決定戦でCが勝った右では、一本道になってない。 最強がDで、最弱がBだと決まる。 でも、AとCは直接対決していないし、推移律からもどちらが強いかは決まらない」

ユーリ「ダウト！」

僕「何がダウト？」

ユーリ「んにゃ、ダウトじゃない？」

僕「どっちだよ」

ユーリ「だって、 第3位決定戦したのに順位が決まってないっておかしくね？　第3位決定戦でCが勝ったら、 第3位はCじゃないの？」

僕「トーナメントではこういう状況が起きてしまう」

ユーリ「あっれー……わかんなくなった！　決勝戦でDが勝ってAが負けたからAが第2位に決まる……と思ったけど、 本当には順位が決まらないことがあるってこと？」

僕「トーナメントは勝ち抜き戦で、 一度負けた人は敗退して、最終勝者を決める方法ということなんだろうね」

ユーリ「やっぱり、ダウト！」

僕「何がダウト？」

ユーリ「最終勝者を決める方法なら、Aが第2位になるのが納得できなーい！　だって、 AとCが戦ったらどっちが勝ってもおかしくないわけっしょ？」

二つのトーナメント

僕「ユーリの疑問はこうだよね」

ユーリ「えーと？　……あー、そだね。そーそー」

僕「もちろん、『それがトーナメントだから』という説明になっちゃうんだけど、 気付いたことはある」

ユーリ「お聞きしませう。語りませ」

僕「謎の古語やめい。 僕が思ったのは、 『トーナメントは優勝者を決めているだけ』 ということ」

ユーリ「優勝者じゃなくて第2位の話をしてんですけどー？」

僕「まあまあ。トーナメントの決勝戦というのは、 二つのトーナメントの優勝者同士が戦ってるんだよ」

ユーリ「意味わからん」

僕「図を見ればすぐにわかるよ」

ユーリ「なーるほどね！　ユーリ、理解した！　左のトーナメントと右のトーナメントがあって、 その優勝者同士が戦うのが決勝戦ってことだね？」

僕「そういうこと。左右に一段階小さなトーナメントがあって、その優勝者が戦う。 そう考えれば、さっきの《ユーリの疑問》にちょっとだけ答えられるなと思った。 つまり、最後の決勝戦に敗れた第2位は、一段階小さなトーナメントの優勝者なんだ！」

ユーリ「……」

僕「どう？　もちろんこれが正解ということじゃなくて、 ちょっと納得できる理由になるんじゃない？」

ユーリ「まーね。でも、ユーリ、気付いちゃった」

僕「お？」

ユーリ「最初にどっちの小さなトーナメントに参加するかがすっごく大事ってこと！」

僕「確かに。それは確かにそう。二つに分かれた小さなトーナメントのうち、 片方に強豪ばかりが集まっていたら、公平な試合とはいいにくい」

ユーリ「うんうん。あれ……待って、お兄ちゃん。 小さなトーナメントの下もずっとだ！」

僕「？」

ユーリ「4人のトーナメントだから、二つの小さなトーナメントだけど、 もしも8人のトーナメントなら、もっと増えるよね？」

僕「ユーリの言う通りだね。トーナメントは再帰的（さいきてき）な構造になってるからだ」

ユーリ「さいきてき」

僕「構造が、より小さな同じ構造でできているということ」

ユーリ「さいきてき……」

僕「構造が再帰的だし、戦い方もそう。 どのレベルでも、より小さなトーナメントの優勝者同士が戦っている」

ユーリ「きらりーん☆　試合開始のとき、参加者全員が優勝者？」

僕「確かに！　その通りだね。 参加者全員が、いわば0試合目の優勝者ということ」

ユーリ「あはは」

ハッセ図

僕「ところでさっきの図に戻るんだけど……」

ユーリ「さっきの図って？」

僕「これ」

ユーリ「明らかに違うやつ」

僕「これは、順序構造（じゅんじょこうぞう）を図として描くときに使う ハッセ図とほとんど同じだよ」

ユーリ「はっせず？」

僕「ハッセというのは数学者の名前。その人にちなんで付けたんだと思う。 ともかく、ハッセ図は順序を持っている構造を表すときによく使われる。 矢印を描くときもあるけど、僕が知っているハッセ図は描かないものが多いかな。 矢印を描く代わりに《強い》方を上に描く。 たとえばさっきの二つの図なら、こんな感じになる」

ユーリ「ふーん」

僕「反射律からわかる線は描かないというのは、 自分自身への線をわざわざ描かないということだね。 さっきの総当たり表でマルをテンに省略したのと同じだ。 もしも順序関係がある二つの要素を全部結んだら、 複雑になってしまう」

ユーリ「あはは……ごちゃごちゃじゃ〜」

僕「だから、こう描く」

ユーリ「ねえお兄ちゃん。 左の一本道はいいけど、右のも順序っていうの？　だってAとCの順位、決まってないよ」

僕「そうだね。左は一本道になっている。こういうのは特別に全順序（ぜんじゅんじょ） という名前がついてる。どの二つを選んでもどちらが強いかわかる」

ユーリ「ぜんじゅんじょ」

僕「右は一本道じゃない。こういうのは全順序ではないけれど、 順序ではある。半順序（はんじゅんじょ）ともいう」

ユーリ「はんじゅんじょ？　わかんなくなった！」

僕「ややこしいよね。僕はこう覚えている」

• 順序という関係は、反射律・反対称律・推移律を満たしている関係のこと。
• 半順序という関係は、順序とまったく同じ。
• 全順序という関係は、どの二つも比較可能な順序関係のこと。

ユーリ「右だとAとCが比較できないから、全順序じゃない。でも順序」

僕「そういうこと」

ユーリ「……お兄ちゃん。じゃんけんって順序じゃないよね？」

僕「その通り。じゃんけんのグー、チョキ、パーの《強さ》は順序じゃない」

ユーリ「さいくりっく〜だから推移律が成り立たない〜（第462回参照）」

僕「そういうこと」

ユーリ「でも、ハッセ図で描けちゃうよ。ほら」

僕「これはハッセ図じゃないよ。グーより強いパーが上に来るのはいいけど、 パーより強いチョキが下に来てしまっているからね」

ユーリ「あっ、そっかー。上下のシバリがあるのかー。サイクリックになれないじゃん！」

僕「だから順序を表すのにいいんだよ」

ユーリ「ぐぬぬ」