書き置き

たまに書く。無理しない。

2001年度 京都大学工学部情報学科後期試験口述・解答例

2007年度から後期試験が廃止されるため、需要もあまりなさそうですがとりあえず残しておきます。

「問題1」
局面<2, 1, 0>の次の局面は<2, 0, 0>と<0, 0, 0>のみ。―(1)<0, 0, 0>は良形であり、―(2)<2, 0, 0>は、<2, 0, 0>→<1, 0, 0>→<0, 0, 0>としか変形できないため、<1, 0, 0>は悪形であり、<2, 0, 0)は良形である。―(3)
(1),(2),(3)より、局面<2, 1, 0>は悪形。―(4)

局面<3, 1, 0>の次の局面は<2, 1, 0>と<3, 0, 0>のみ。―(5)
局面<3, 0, 0>の次の局面は<2, 0, 0>のみであり、
(3)より局面<2, 0, 0>は良形であるので、局面<3, 0, 0>は悪形。―(6)
(4),(5),(6)より、局面<3, 1, 0>は良形。

「問題2」
局面p=の次の局面をq=とおくと、

問題文(1)のくずし方において、(k1+k2+k3)-(m1+m2+m3)=1
問題文(2)のくずし方において、(k1+k2+k3)-(m1+m2+m3)=2ki-1(但しi=1,2,3)

従って、(k1+k2+k3)と(m1+m2+m3)の偶奇は常に異なる。―(7)

ここで、局面pが良形であるための必要十分条件を、
「(k1+k2+k3)が偶数」と推測する。―(*)

(I)p=<0, 0, 0>のとき、
k1+k2+k3=0、つまり偶数となり、また、局面pは良形であるから(*)は正しい。

(II)p≠<0, 0, 0>のとき、
pの次の局面全てについて(*)が正しいと仮定すると、
(k1+k2+k3)が偶数
⇔(m1+m2+m3)は奇数(∵(7))
⇔pの次の局面は全て悪形(仮定より)
⇔pは良形
∴(*)は正しい。

(I),(II)より帰納法より(*)は正しい。
つまり、変形3山くずしの局面p=が良形であるための
必要十分条件は、(k1+k2+k3)が偶数。