グレブナー基底で嘘を見抜く

グレブナー基底大好きbot @groebner_basis

嘘をついてるのは誰ぶな？

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く①】 このアンケートの問題を今から、グレブナー基底を用いて機械的に解いてみたいと思うぶなっ！ みんなも一度この問題について考えてみてぶなっ！

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く②】 一応、アンケートの問題を文字に起こすと、 問題「次のうち嘘をついているのは誰か？」 A「Bは正しい」 B「CかDは正しい」 C「Dは嘘を付いている」 D「嘘をついているのは１人だけだ」 便宜上、回答１～４をA～Dに置き換えたぶなっ！

グレブナー基底大好きbot @groebner_basis

【見抜く③】 まずは、この問題を「多項式」で置き換えたいと思うぶなっ！ A、B、C、Dの主張にそれぞれ x ,y, z, w という変数を割り当て、主張が正しいときには0, 正しくないときには1となることとするぶな！ 例えばAの主張が正しければx=0, 嘘ならばx=1となるぶな！

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く④】 今から、０と１しか係数として登場しない多項式の世界を考えるぶな。 （つまり、体K={0,1}上で考えるということぶな。） まず、Aの主張は「Bは正しい」ということぶなから、 x=y という式が成り立つぶな。

グレブナー基底大好きbot @groebner_basis

【嘘を見抜く⑤】 実際、もしAの主張が正しければ（つまりx=0）ならば y=x=0 となりBの主張は正しいとなり、逆にAが嘘をついていれば（つまりx=1ならば）、 y=x=1 となりBは嘘をついていることになるぶな。 つまり、 A「Bは正しい」⇔x=y が成り立つぶな。

グレブナー基底大好きbot @groebner_basis

【嘘を見抜く⑥】 また補足としてx,y,z,wは、それぞれ0か1の値のみしか取らないことに注意ぶなよ！ では次にBの主張を多項式に変換してみるぶな。 B「CかDは正しい」 ぶなから、つまり、z=0またはw=0ぶな。 よって、 y=z*w が対応する多項式として出てくるぶな。

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く⑦】 実際、Bが正しければy=0で、 z*w=y=0 からCかDのどちらかは正しいぶなね！ 逆にBが嘘をついていればy=1で、 z*w=y=1 から z=w=1 となり、CとDは両方とも嘘をついているぶなっ！

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く⑧】 次にCの主張を多項式で表すぶな。 C「Dは嘘をついている」から z=1-w が対応する多項式になるぶな。 これは、zとwの値（つまりCとDの真偽）は必ず異なり、 つまり、 z=0⇒w=1 z=1⇒w=0 となることから分かるぶなねっ！

グレブナー基底大好きbot @groebner_basis

【グレブナー嘘を見抜く⑨】 最後に、 Dの主張「嘘をついているのはただ一人である」 を多項式で書くぶな。 これはつまり、x,y,z,wの中で「1」は１つだけで残りは「0」ということぶな。 少し複雑なのでゆっくりみていくぶなね。 まず、 x+y+z+w=1 という式を考えるぶな。

グレブナー基底大好きbot @groebner_basis

【グレブナー嘘を見抜く⑩】 もし、x,y,z,wに1が一つだけならばこの式は満たされるぶな。 よって 「嘘つきがただ一人」⇒ x+y+z+w=1 が成り立つぶな。 では逆の方向は成り立つかというと、x,y,z,wの中に1が３つだけあっても右の式を満たすので、逆は成り立たないぶな。

グレブナー基底大好きbot @groebner_basis

【グレブナー嘘を見抜く⑪】 実際、例えば、x=y=z=1,w=0のときは、1+1+1+0=1となり成り立つぶな。（0と1しかない世界で考えてるので、2=0に注意ぶな！） なので、 xyz+xyw+xzw+yzw=0 という式を右に加えるぶな。

グレブナー基底大好きbot @groebner_basis

