계산기 실험 (후편)
군죠는 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 교수가 보여준 20000자짜리 그뢰브너 기저에 살짝 겁이 났지만, 실제로 계산이 잘 되는 걸 보고서 가슴을 쓸어내렸다.
"그럼 계속 해보자!"
＊＊＊
문제. 이 중에서 누가 거짓말을 하고 있는가?
A. "B가 하는 말은 맞다."
B. "C나 D가 하는 말은 맞다."
C. "D는 거짓말을 하고 있다."
D. "여기서 한 명만 거짓말을 하고 있다."
＊＊＊
군죠는 처음 문제보다 좀 어려운 문제를 생각했다.
"이번엔 변수를 하나 추가해서 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. "여기서 한 명만 거짓말을 하고 있다."
"으음, 이건..."
위 문제를 군죠가 생각했다고는 하나, 애초에 적당히 구글링을 해서 얻은 적당한 문장을 적당히 갖다 붙여 적당히 만든 문제라서, 문제가 적당히 만들어졌는지 적당주의자 군죠가 적당히 검증할 방법은 없었다.
그렇기에 군죠는 D가 한 말을 어떻게 수식으로 표현할 지 고민 중이다.
"으음─."
'A 혹은 B 혹은 C 혹은 D가 거짓말을 하고 있다.'
"라는 뜻이니까,"
w+(x+1)(y+1)(z+1)(w+1)=0
"...이라고 두면 식이야 간단하지만, 이건 '적어도 한 명이 거짓말을 하고 있다'라는 뜻이니 거짓말쟁이가 두 명, 세 명, 네 명이어도 된단 말이야. 그러니 지금 D가 한 말에 들어맞는 식은 아니란 말이지. 으음."
A,B,C가 한 말과 달리 D가 한 말은 사람 수를 지정하고 있다.
사람 수를 지정하는 걸 어떻게 다항식으로 표현할 것인가?
"게다가 한 명 뿐이라고만 써있으니까 그 거짓말쟁이가 A여도 B여도 된단 말이지. 처음부터 D가 거짓말을 치고 있을 수도 있는 거고."
'거짓말쟁이는 언제나 하나!'라고 외치는 코 모 탐정 그 자신이 거짓말쟁이일 수도 있는 것이다.
"으으으."
군죠는 10분 정도 고민하다가 결국 머리를 쥐어싸고 아무 생각도 할 수 없게 되었다.
"설마 여기까지일 줄이야..."
결국 자포자기하여 라이하 고개에서 아카이 슈이치가 할 법한 대사를 중얼거린다.
"무슨 일이야?"
"우와악!"
C.J.다.
책상에 엎어져 끙끙대던 군죠를 발견하고 말을 건 모양이다.
"뭐야, 너잖아."
"뭐야, 라니 뭐야."
"그런 건 됐고 나 좀 살려줘. 중국인은 다들 머리 좋다며?"
"어, 뭔데?"
"이 문제 못 풀겠어."
군죠는 C.J.에게 이러쿵저러쿵 문제를 설명한다.
C.J.는 그 설명을 듣고 바로 답했다.
"그렇구나. 적어도 대칭식 아니겠어?"
"대칭식?"
"x+y+z+w랑 xyzw처럼 x,y,z,w를 바꿔 대입해도 같은 식 나오는 거 말야."
"아하, 그거."
"거짓말쟁이는 한명이라면서. 그러면 누가 거짓말을 하더라도, 다시 말해 대응되는 변수를 바꿔서 대입해도 식이 변하지 않는다는 거잖아?"
"그러네. 변수를 바꿨을 때 식이 달라지면 식의 의미가 변하는구나."
"그리고 대칭식은 모두 기본대칭다항식으로 만들 수 있으니까 걔들을 어떻게 잘 다뤄보면 나오지 않겠어?"
(4변수) 기본대칭다항식이란 가장 간단한 대칭다항식으로, 아래처럼 총 4개 있다.
x+y+z+w
xy+yz+zw+wx+yw+xz
xyz+yzw+zwx+wxy
xyzw
모든 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이므로 성립하고, 한 명만 거짓말을 한다면 1+0+0+0=1이니까 성립하지 않겠지. 두 명만 거짓말을 한다면 1+1+0+0=1+1=0이니까 OK고, 3명만 거짓말을 한다면 1+1+1+0=1이니까 안 되고. 그리고 모두 거짓말쟁이면 1+1+1+1=0이니까 오케이. 따라서,"
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*1+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*0=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+wxy=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=0이므로 (3)이 성립하지 않음.1
거짓말쟁이=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=1이므로 (3)이 성립.
"따라서,"
xyz+yzw+zwx+wxy=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+wxy=0 ⇔ 거짓말쟁이는 0명, 2명 또는 4명.
xyzw=0 ⇔ 거짓말쟁이는 0명, 1명, 2명 또는 3명.
"...처럼 되지. 이제 어떻게 '한 명만 거짓말쟁이'라는 식을 만들까..."
요컨대 군죠는 이 증거들로부터 어떻게 범인인 대칭식을 찾을 지 추리하고 있다.
나비넥타이형 음성 변조기도, 손목시계형 마취총도, 터보 엔진이 달린 스케이트보드도 없지만 지금 군죠는 어엿한 명탐정이다.
입에 피스톨 모양을 한 손가락을 대고 골똘히 생각한다.
번ーーーーーー쩍!
군죠의 귀에 섬광이 번쩍인다. 무언가 번뜩인 게 있는 모양이다.
"서, 설마!?"
x+y+z+w=0 ⇔ 거짓말쟁이는 짝수명.
"의 부정을 생각하면 0의 부정은 1이니까,"
x+y+z+w=1 ⇔ 거짓말쟁이는 홀수명.
"그리고 두 번째 식,"
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명.
"...이러면 되잖아!!"
군죠는 답을 찾고 흥분하여 그만 의자에서 벌떡 일어섰다.
마음 속에서 이렇게 하면 되겠다는 발견의 기쁨이 치밀어올랐다.
"그러므로 거짓말쟁이 문제,"
＊＊＊
문제. 이 중에서 누가 거짓말을 하고 있는가?
A. "B가 하는 말은 맞다."
B. "C나 D가 하는 말은 맞다."
C. "D는 거짓말을 하고 있다."
D. "여기서 한 명만 거짓말을 하고 있다."
＊＊＊
"...는 연립방정식,"
x-y=0
y-zw=0
z+w+1=0
w-z+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-1명의 사람들이 "내 다음 사람은 거짓말을 하고 있다"고 말하는 거짓말쟁이 문제다.
"좋았어. 이걸 각각 식으로 나타내면,"
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 gura(N){
P=[];
V=[];
A=1;
for(I=1;I<=N;I++){
A=gur();
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언어와 문법이 비슷하지만 (대입할 때 쓸) 변수는 대문자로만 써야 하는 등 독특한 규칙 역시 갖고 있다.
군죠는 위와 같이 다항식에 쓸 변수를 생성하기 위해 gur()라는 함수를 사용했다.
그리고 방금 만든 거짓말쟁이 문제를 임의의 N명에 대해서 풀 수 있는 gura(N)이라는 함수를 만들었다.
"좋았어! 이걸로 N을 계속 키워서 어디까지 계산할 수 있는지 알아보자!!"
우선 N=10을 넣었다.
gura(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을 넣었다.
gura(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]
"으음... 이것도 잘 계산되는데. 좋았어, 더 큰 수로!"
이번에는 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 gura2(N){
P=[];
V=[];
B=1;
for(I=1;I<=N;I++){
A=gur();
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일 때를 계산해볼까."
gura2(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 아래로는 싹 다 거짓말쟁이일 것 같은데. 그래, 아까처럼 N을 키워볼까!"
gura2(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]
"잘 나오네! 좀 더 키워볼까!"
gura2(100)
"어? 안 나오네...?"
한동안 기다렸지만 답은 나올 기색조차 없었다.
"어쩔 수 없지. 수를 좀 줄여서 계산해볼까."
gura2(25)
"끄응, 안 나오네."
결국 N=15인 경우를 계산해보기로 했다.
gura(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가 어렵다니 너 바보야?"
"얜 또 뭔 소리야?"
그 녀석은 나 이상으로 놀림받았다.
마침내 그 녀석을 향해 다들 바보라고 외쳐대기 시작했다.
그러자 녀석은 나 이상으로 얼굴이 새빨개져선 외쳤더랬지.
"그, 그러니까 스즈는 대단하다고!!"
그 이후 녀석들은 우리가 사귄다며 더 심하게 놀려댔다.
그 순간은 부끄러웠지만 또 은근히 기뻤더랬지.
그리고 중학교에 입학해서는 가끔씩 그 녀석이 읽던 수학책을 뺏어... 아니 빌려 읽다보니 수학에 흥미가 생겼다.
후우... 일본 돌아가면 녀석에게 거짓말쟁이 문제나 내볼까.
그 날 군죠의 눈에 비친 캘리포니아의 밤하늘은 평소보다 어스레하나마 밝은 별빛으로 가득했다.
- 원문에서 계산 실수한 것을 교정하였음―역자 주. [본문으로]