計算機実験(後編)
群城は Risa/Asir を起動した。
「よし、嘘つき問題を、計算していこう!」
ここは、大学の 24-Hour Study Room.
24時間いつでも空いていて、学生ならだれでも利用できる自習室だ。
Summer Break にも関わらず、群城の他にも、少なくない数の学生が勉強している。
留学始めは、アメリカの学生は勉強熱心だなあと感心していたが、大学生活を送るにつれ、課題がかなり多いからなのでは?と思うようになった。
「えーと、まずは簡単な問題からやってみるか。」
群城は、腕まくりをして気合いを入れる。
カバンからノートを取り出し、書き込む。
***
問題. この中で嘘をついているのは、誰か?
A. 「Bは嘘をついている」
B. 「Cは嘘をついてない」
C. 「AとBのどちらかは嘘をついてない」
***
「A, B, C の真偽をそれぞれ、x, y, z で対応させて、真実を0、嘘を1して、これを、連立方程式で置き直すと、」
x - y + 1 = 0
y - z = 0
z - xy = 0
「ってなるよな。だから、Asir で、」
nd_gr([x-y+1,y-z,z-x*y],[x,y,z],2,2)
「を計算をすればいーか。さあ、本当に計算できるかな。」
群城は、Enter を押した。
[z^2,y+z,x+z+1]
「おお!出来てる!やるなお前!」
群城は、パソコンを褒めるように、バシバシと叩く。
グレブナー基底を計算できる、無料の数式処理ソフトはないかと、調べていたところ、なんだ日本製のがあるじゃん!と、群城が数週間前にインストールしたのが、Risa/Asir である。
「なんだ意外とイケるんじゃないか?これ?」
実は、群城は、グレブナー基底の定義自体は、知っていたものの、実際に計算したことはあまりなかった。
「えーと、ってことは、答えは、」
A=嘘つき
B=正直
C=正直
「ってことだな、よし!」
さっきの、Borgwardt 先生の2万字のグレブナー基底に、少しビビっていためか、実際に計算できたことに、群城は胸を撫で下ろした。
「どんどんいくぞ!」
***
問題. この中で嘘をついているのは、誰か?
A「Bは正しい」
B「CかDは正しい」
C「Dは嘘をついている」
D「嘘をついているのは1人だけだ」
***
最初の問題より、ちょっと難しいものを、群城は考えた。
「今度は、変数を、一つ足して、x, y, z, w で考えると、まず、」
A「Bは正しい」
「ってのは、」
x - y = 0
「と同値になる。そして、」
B「CかDは正しい」
「ってのは、えーと、z か w のどっちかが 0(真実)って、ことだから、」
y - zw = 0
「でいいんだな。次に、 Cの発言、」
C「Dは嘘をついている」
「は、1 + 1 = 0 で考えてるから、」
z + w + 1 = 0
「で、オッケーだろ!そんじゃあ、最後!」
D「嘘をついているのは1人だけだ」
「うーんと、これは…」
上の問題は、群城が考えたものだが、そもそも適当にネットでググって、適当に貼り合わせたものなので、適当に作られているかどうかは、適当な群城にはわからなかった。
というわけで、群城は、Dの発言に対応する式を考える。
「んー。」
『AまたはBまたはCまたはDが嘘ついている』
「だったら、」
w + (x + 1)(y + 1)(z + 1)(w + 1) = 0
「ってなって、簡単なんだけどなあ。でも、これだと、『少なくとも1人が嘘をついている』ことになって、『2人、3人、4人が嘘つき』でもよくて、『1人だけ嘘つき』には、当てはまらないんだよなあ。うーむ。」
人数を指定していることが、A, B, C の発言とは違うところだ。
人数の指定を、どうやって多項式で表現するか?
「しかも、『1人だけ』しか書いてないから、その嘘つきが A でも B でも誰でもいいわけだし。そもそも、D が嘘をついててもいいわけだし。」
「嘘つきは、いつも1人!」と決め台詞を言っている江D川くんが、嘘つきであってもいいのだ。
「ううう。」
10分くらい考えて、群城は、頭を抱えて、とうとうわからなくなってしまった。
「まさかここまでとはな・・・」
もはや自暴自棄になって、来葉峠で赤井さんが言いそうなセリフまでつぶやく。
「どうしたの?」
「うわあ!」
C.J. だ。
机に突っ伏して、うなっている群城を見かけて、声をかけたらしい。
「なんだ、C.J. か。」
「なんだ、とはなによ。」
「それより、助けてくれよ。中国人はみんな頭いいだろ?」
「あらなに?」
「この問題が分からないんだ。」
群城は、かくかくしかじかと、C.J. に問題を説明する。
C.J. はその説明を聞いて、すぐに、こう答えた。
「なるほどね。少なくとも、対称式なんじゃない?」
「対称式?」
「ほら、x + y + z + w とか、xyzw とか、x,y,z,w の変数を入れ替えても、同じに式になるやつ。」
「ああ、それか。」
「だって、『嘘つき一人だけ』って、誰が嘘ついてても、つまり、対応する変数を入れ替えても、式が変わらないってことでしょ?」
「そっか。変数を入れ替えて、違う式になっちゃったら、式の意味が変わっちゃうもんな。」
「そして、対称式って、みんな、基本対称式から作れるから、その辺の式をいじくってたら、出てくるんじゃない?」
(4変数の)基本対称式とは、
x + y + z + w,
xy + yz + zw + wx + yw + xz,
xyz + yzw + zwx + xyw,
xyzw
の4つの対称式のことで、最も簡単な対称式たちのことである。
対称式は、この4変数の多項式の足し算や掛け算で作れることが知られている。
例えば、
x^2 + y^2 + z^2 + w^2
は対称式であるが、(試しに、x と y を入れ替えても、y^2 + x^2 + z^2 + w^2 になって、元のと同じ式になっている )
x^2 + y^2 + z^2 + w^2 = (x + y + z + w)^2 - 2*(xy + yz + zw + wx + yw + xz)
と、基本対称式を使って、表すことができる。
「……なるほど……。さんきゅー C.J. !!」
「ヒントになってくれたらいいけど…。あ、そういえば、この前、部屋に行ったとき、私、やっぱりなにか邪魔しちゃってた?」
C.J. が問いかけたが、群城は、式を求めようと、自分の世界に入っていて、なにも聞こえていなかった。
「……それじゃあ、頑張ってね。」
C.J. はそんな群城の姿を見て、どこか嬉しく思い、Study Room を後にした。
「まずは、一つ目の基本対称式の意味から、考えてみるか。」
x + y + z + w = 0 …(1)
「これは、全員、正直なとき、0 + 0 + 0 + 0 = 0 だから、成り立つし、1 人だけ、嘘をついてたら、1 + 0 + 0 + 0 = 1 だから、成り立たない。2人だけ嘘は、1 + 1 + 0 + 0 = 1 + 1 = 0 だから、OK で、3 人だけ嘘は、1 + 1 + 1 + 0 = 1 だから。ダメ。全員嘘つきは、1 + 1 + 1 + 1 = 0 だからおk。つまり、」
x + y + z + w = 0 ⇔ 嘘をついている人数は、偶数
「が成り立つ。うーん。これは、使えそうにないかなあ。次を見てみるか。」
xy + yz + zw + wx + yw + xz = 0 …(2)
「えっと、次の基本対称式は、この式だな。嘘の人数で、xy + yz + zw + wx + yw + xz の値を確認してみると…」
嘘=0人 → 0 + 0 + 0 + 0 + 0 + 0 = 0、(2)は成り立つ。
嘘=1人 → x=1,y=z=w=0 とすれば、1*0 + 0*0 + 0*0 + 0*1 + 0*0 + 1*0 = 0 で、(2)は成り立つ。
嘘=2人 → x=y=1,z=w=0 とすれば、1*1 + 1*0 + 0*0 + 0*1 + 1*0 + 1*0 = 1 で、(2)は成り立たない。
嘘=3人 → x=y=z=1, w=0 とすれば、1*1 + 1*1 + 1*0 + 0*1 + 1*0 + 1*1 = 1 で、(2)は成り立たない。
嘘=4人 → x=y=z=w=1 とすれば、1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 = 0 で、(2)は成り立つ。
つまり、
xy + yz + zw + wx + yw + xz = 0 ⇔ 嘘つきは、0人か、1人か、4人
「うーん。1人は出てきたけど、0人と4人が邪魔だなあ。次のも見てみるか。」
xyz + yzw + zwx + xyw = 0…(3)
「大変だけど、これも一つずつ確認して…」
嘘=0人 → 0 + 0 + 0 + 0 = 0、(3)は成り立つ。
嘘=1人 → x=1,y=z=w=0 とすれば、1*0*0 + 0*0*0 + 0*0*1 + 1*0*0 = 1 で、(3)は成り立たない。
嘘=2人 → x=y=1,z=w=0 とすれば、1*1*0 + 1*0*0 + 0*0*1 + 1*1*0 = 0 で、(3)は成り立つ。
嘘=3人 → x=y=z=1, w=0 とすれば、1*1*1 + 1*1*0 + 1*0*1 + 1*1*0 = 1 で、(3)は成り立たない。
嘘=4人 → x=y=z=w=1 とすれば、1*1*1 + 1*1*1 + 1*1*1 + 1*1*1 = 0 で、(3)は成り立つ。
「つまり、」
xyz + yzw + zwx + xyw = 0 ⇔ 嘘つきは、0人か、2人か、4人
「最後の基本対称式は、」
xyzw = 0 …(4)
「だけど、これは、」
xyzw = 0 ⇔ 嘘つきは、0人か、1人か、2人か、3人
「であることは、自明だな。以上のことを整理すると、」
x + y + z + w = 0 ⇔ 嘘をついている人数は、偶数
xy + yz + zw + wx + yw + xz = 0 ⇔ 嘘つきは、0人か、1人か、4人
xyz + yzw + zwx + xyw = 0 ⇔ 嘘つきは、0人か、2人か、4人
xyzw = 0 ⇔ 嘘つきは、0人か、1人か、2人か、3人
「ってなった。ここから、どうやって、『1人だけ嘘つき』を作るか…」
言ってしまえば、これは、いかにして、これらの証拠から、犯人の対称式を求めるか、という推理である。
蝶ネクタイ型変声機も、腕時計型麻酔銃も、ターボエンジン付きスケートボードもないが、群城は今、立派な名探偵である。
口に、ピストルの形をした指を当て、じっと考える。
シュピピーーーーーーンン!!!!!!
群城の耳に閃光が走る。何かひらめいたようだ。
「ま、まさか!?」
x + y + z + w = 0 ⇔ 嘘をついている人数は、偶数
「の否定を考えると、0 の否定は、1だから、」
x + y + z + w = 1 ⇔ 嘘をついている人数は、奇数
「そして、2つ目の式、」
xy + yz + zw + wx + yw + xz = 0 ⇔ 嘘つきは、0人か、1人か、4人
「と合わせると、」
x + y + z + w = 1 かつ xy + yz + zw + wx + yw + xz = 0
⇔
嘘をついている人数は、奇数で、0人か、1人か、4人
⇔
嘘をついている人数は、1人
「そうか!2つの式を連立させればいいのか!あとは、それぞれ w = の式にすれば、」
D「嘘をついているのは1人だけだ」
⇔ w = x + y + z + w - 1 かつ w = xy + yz + zw + wx + yw + xz
「でいいんだ!!」
群城は、答えが出せて興奮して、思わず椅子から立ち上がる。
よしよしよしと、心の底から、嬉しさがこみ上げてくる。
「つまりは、嘘つき問題、」
***
問題. この中で嘘をついているのは、誰か?
A「Bは正しい」
B「CかDは正しい」
C「Dは嘘をついている」
D「嘘をついているのは1人だけだ」
***
「は、連立方程式、」
x - y = 0
y - zw = 0
z + w + 1 = 0
w - x + y + z + w - 1 = 0
w - xy + yz + zw + wx + yw + xz = 0
「に帰着できて、これが Asir で解ければ!」
群城は、ドキドキしながらも、入力ミスがないように、Asir に
nd_gr([x-y,y-z*w,z+w+1,w-x+y+z+w-1,w-x*y+y*z+z*w+w*x+y*w+x*z],[x,y,z,w],2,2);
と打ち込んだ。
「頼む、計算できてくれ!!」
手に汗を握りながら、群城は、Enter を押した。
[w,z+1,y,x]
「よっしゃああああ!!!!!!」
答えが出たようだ。
つまり、嘘つき問題の正解とは、
A=正直
B=正直
C=嘘つき
D=正直
ということが、グレブナー基底を計算することで、確かに分かったのだ。
嘘つき問題が、解けるということは、分かっていたが、
この問題が解けることは、実際に、計算をしてみなければ、わからないことだった。
郡城は、この結果に満足した。
…………と同時に、物足りなさを感じていた。
できるって、なんかつまらない。
確かに、出来たことは、嬉しかった。
しかし、出来ずに、考えて、考えて、考えて、考えてた時の方が、もっと楽しかった。
ざわ…ざわ…
群城の胸の中で、何かが、騒ぎ始めた。
もっと。もっと。もっと。
もっと、人物を、式を、増やしてみたらどうだろうか。
Borgwardt 先生のオフィスで見た、あの大量のグレブナー基底が見たい。
計算できなくなる限界が知りたい。
しかし、いちいち問題を作るのは、面倒臭い。
何か、いい方法はないか。
うーんと、群城は、考えあぐねて、次のような「規則性」のある嘘つき問題を思いついた。
***
問題. この中で嘘をついているのは、誰か?
X_1「X_2は嘘をついている」
X_2「X_3は嘘をついている」
X_3「X_4は嘘をついている」
…
X_(n-1)「X_nは嘘をついている」
X_n「私は嘘をついていない」
***
「これなら、どうかな。」
n人の人が、最後の人以外は、それぞれ「次の人は嘘をついている」と主張している、という問題だ。
「よし、これをそれぞれ、式で表すと、」
x1 + x2 + 1 = 0
x2 + x3 + 1 = 0
x3 + x4 + 1 = 0
…
x(n-1) + xn + 1 = 0
xn - xn = 0
「っていう感じになるな。試しに、n=5 で計算してみればー」
x1 + x2 + 1 = 0
x2 + x3 + 1 = 0
x3 + x4 + 1 = 0
x4 + x5 + 1 = 0
x5 - x5 = 0
「だから、Asir に、」
nd_gr([x1+x2+1,x2+x3+1,x3+x4+1,x4+x5+1,x5-x5],[x1,x2,x3,x4,x5],2,2);
「と打ち込んで、計算すると、」
[x4+x5+1,x3+x5,x2+x5+1,x1+x5]
「あれれーおかしいぞおーー?あ、そうか。この場合、x5=0 か x5=1 で場合分けができて、」
X_1=正直
X_2=嘘つき
X_3=正直
X_4=嘘つき
X_5=正直
と
X_1=嘘つき
X_2=正直
X_3=嘘つき
X_4=正直
X_5=嘘つき
「のどちらも、答えとして、あり得るってことか。たぶん、これって、n が他の値でも、同じ感じに、交互に正直、嘘つきってなると思うけど……」
群城は、ペンを鼻の上に挟んで、机の背もたれに、寄りかかる。
「打ち込むのが、めんどくさいんだよなあ。」
群城は、不精なところがあり、将来的には、人を顎で使って、お茶を持ってこさせることもあるかもしれない。
「あ、そうか、プログラム組めばいいのか。」
そう言って、群城は、Asir で簡単なプログラムを書いた。
def uso(N){
P=[];
V=[];
A=1;
for(I=1;I<=N;I++){
A=uc();
if(I>1){
P=cons(A+B+1,P);
}
V=cons(B,V);
B=A;
}
G=nd_gr(P,V,2,2);
return(G);
}
end$
Asirでは、C言語をベースとした、"Asir言語" でプログラムを書くことができる。
if文、for文など、基本的には、C言語と書き方は同じだが、(代入に使う)変数は大文字にしなければならないなど、独特の所作もある。
上のように、群城は、多項式に使う変数を生成するため、uc() という関数を使った。
そして、さっきのN人の場合の嘘つき問題のグレブナー基底を計算する uso(N)という関数を作った。
「よし!これで、Nを大きくして言って、どこまで計算できるかやってみるぞ!!」
まず、N=10を代入した。
uso(10);
[_0+_1+1,_0+_2,_0+_3+1,_0+_4,_0+_5+1,_0+_6,_0+_7+1,_0+_8,_0+_9+1]
が出てきた。
ここで、_0,...,_9 は、多項式の変数のことである。
「なんか見づらいけど、_0=0 とすれば、_1=1, _2=0, …てな感じに、正直、嘘つきが交互に出てくるし、確かに、計算できているな!もっと、大きくしてみよう!」
群城は、N=100を代入した。
uso(100);
[_0+_1+1,_0+_2,_0+_3+1,_0+_4,_0+_5+1,_0+_6,_0+_7+1,_0+_8,_0+_9+1,_0+_10,_0+_11+1,_0+_12,_0+_13+1,_0+_14,_0+_15+1,_0+_16,_0+_17+1,_0+_18,_0+_19+1,_0+_20,_0+_21+1,_0+_22,_0+_23+1,_0+_24,_0+_25+1,_0+_26,_0+_27+1,_0+_28,_0+_29+1,_0+_30,_0+_31+1,_0+_32,_0+_33+1,_0+_34,_0+_35+1,_0+_36,_0+_37+1,_0+_38,_0+_39+1,_0+_40,_0+_41+1,_0+_42,_0+_43+1,_0+_44,_0+_45+1,_0+_46,_0+_47+1,_0+_48,_0+_49+1,_0+_50,_0+_51+1,_0+_52,_0+_53+1,_0+_54,_0+_55+1,_0+_56,_0+_57+1,_0+_58,_0+_59+1,_0+_60,_0+_61+1,_0+_62,_0+_63+1,_0+_64,_0+_65+1,_0+_66,_0+_67+1,_0+_68,_0+_69+1,_0+_70,_0+_71+1,_0+_72,_0+_73+1,_0+_74,_0+_75+1,_0+_76,_0+_77+1,_0+_78,_0+_79+1,_0+_80,_0+_81+1,_0+_82,_0+_83+1,_0+_84,_0+_85+1,_0+_86,_0+_87+1,_0+_88,_0+_89+1,_0+_90,_0+_91+1,_0+_92,_0+_93+1,_0+_94,_0+_95+1,_0+_96,_0+_97+1,_0+_98,_0+_99+1]
_0,...,_99 が100個の変数として登場している。
「えーと……。今度も確かに、計算できてるな。よし、もっとでっかいの!」
群城は、N=1000を代入した。
[_0+_1+1,_0+_2,_0+_3+1,_0+_4,_0+_5+1,_0+_6,_0+_7+1,_0+_8,_0+_9+1,_0+_10,_0+_11+1,_0+_12,_0+_13+1,_0+_14,_0+_15+1,_0+_16,_0+_17+1,_0+_18,_0+_19+1,_0+_20,_0+_21+1,_0+_22,_0+_23+1,_0+_24,_0+_25+1,_0+_26,_0+_27+1,_0+_28,_0+_29+1,_0+_30,_0+_31+1,_0+_32,_0+_33+1,_0+_34,_0+_35+1,_0+_36,_0+_37+1,_0+_38,_0+_39+1,_0+_40,_0+_41+1,_0+_42,_0+_43+1,_0+_44,_0+_45+1,_0+_46,_0+_47+1,_0+_48,_0+_49+1,_0+_50,_0+_51+1,_0+_52,_0+_53+1,_0+_54,_0+_55+1,_0+_56,_0+_57+1,_0+_58,_0+_59+1,_0+_60,_0+_61+1,_0+_62,_0+_63+1,_0+_64,_0+_65+1,_0+_66,_0+_67+1,_0+_68,_0+_69+1,_0+_70,_0+_71+1,_0+_72,_0+_73+1,_0+_74,_0+_75+1,_0+_76,_0+_77+1,_0+_78,_0+_79+1,_0+_80,_0+_81+1,_0+_82,_0+_83+1,_0+_84,_0+_85+1,_0+_86,_0+_87+1,_0+_88,_0+_89+1,_0+_90,_0+_91+1,_0+_92,_0+_93+1,_0+_94,_0+_95+1,_0+_96,_0+_97+1,_0+_98,_0+_99+1,_0+_100,_0+_101+1,_0+_102,_0+_103+1,_0+_104,_0+_105+1,_0+_106,_0+_107+1,_0+_108,_0+_109+1,_0+_110,_0+_111+1,_0+_112,_0+_113+1,_0+_114,_0+_115+1,_0+_116,_0+_117+1,_0+_118,_0+_119+1,_0+_120,_0+_121+1,_0+_122,_0+_123+1,_0+_124,_0+_125+1,_0+_126,_0+_127+1,_0+_128,_0+_129+1,_0+_130,_0+_131+1,_0+_132,_0+_133+1,_0+_134,_0+_135+1,_0+_136,_0+_137+1,_0+_138,_0+_139+1,_0+_140,_0+_141+1,_0+_142,_0+_143+1,_0+_144,_0+_145+1,_0+_146,_0+_147+1,_0+_148,_0+_149+1,_0+_150,_0+_151+1,_0+_152,_0+_153+1,_0+_154,_0+_155+1,_0+_156,_0+_157+1,_0+_158,_0+_159+1,_0+_160,_0+_161+1,_0+_162,_0+_163+1,_0+_164,_0+_165+1,_0+_166,_0+_167+1,_0+_168,_0+_169+1,_0+_170,_0+_171+1,_0+_172,_0+_173+1,_0+_174,_0+_175+1,_0+_176,_0+_177+1,_0+_178,_0+_179+1,_0+_180,_0+_181+1,_0+_182,_0+_183+1,_0+_184,_0+_185+1,_0+_186,_0+_187+1,_0+_188,_0+_189+1,_0+_190,_0+_191+1,_0+_192,_0+_193+1,_0+_194,_0+_195+1,_0+_196,_0+_197+1,_0+_198,_0+_199+1,_0+_200,_0+_201+1,_0+_202,_0+_203+1,_0+_204,_0+_205+1,_0+_206,_0+_207+1,_0+_208,_0+_209+1,_0+_210,_0+_211+1,_0+_212,_0+_213+1,_0+_214,_0+_215+1,_0+_216,_0+_217+1,_0+_218,_0+_219+1,_0+_220,_0+_221+1,_0+_222,_0+_223+1,_0+_224,_0+_225+1,_0+_226,_0+_227+1,_0+_228,_0+_229+1,_0+_230,_0+_231+1,_0+_232,_0+_233+1,_0+_234,_0+_235+1,_0+_236,_0+_237+1,_0+_238,_0+_239+1,_0+_240,_0+_241+1,_0+_242,_0+_243+1,_0+_244,_0+_245+1,_0+_246,_0+_247+1,_0+_248,_0+_249+1,_0+_250,_0+_251+1,_0+_252,_0+_253+1,_0+_254,_0+_255+1,_0+_256,_0+_257+1,_0+_258,_0+_259+1,_0+_260,_0+_261+1,_0+_262,_0+_263+1,_0+_264,_0+_265+1,_0+_266,_0+_267+1,_0+_268,_0+_269+1,_0+_270,_0+_271+1,_0+_272,_0+_273+1,_0+_274,_0+_275+1,_0+_276,_0+_277+1,_0+_278,_0+_279+1,_0+_280,_0+_281+1,_0+_282,_0+_283+1,_0+_284,_0+_285+1,_0+_286,_0+_287+1,_0+_288,_0+_289+1,_0+_290,_0+_291+1,_0+_292,_0+_293+1,_0+_294,_0+_295+1,_0+_296,_0+_297+1,_0+_298,_0+_299+1,_0+_300,_0+_301+1,_0+_302,_0+_303+1,_0+_304,_0+_305+1,_0+_306,_0+_307+1,_0+_308,_0+_309+1,_0+_310,_0+_311+1,_0+_312,_0+_313+1,_0+_314,_0+_315+1,_0+_316,_0+_317+1,_0+_318,_0+_319+1,_0+_320,_0+_321+1,_0+_322,_0+_323+1,_0+_324,_0+_325+1,_0+_326,_0+_327+1,_0+_328,_0+_329+1,_0+_330,_0+_331+1,_0+_332,_0+_333+1,_0+_334,_0+_335+1,_0+_336,_0+_337+1,_0+_338,_0+_339+1,_0+_340,_0+_341+1,_0+_342,_0+_343+1,_0+_344,_0+_345+1,_0+_346,_0+_347+1,_0+_348,_0+_349+1,_0+_350,_0+_351+1,_0+_352,_0+_353+1,_0+_354,_0+_355+1,_0+_356,_0+_357+1,_0+_358,_0+_359+1,_0+_360,_0+_361+1,_0+_362,_0+_363+1,_0+_364,_0+_365+1,_0+_366,_0+_367+1,_0+_368,_0+_369+1,_0+_370,_0+_371+1,_0+_372,_0+_373+1,_0+_374,_0+_375+1,_0+_376,_0+_377+1,_0+_378,_0+_379+1,_0+_380,_0+_381+1,_0+_382,_0+_383+1,_0+_384,_0+_385+1,_0+_386,_0+_387+1,_0+_388,_0+_389+1,_0+_390,_0+_391+1,_0+_392,_0+_393+1,_0+_394,_0+_395+1,_0+_396,_0+_397+1,_0+_398,_0+_399+1,_0+_400,_0+_401+1,_0+_402,_0+_403+1,_0+_404,_0+_405+1,_0+_406,_0+_407+1,_0+_408,_0+_409+1,_0+_410,_0+_411+1,_0+_412,_0+_413+1,_0+_414,_0+_415+1,_0+_416,_0+_417+1,_0+_418,_0+_419+1,_0+_420,_0+_421+1,_0+_422,_0+_423+1,_0+_424,_0+_425+1,_0+_426,_0+_427+1,_0+_428,_0+_429+1,_0+_430,_0+_431+1,_0+_432,_0+_433+1,_0+_434,_0+_435+1,_0+_436,_0+_437+1,_0+_438,_0+_439+1,_0+_440,_0+_441+1,_0+_442,_0+_443+1,_0+_444,_0+_445+1,_0+_446,_0+_447+1,_0+_448,_0+_449+1,_0+_450,_0+_451+1,_0+_452,_0+_453+1,_0+_454,_0+_455+1,_0+_456,_0+_457+1,_0+_458,_0+_459+1,_0+_460,_0+_461+1,_0+_462,_0+_463+1,_0+_464,_0+_465+1,_0+_466,_0+_467+1,_0+_468,_0+_469+1,_0+_470,_0+_471+1,_0+_472,_0+_473+1,_0+_474,_0+_475+1,_0+_476,_0+_477+1,_0+_478,_0+_479+1,_0+_480,_0+_481+1,_0+_482,_0+_483+1,_0+_484,_0+_485+1,_0+_486,_0+_487+1,_0+_488,_0+_489+1,_0+_490,_0+_491+1,_0+_492,_0+_493+1,_0+_494,_0+_495+1,_0+_496,_0+_497+1,_0+_498,_0+_499+1,_0+_500,_0+_501+1,_0+_502,_0+_503+1,_0+_504,_0+_505+1,_0+_506,_0+_507+1,_0+_508,_0+_509+1,_0+_510,_0+_511+1,_0+_512,_0+_513+1,_0+_514,_0+_515+1,_0+_516,_0+_517+1,_0+_518,_0+_519+1,_0+_520,_0+_521+1,_0+_522,_0+_523+1,_0+_524,_0+_525+1,_0+_526,_0+_527+1,_0+_528,_0+_529+1,_0+_530,_0+_531+1,_0+_532,_0+_533+1,_0+_534,_0+_535+1,_0+_536,_0+_537+1,_0+_538,_0+_539+1,_0+_540,_0+_541+1,_0+_542,_0+_543+1,_0+_544,_0+_545+1,_0+_546,_0+_547+1,_0+_548,_0+_549+1,_0+_550,_0+_551+1,_0+_552,_0+_553+1,_0+_554,_0+_555+1,_0+_556,_0+_557+1,_0+_558,_0+_559+1,_0+_560,_0+_561+1,_0+_562,_0+_563+1,_0+_564,_0+_565+1,_0+_566,_0+_567+1,_0+_568,_0+_569+1,_0+_570,_0+_571+1,_0+_572,_0+_573+1,_0+_574,_0+_575+1,_0+_576,_0+_577+1,_0+_578,_0+_579+1,_0+_580,_0+_581+1,_0+_582,_0+_583+1,_0+_584,_0+_585+1,_0+_586,_0+_587+1,_0+_588,_0+_589+1,_0+_590,_0+_591+1,_0+_592,_0+_593+1,_0+_594,_0+_595+1,_0+_596,_0+_597+1,_0+_598,_0+_599+1,_0+_600,_0+_601+1,_0+_602,_0+_603+1,_0+_604,_0+_605+1,_0+_606,_0+_607+1,_0+_608,_0+_609+1,_0+_610,_0+_611+1,_0+_612,_0+_613+1,_0+_614,_0+_615+1,_0+_616,_0+_617+1,_0+_618,_0+_619+1,_0+_620,_0+_621+1,_0+_622,_0+_623+1,_0+_624,_0+_625+1,_0+_626,_0+_627+1,_0+_628,_0+_629+1,_0+_630,_0+_631+1,_0+_632,_0+_633+1,_0+_634,_0+_635+1,_0+_636,_0+_637+1,_0+_638,_0+_639+1,_0+_640,_0+_641+1,_0+_642,_0+_643+1,_0+_644,_0+_645+1,_0+_646,_0+_647+1,_0+_648,_0+_649+1,_0+_650,_0+_651+1,_0+_652,_0+_653+1,_0+_654,_0+_655+1,_0+_656,_0+_657+1,_0+_658,_0+_659+1,_0+_660,_0+_661+1,_0+_662,_0+_663+1,_0+_664,_0+_665+1,_0+_666,_0+_667+1,_0+_668,_0+_669+1,_0+_670,_0+_671+1,_0+_672,_0+_673+1,_0+_674,_0+_675+1,_0+_676,_0+_677+1,_0+_678,_0+_679+1,_0+_680,_0+_681+1,_0+_682,_0+_683+1,_0+_684,_0+_685+1,_0+_686,_0+_687+1,_0+_688,_0+_689+1,_0+_690,_0+_691+1,_0+_692,_0+_693+1,_0+_694,_0+_695+1,_0+_696,_0+_697+1,_0+_698,_0+_699+1,_0+_700,_0+_701+1,_0+_702,_0+_703+1,_0+_704,_0+_705+1,_0+_706,_0+_707+1,_0+_708,_0+_709+1,_0+_710,_0+_711+1,_0+_712,_0+_713+1,_0+_714,_0+_715+1,_0+_716,_0+_717+1,_0+_718,_0+_719+1,_0+_720,_0+_721+1,_0+_722,_0+_723+1,_0+_724,_0+_725+1,_0+_726,_0+_727+1,_0+_728,_0+_729+1,_0+_730,_0+_731+1,_0+_732,_0+_733+1,_0+_734,_0+_735+1,_0+_736,_0+_737+1,_0+_738,_0+_739+1,_0+_740,_0+_741+1,_0+_742,_0+_743+1,_0+_744,_0+_745+1,_0+_746,_0+_747+1,_0+_748,_0+_749+1,_0+_750,_0+_751+1,_0+_752,_0+_753+1,_0+_754,_0+_755+1,_0+_756,_0+_757+1,_0+_758,_0+_759+1,_0+_760,_0+_761+1,_0+_762,_0+_763+1,_0+_764,_0+_765+1,_0+_766,_0+_767+1,_0+_768,_0+_769+1,_0+_770,_0+_771+1,_0+_772,_0+_773+1,_0+_774,_0+_775+1,_0+_776,_0+_777+1,_0+_778,_0+_779+1,_0+_780,_0+_781+1,_0+_782,_0+_783+1,_0+_784,_0+_785+1,_0+_786,_0+_787+1,_0+_788,_0+_789+1,_0+_790,_0+_791+1,_0+_792,_0+_793+1,_0+_794,_0+_795+1,_0+_796,_0+_797+1,_0+_798,_0+_799+1,_0+_800,_0+_801+1,_0+_802,_0+_803+1,_0+_804,_0+_805+1,_0+_806,_0+_807+1,_0+_808,_0+_809+1,_0+_810,_0+_811+1,_0+_812,_0+_813+1,_0+_814,_0+_815+1,_0+_816,_0+_817+1,_0+_818,_0+_819+1,_0+_820,_0+_821+1,_0+_822,_0+_823+1,_0+_824,_0+_825+1,_0+_826,_0+_827+1,_0+_828,_0+_829+1,_0+_830,_0+_831+1,_0+_832,_0+_833+1,_0+_834,_0+_835+1,_0+_836,_0+_837+1,_0+_838,_0+_839+1,_0+_840,_0+_841+1,_0+_842,_0+_843+1,_0+_844,_0+_845+1,_0+_846,_0+_847+1,_0+_848,_0+_849+1,_0+_850,_0+_851+1,_0+_852,_0+_853+1,_0+_854,_0+_855+1,_0+_856,_0+_857+1,_0+_858,_0+_859+1,_0+_860,_0+_861+1,_0+_862,_0+_863+1,_0+_864,_0+_865+1,_0+_866,_0+_867+1,_0+_868,_0+_869+1,_0+_870,_0+_871+1,_0+_872,_0+_873+1,_0+_874,_0+_875+1,_0+_876,_0+_877+1,_0+_878,_0+_879+1,_0+_880,_0+_881+1,_0+_882,_0+_883+1,_0+_884,_0+_885+1,_0+_886,_0+_887+1,_0+_888,_0+_889+1,_0+_890,_0+_891+1,_0+_892,_0+_893+1,_0+_894,_0+_895+1,_0+_896,_0+_897+1,_0+_898,_0+_899+1,_0+_900,_0+_901+1,_0+_902,_0+_903+1,_0+_904,_0+_905+1,_0+_906,_0+_907+1,_0+_908,_0+_909+1,_0+_910,_0+_911+1,_0+_912,_0+_913+1,_0+_914,_0+_915+1,_0+_916,_0+_917+1,_0+_918,_0+_919+1,_0+_920,_0+_921+1,_0+_922,_0+_923+1,_0+_924,_0+_925+1,_0+_926,_0+_927+1,_0+_928,_0+_929+1,_0+_930,_0+_931+1,_0+_932,_0+_933+1,_0+_934,_0+_935+1,_0+_936,_0+_937+1,_0+_938,_0+_939+1,_0+_940,_0+_941+1,_0+_942,_0+_943+1,_0+_944,_0+_945+1,_0+_946,_0+_947+1,_0+_948,_0+_949+1,_0+_950,_0+_951+1,_0+_952,_0+_953+1,_0+_954,_0+_955+1,_0+_956,_0+_957+1,_0+_958,_0+_959+1,_0+_960,_0+_961+1,_0+_962,_0+_963+1,_0+_964,_0+_965+1,_0+_966,_0+_967+1,_0+_968,_0+_969+1,_0+_970,_0+_971+1,_0+_972,_0+_973+1,_0+_974,_0+_975+1,_0+_976,_0+_977+1,_0+_978,_0+_979+1,_0+_980,_0+_981+1,_0+_982,_0+_983+1,_0+_984,_0+_985+1,_0+_986,_0+_987+1,_0+_988,_0+_989+1,_0+_990,_0+_991+1,_0+_992,_0+_993+1,_0+_994,_0+_995+1,_0+_996,_0+_997+1,_0+_998,_0+_999+1]
2、3分、時間はかかったが、確かに計算することができた。
だいたいこの問題は、計算できそうなので、群城は、もっと複雑な嘘つき問題を考えることにした。
***
問題. この中で嘘をついているのは、誰か?
X_1「X_nは嘘をついている」
X_2「X_1は嘘をついている」
X_3「X_1とX_2は嘘をついている」
X_4「X_1とX_2とX_3は嘘をついている」
…
X_(n-1)「X_1とX_2と…とX_(n-2)は嘘をついている」
X_n「X_1とX_2と…とX_(n-1)は嘘をついている」
***
すなわち、階段状に、X_2以降は、自分より番号が若い人は、みんな嘘をついている、そして、X_1 は X_n が嘘をついていると下克上している、魑魅魍魎な状況である。
「これを、式で表せば、」
x1 + xn + 1 = 0
x2 + x1 + 1 = 0
x3 + x1*x2 + 1 = 0
x4 + x1*x2*x3 + 1 = 0
…
x(n-1)+x1*x2*...*x(n-2) + 1 = 0
xn + x1*x2*...*x(n-1) + 1 = 0
「となる。このプログラムを組めば、」
def uso2(N){
P=[];
V=[];
B=1;
for(I=1;I<=N;I++){
A=uc();
if(I>1){
P=cons(A+B+1,P);
}
V=cons(A,V);
B*=A;
}
P=cons(V[0]+V[N-1]+1,P);
G=nd_gr(P,V,2,2);
return(G);
}
end$
「で良さそうだな。これで、N=5のときを試してみよう。」
uso2(5);
[_0^8+_0^4+_0^2,_0+_1+1,_0^2+_0+_2+1,_0^4+_0+_3+1,_0+_4+1]
「これって、つまり、」
X_1=正直
X_2=嘘つき
X_3=嘘つき
X_4=嘘つき
X_5=嘘つき
「ってことだよな。一般のNの場合も、X_2以降は、みんな嘘つきになりそうだ。よし、さっきみたいに数を増やしてみるかな!」
uso2(10)
[_0^256,_0+_1+1,_0^2+_0+_2+1,_0^4+_0+_3+1,_0^8+_0^4+_0^2+_0+_4+1,_0^16+_0+_5+1,_0^32+_0^16+_0^2+_0+_6+1,_0^64+_0^16+_0^4+_0+_7+1,_0^128+_0^64+_0^32+_0^16+_0^8+_0^4+_0^2+_0+_8+1,_0+_9+1]
「よし、出来てる!もっと大きく!」
uso2(100)
「あれ?出てこない…?」
しばらく待ったが、出てくる気配がなかった。
「しょうがない。ちょっと数字を小さくしてみるかな。」
uso2(50)
だが、これまた、すぐに出てこない。
「もっと小さくかあ?」
uso(25)
「うーん出てこないなあ。」
いよいよ、N=15の場合を試してみることにした。
uso(15)
[_0^8192+_0^4096+_0^512+_0^256+_0^32+_0^16+_0^2,_0+_1+1,_0^2+_0+_2+1,_0^4+_0+_3+1,_0^8+_0^4+_0^2+_0+_4+1,_0^16+_0+_5+1,_0^32+_0^16+_0^2+_0+_6+1,_0^64+_0^16+_0^4+_0+_7+1,_0^128+_0^64+_0^32+_0^16+_0^8+_0^4+_0^2+_0+_8+1,_0^256+_0+_9+1,_0^512+_0^256+_0^2+_0+_10+1,_0^1024+_0^256+_0^4+_0+_11+1,_0^2048+_0^1024+_0^512+_0^256+_0^8+_0^4+_0^2+_0+_12+1,_0^4096+_0^256+_0^16+_0+_13+1,_0+_14+1]
出てきたが、その _0 の指数に群城は驚いた。
「8192次の式が出てきている……」
元の式は、せいぜい、14次の式しか出てこなったはずだ。
それが、グレブナー基底になると、大きく膨れ上がっている。
もしかしたら、次数の増加が原因で、計算が遅くなっているかもしれない。
群城は、そう推測した。
「もっと、もっと、複雑な、嘘つき問題だったら、もっと全然計算できないかもしれない。」
嘘つき問題は、グレブナー基底を使って解ける!と、当初豪語していた自分が、群城は少し恥ずかしくなった。
と、同時に、どうしたらもっと効率よく計算できるんだ?とも、考えていた。
ハッと、Borgwardt 先生が言っていたことを思い出した。
「出来ることより、出来ないことを見つけること。」
もしかしたら、このことを言っていたのかもしれない。
出来ることで、満足せず、出来ないことを見つけ、それを出来るように工夫して、また出来ないことを探す。
計算機実験とは、その繰り返しなのかもしれない。
気がつくと、あれから、何時間も経っており、外は、すっかり暗くなっていた。
こんなに数学に集中したのは、いつぶりかな。
群城は、自転車のキーをはずしながら、そう思った。
「そもそも、なんで、数学を好きになったんだっけ?」
ふとそんなことが脳裏によぎり、過去を振り返ってみる。
「ああ、あれか。」
あれは、小学生のときだったっけ。
「ぶぶー!いち足すいちは、田んぼの田だろ!ばっかでー!」
「すすのばーか!ばーか!」
アタシは、あの頃は、まだ気が弱かったから、よく男子にからかわれていた。
「……1足す1は…………2だもん。」
それが、いつもの昼休み。
「なんかいってるぞこいつ!」
「すすさーん?」
「大きな声で、発言しないと、聞こえませんよー?」
あいつは、教室では、いつも本を読んでいた。
あいつとは、家が近いぐらいで、仲がいいってわけでもなかった。
「みろよこいつの筆箱!」
「変なのー!」
「壊しちゃおうぜ!」
どうしよう。
お母さんから、せっかく、買ってもらったものなのに。
アタシが、目をつぶった瞬間、
声がした。
「いち足すいちは――」
あいつだった。
「1+1=2 ってのは、すごく難しくて、ラッセルっていう天才数学者が、証明したんだ。しゅーごーろんっていう、難しいものを使わなきゃいけなくて、えーと、だから、すごく難しくて……と、とにかくすごく難しいんだ!」
1+1=2が難しいとか、バカじゃねえの?なにいってんだこいつ?
と、アタシ以上に、笑われるあいつ。
とうとう、あいつに向けて、バーカ!バーカ!のコールまで始まった。
そして、アタシ以上に顔を真っ赤にして、叫んだんだよね。
「だ、だから、すずちゃんはすごいんだ!!」
それから、「あいつら、付き合ってるんだぜー」と、もっとからかわれるようになったけど、そのときは、恥ずかしながらも、ちょっと嬉しかったっけ。
そして、中学に入ったら、あいつの読んでた数学の本とか、ちょくちょくカツア…借りて、数学に興味持つようになったんだっけ。
ふう…。日本に帰ったら、あいつに嘘つき問題を出してみるかな。
その日のカリフォルニアの星空は、いつもより、ちょっとだけ明るいなと、群城はそう思った。
新規登録で充実の読書を
- マイページ
- 読書の状況から作品を自動で分類して簡単に管理できる
- 小説の未読話数がひと目でわかり前回の続きから読める
- フォローしたユーザーの活動を追える
- 通知
- 小説の更新や作者の新作の情報を受け取れる
- 閲覧履歴
- 以前読んだ小説が一覧で見つけやすい
アカウントをお持ちの方はログイン
ビューワー設定
文字サイズ
背景色
フォント
組み方向
機能をオンにすると、画面の下部をタップする度に自動的にスクロールして読み進められます。
応援すると応援コメントも書けます