この記事はQiita 数学 Advent Calendar 2015の2日目の記事です。（後付け）
以下で画像として貼り付けている「ドナルドけんてい」を見ていて、「こたえ」は無くても分かるのではないか？という仮説を立てたので、これを検証します。
具体的には、自分が「ドナルドけんてい」を作る人の立場になったとすると、
・間違えた場合、回り道をする必要があるか、ゴールのグレードが下がるか、いずれかのペナルティを科す。
ということを自然に思いつきます。これを、数学の行列を使って検証する方法について、具体的に説明します。理論的な話も簡単に書いてありますが、Rのソースを読むと、かなり簡単なことしかやっていなさそう、ということがなんとなく伝わると思います。行列はもはや必須の道具ともいえる状況になりつつありますが、勉強するモチベーションとして、どうぞ。
ドナルドけんていとは
この画像にインスパイアされました。
・ドナルドけんてい$D$とは、ループと始点・終点が同じ矢を持たない(有限)有向グラフで、シンク(＝その点から出る矢が存在しないような点)$e$に対して得点$S(e)$が決まっており、ただ一つのソース（＝その点に向かって入る矢が存在しないような点）$e_0$を持つもののことを言う。
※得点$S$は、$D$の$e$から全順序集合への写像ですが、シンク$e$たちに順序が定まっていると思うこともできます。図の場合、上級$>$中級$>$初級$>$もういちど、チャレンジ！です。
正答の逆算
やりたいのは、冒頭で述べた通り正答の逆算で、これは、特別な数学の訓練を積んでいる人でなくても分かることだと思います。
ここでやろうとしている正答の逆算は、一般的なパズル誌に普通に載せられるレベル（ナンバープレイスやイラストロジックなどと同レベル）で、いわゆる数学に興味のない方でも解こうと思えば簡単に解けるレベルと思います。
しかし、正答の逆算を「きちんと」説明するため、適当な言葉を矢継ぎ早に定義していきます。
言葉の定義
・ドナルドけんてい$D$上の経路$P$とは、矢の列$p_1,...,p_n$であって、任意の$1\leq i<n$に対して$p_i$の終点＝$p_{i+1}$の始点が成り立つもののことをいう。
・経路$P$が点$e$を含むとは、ある$p_i$の始点または終点が$e$に一致することをいう。
・ドナルドけんてい$D$上の極大経路$P$とは、$D$上の経路であって、$P$を連続真部分列として含むような$D$上の経路が存在しないもののことをいう。$P$が極大経路であることと、$P$がソースからシンクへの経路であることと同義である。（これはある程度一般のグラフについて成り立つ。）
・極大経路$P$の最後の矢の終点を$e_P$とするとき、得点$S(P)$を、$S(P)=S(e_P)$で定める。
・各点$e$における最高得点を、$P$が$e$を含むようなすべての極大経路を動くものとして、$\sup_{P}(S(P))$によって定める。
・ドナルドけんてい$D$上の点$e$における正答とは、$e$を始点とする矢$a$であって、次の条件を満たすもののことをいう。
★$S(P)=S(e)$かつ$e$を含むような$P$について、$P$がこれらの経路の中で長さが最小の場合、$a$を含む。
一般には、$S(P)=S(e)$かつ$P$が$e$を含むような経路について、長さが最小となる経路が複数存在する可能性があるので、そのような場合は各点$e$における正答は一意には決まりません。ただし、画像によって与えられたドナルドけんていについては、$S(e)$に対して正答が一意に決まります。（もちろん自明ではありません。）
実際に逆算してみる
上の定義に従って、正答を計算する方法を考えます。
もちろん、「力づく」でも計算できて、かつ「力づく」で計算する方がたぶん早いと思うのですが、ここでは行列を使って解く方法を考えます。
実は、経路を関数合成と同一視して考えれば簡単にわかるのですが、グラフの隣接行列を$A$とするとき、$A^n$は同じ台集合に対して長さ$n$の経路を矢と思い直した有向グラフの隣接行列に対応します。
これを利用すると、$a$を含まない経路というのは、$a$にあたる箇所を0としても生き残るような$A^n$の成分に対応します。
ここで、$A$を作るときにソースを先頭に、シンクを最後の方に固めておくと、1列目の「最後の方」の成分が、ソースからシンクへの経路、つまり極大経路に対応する成分となります。
したがって、$A^n - (A-a)^n$を計算したとき、1列目の「最後の方」に差が出た場合、$n$は$a$を含む極大経路の長さを意味していて、「最後の方」の具体的にどこに出てきたかを見ることで、その極大経路の得点を計算できます。
今のドナルドけんていの場合、シンク以外の各点は必ず2つの矢をもつので、$a_1,a_2$のそれぞれについて
$A^n - (A-a_1)^n, A^n - (A-a_2)^n$を計算して、極大経路の長さと得点を求めたとき、より高い得点のもの、得点が同じ場合はより長さが短いもの、が正答ということになります。
これを、敢えてRで書いてみます。
以下、特に説明していませんが、A～Lを1,...,12、もういちど～上級を13,14,15,16とし、jからiへの矢が存在するとき、A[i,j]=1としています。
A <- matrix(nrow = 16, ncol = 16, 0)
A[2,1] <- A[5,1] <- A[3,2] <- A[6,2] <- A[4,3] <- A[8,3] <- A[14,4] <- A[8,4] <-
A[10,5] <- A[9,5] <- A[11,6] <- A[10,6] <- A[3,7] <- A[8,7] <- A[14,8] <- A[15,8] <-
A[10,9] <- A[13,9] <- A[7,10] <- A[13,10] <- A[12,11] <- A[13,11] <- A[16,12] <- A[13,12] <- 1
GetMatrix <- function(i,j){
B <- A
B[i,j] <- 0
C <- B
D <- A
R <- A
for(i in 1:16){
E <- D - C
R[,i] <- E[,1]
C <- C %*% B
D <- D %*% A
}
R
}
GetTrueAnswer <- function(L, R){
M <- L-R
for(i in 16 : 13){
for(j in 1:16){
if(M[i,j] > 0){
return("1")
} else if(M[i,j] < 0){
return("2")
}
}
}
}
# 以下のような処理を繰り返す
R1<-GetMatrix(2,1)
R2<-GetMatrix(5,1)
GetTrueAnswer(R1,R2)
考察
自分がドナルドけんていを作る人の立場になったとすると、
・間違えた場合、回り道をする必要があるか、ゴールのグレードが下がるか、いずれかのペナルティを科す。
ということを自然に思いつきます。この意味でのペナルティが徹底されているかどうか、ということを検証する方法が、ここで定義している「逆算」にあたります。
果たして結果は…。
なんと、Gの問題が、正解は①となっていますが、①のルートの方が明らかに遠回りになります。。。仮定は正しくありませんでした。これは問題ですね。でも、Gの問題の内容的には黄色の方が正しそうなので、Gの問題の①と②の番号をつけ間違えたと解釈するのが適切な気がします。
また、それ以外にも間違えてもゴールのグレードが下がらない問題があったり、一問間違えただけで最下級の「もういちど、チャレンジ！」に飛ばされてしまうあたり、ちょっと結果に納得できていません。
具体的には、Eの「どんなかみがた？」という質問は、隣に立っているドナルドを見れば分かるにも関わらず、これを間違えても中級になれるあたり、特に納得できていません。一方で、Lの靴の大きさを間違えると即死（？）するあたり、上級に対する厳しさを感じます。本当にハンバーガー４つ分なのか、ドナルド人形をチェックしてやろうかしら。。。
おまけ
パズル好きな人がすぐに思いつきそうなことでも、きちんと話をしようとすると、実は色々な言葉を丁寧に定義したりする必要があります。私の言葉の使い方にも勿論問題があるのですが、その辺りのさじ加減は、いつも非常に難しいと思います。
なんていうか、この記事であれば、ナンセンスかつ面白い部分を共有する対象をなるべく多くとりたいと思うのですが、難しいですね。