【グレブナー嘘を見抜く⑫】 1が３つの場合、この式を満たさないことは簡単にわかるぶな。 しかも、1が１つの場合この式を満たすぶなっ！ よって、 「嘘つきはただ一人」⇔ x+y+w+z=1 かつ xyz+xyw+xzw+yzw=0 が成り立つぶなっ！

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く⑬】 一般に、命題P,Qとそれに対応する変数p,qがあるとき、 PかつQ ⇔ (p-1)*(q-1)-1=0 が成り立つぶな（演習問題とするぶな！） これを使って、前ツイートの同値部分の右側をまとめて多項式で表すと、

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く⑭】 {(x+y+w+z-1)-1}*{(xyz+xyw+xzw+yzw)-1}-1=0 となるぶな！つまり、 D「嘘つきはただ一人」⇔ w={(x+y+w+z-1)-1}*{(xyz+xyw+xzw+yzw)-1}-1 が成り立つぶなっ！

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く⑮】 以上の条件をまとめると、 x-y=0, y-zw=0, z+w-1=0, w-{(x+y+w+z-1)-1}*{(xyz+xyw+xzw+yzw)-1}-1=0 という連立方程式で最初の「嘘つき問題」を表すことができたぶなっ！

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く⑯】 問題は、『どのやってこの「連立方程式」を解けるか？』ぶな！ ここで登場するのが「グレブナー基底」ぶな！ 実は、グレブナー基底を使うと、この「連立方程式」を解くことができるぶなっ グレブナー基底すごいぶなっ！！！！！

グレブナー基底大好きbot @groebner_basis

【グレブナー嘘を見抜く⑰】 実際に、上の連立方程式の多項式からなるイデアル <x-y, y-zw, z+w-1, w-{(x+y+w+z-1)-1}*{(xyz+xyw+xzw+yzw)-1}-1> のK={0,1}上のグレブナー基底を辞書式順序x>y>z>wで求めてみるぶな。

グレブナー基底大好きbot @groebner_basis

【グレブナー嘘を見抜く⑱】 Risa/Asirなどの数式処理ソフトで計算すると、 {z+w+1,x+y,y^2+w,y+w^2+w} がグレブナー基底として出てくるぶな。 ここで、上の多項式からなる連立方程式の解と、元の連立方程式の解は一致していることに注意ぶなっ！

グレブナー基底大好きbot @groebner_basis

【嘘を見抜く⑲】 よって、 z+w+1=0, x+y=0 y^2+w=0 y+w^2+w=0 が「嘘つき問題」を表す「整理された」連立方程式として出てきたぶな。 ここで、最後の式に注目するぶな。 その式の中の w^2+w に注目すると、これはwが０だろうと１だろうと常に０ぶな。

グレブナー基底大好きbot @groebner_basis

【グレブナー嘘を見抜く⑳】 したがって、最後の式から、y=0が言えるぶな。 よって、３つ目の式 y^2+w=0 からw=0が言えて、さらに、２つ目の式 x+y=0 からx=0が言えるぶな。 最後に、w=-と１番目の式 z+w+1=0 から、z=1が言えるぶな。

グレブナー基底大好きbot @groebner_basis

【グレブナー基底嘘を見抜く㉑】 つまり、最初の連立方程式の解として、 x=0,y=0,z=1,w=0 が言えたぶなっ！ これは、もとの変数の意味に戻ると、 A＝正直 B=正直 C=嘘つき D=正直 が問題の答えとして分かったぶなっ！ つまり、嘘つきは回答３ぶなっ！

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く㉒】 「普通に解いた方が速いのでは？」と思った人もいるかもしれないぶなけど、今解いた方法だと、コンピュータを使って機械的に解くことができることにメリットがあるぶなっ！例えば、１００人の「嘘つき問題」があっても、パソコンに計算させれば楽々ぶなねっ！

グレブナー基底大好きbot @groebner_basis

【グレブナー基底で嘘を見抜く㉓】 そして、今の解法の一番のポイントは「グレブナー基底を使うと連立方程式が解ける」ということぶなねっ！これは「消去理論」といって、グレブナー基底の性質として有名なものぶなっ！来週以降はこの消去理論についてぶなついしていきたいと思うぶなっつ！

グレブナー基底大好きbot @groebner_basis

【今日のまとめ】 「嘘つき問題は、実はグレブナー基底を使って解ける」 ぶなっ！