김 용묵의 절대공간 - 블로그

A와 B라는 두 집단이 서로 패싸움을 시작했다. A는 전투원이 5명이고 B는 4명이다. 그런데 양 진영의 모든 전투원들은 체력· 정신력· 무장 등등이 완전히 동일하며, 기습 가능성이라든가 지형적인 유불리, 엄폐물 같은 것도 없이 탁 트인 개활지에서 순수하게 힘과 힘만이 충돌하는 형태로 싸우게 됐다고 치자. 싸움은 둘 중 한 진영의 전투원들이 몽땅 죽거나 중상을 입어서 전투력을 상실할 때까지 계속된다. 그렇다면 이 싸움의 결과는 어찌 될까?

마오 쩌둥이던가 스탈린이던가.. 인권 쌈싸먹은 독재자답게 "전쟁 나서 1억 인구가 죽는 것쯤은 별 일 아니다. 사람이야 또 낳으면 되니까. 적군이 병력이 1억이면 우리는 1억에다 한 명만 더 붙여서 이기면 된다" 그런 요지의 무지막지한 말을 한 적이 있었다. 정확하게 누가 언제 한 말인지 출처 확인이 잘 안 되네, 분명 본 기억은 있는데..

그런데 저건 병신 같지만 묘하게 설득력이 있는 말이다. 외적인 요인이 차이가 전혀 없고 완전히 동일하다면 상식적으로 생각했을 때 쪽수가 한 명이라도 더 많은 집단이 필승하고 부족한 집단은 필패할 것이다.
위의 경우라면 B가 지고 A가 이기는 것 자체는 따 놓은 당상이다. 단지 문제는 A가 B를 얼마나 너끈히 이기느냐, 어느 정도의 피해를 입고 승리하느냐로 귀착된다.

그 답은 A와 B가 어떤 방식으로 싸우느냐에 따라 달라진다.
조폭들 패싸움처럼 기껏해야 일대일로 근접해서 냉병기를 사용하는 싸움이라든가, 총이라 해도 18세기 전열보병 전술처럼 비현실적일 정도로 너무 신사적으로 일대일 턴제로 싸우는 거라면 말 그대로 일대일로 상쇄하고 남은 병력만이 생존자가 된다. B는 전멸이요, A는 A-B에 해당하는 인원이 남는다. 고로 5:4의 싸움이라면 한 명만 남는 거다. 이것을 일명 란체스터 제1법칙이라고 한다.

그러나 점 vs 점이 아니라 면 vs 면 단위로 실시간으로 부딪치는 현실의 전투에서는 다구리가 더 대규모로 가능하며 병력의 작은 차이가 훨씬 더 큰 차이를 야기한다. 설정상 한 집단의 전투력은 병력에 비례해서 나오게 돼 있는데 그 전투력 자체가 병력의 손실로 인해서 차츰 감소한다. 두 변수가 같이 변화하면서 비선형적인 구도를 만든다는 뜻이다. 그래서 처음부터 병력과 전투력이 열세였던 집단은 그 감소폭이 더욱 커지면서 전멸에 이르지만, 우세 집단이 받는 대미지는 시간이 흐를수록 더욱 작아진다. 전투력도 부익부 빈익빈으로 치닫는다!

그래서 답부터 말하자면, 이런 현실의 싸움에서 A와 B가 붙으면 B가 전멸한 뒤 A는 한 명만 남는 게 아니라 이론적으로 3명이나 생존해 있게 된다. B는 자기 진영 4명이 전멸하는 동안 A를 2명밖에 못 죽인다는 것이다. 공식으로 표현하면 단순한 A-B가 아니라 sqrt(A^2 - B^2)이다.
마치 직각삼각형 세 변의 길이와 같은 구도가 된다. 그렇다면 5명 vs 4명이 아니라 13명 vs 12명이 붙으면, 12명 팀은 전멸하고 13명 팀은 8명만 죽어서 5명이 남는다.

이것은 란체스터 제2법칙이라고 명명되어 있다. 영국의 항공 공학 엔지니어가 1차 세계 대전의 양상에서 착안하여 고안했다.
스타크 같은 전략 시뮬 게임에서 드라군, 마린, 히드라 같은 원거리 공격 유닛들을 서로 마주보게 해서 어택 땅으로 싸움을 붙여 보면 이 법칙이 의외로 굉장히 잘 적중한다고 한다. 란체스터의 법칙에 대해 소개해 놓은 타 블로그 글들을 검색해 보면 전략 시뮬 게임으로 실험을 해 봤는데 높은 적중률을 보고 놀랐다는 말이 많이 나온다. 1억 명에다가 딱 한 명만 더 보태서 이기면 된다는 말이 그저 허세만은 아닌 셈이다.

란체스터 제2법칙이 어째서 성립하는지를 엄밀하게 논하려면 삼라만상의 변화량을 기술하는 끝판왕 도구인 미분방정식을 동원해야 한다.
시각 t에 대해서 A 진영의 병력을 나타내는 함수 f(t), B 진영의 병력을 나타내는 함수 g(t)를 정의하자.
위의 예에서는 전투 전의 초기 상태 t=0에 대해 f(0)=5, g(0)=4가 될 것이다. 뭐, 일반화해서 f(0)=a, g(0)=b라고 잡아도 된다.

전투의 진행으로 인해 f(t), g(t) 모두 병력이 감소할 것이다. 그런데 그 감소하는 변화량이 바로 상대방 함수의 함수값과 같다. d f(t) / dt = -g(t) 요, d g(t) / dt = -f(t)라는 뜻이다.
그렇다면 이 f와 g는 도대체 어떻게 생겨먹은 함수일까? 0보다 큰 t에 대해서 g(t)=0이 되고(B 진영의 전멸) 그 정의상 동시에 f'(t)=0도 되는 지점이 있을 것이다. 그 t가 얼마인지는 중요하지 않겠지만, 이때 f(t)의 값을 a와 b에 대해서 구하면 란체스터 제2법칙을 유도할 수 있을 것이다.

f의 도함수가 -g이고 g의 도함수가 또 -f라니.. 일단 얘는 미분을 짝수 번 반복하면 도함수가 자기 자신으로 돌아오는 뭔가 골때리는 함수 형태가 될 듯하다. 즉, 4배수 주기로 제자리로 돌아오는 삼각함수보다는.. cosh, sinh 같은 쌍곡선함수 형태가 될 것 같다. 걔들은 미분을 하면 cosh, sinh, cosh ... 이렇게 반복되는데, 문제의 저 함수는 f, -g, f, ... 이렇게 반복된다.

그래서 답을 구해 보면.. a>b여서 f가 더 우세한 진영을 나타낸다는 걸 염두에 뒀을 때
2*f(x) = (a+b)/e^x + (a-b)*e^x 요, 2*g(x) = (a+b)/e^x - (a-b)*e^x 가 된다. (2를 곱한 게 저런 것이므로 전체를 2로 나눠 줄 것)
e^x와 e^x의 역수를 절반씩 적절히 더하거나 빼는 cosh / sinh 함수를 상수배/평행이동만 한 형태인 걸 알 수 있다. f는 cosh에 대응하고 g는 그냥 sinh가 아니라 -sinh가 된다.

cosh는 현수선을 나타내는 함수이기도 하다. 그 말인즉슨 A와 B가 싸울 때 A의 피해 양상은 빨랫줄이나 쇠사슬이 아래로 축 늘어진 것과 비슷한 양상으로 스무스하게 감소할 거라는 뜻이다. 실제로 그런지 확인해 보자.

바로 이것이 5명과 4명, 또는 엄밀히 말해 5:4 비율의 병력이 맞붙었을 때 란체스터 제2법칙에 따라 예상되는 병력의 변화 양상이다!
g(x)=0이 되는 시점은 x= ln( (a+b)/(a-b) )/2 가 되며, (a=5, b=4일 때는 저 값은 대략 1.1)
이때 f(x)를 구해 보면 (a+b)/sqrt( (a+b)/(a-b) )가 나오고 식을 정리하면 진짜로 sqrt(a^2 - b^2)가 나온다.
임계점 이후부터는 g는 음수가 나오고 f는 감소가 아니라 오히려 증가하기 시작하지만, 이건 현실에서는 아무 의미 없는 추세일 테니 제끼면 된다.

더 직관적인 비유로 설명하자면.. 5:4가 붙어서 곧이곧대로 1명만 남는 싸움, 즉 란체스터 제1법칙은 y=1이라는 상수 그래프를 떠올리면 된다. 여기서 x가 4부터 0까지 가는(B진영) 동일 면적(= 정적분)을 5에서부터(A진영) 시작한다면 1에 도달한다.

그러나 란체스터 제2법칙은 y=1이 아니라 y=x라는 가변적인 그래프에 대응한다. 여기서 x가 4부터 0까지 가는 B진영의 면적 8(밑변과 높이가 모두 4인 삼각형)을 5에서부터 시작한다면.. 1이 아니라 3에서 멈추게 된다. 윗변 3, 아랫변 5, 높이 2인 사다리꼴의 넓이가 8이 되니까 말이다.
이를 일반화하면, 0부터 B까지 y=x를 정적분한 값은 sqrt(A^2-B^2)에서부터 A까지 정적분한 값과 같다. 이렇게 이해해도 된다.

전쟁이라는 건 여기저기 가성비를 따지면서 지킬 것과 버릴 것을 가리고 작전을 잘 짜야 이길 수 있다. 즉, 경제· 경영과도 밀접한 관계가 있다. 그렇기 때문에 오늘날 란체스터의 법칙은 군사학보다는 경제학 쪽에서도 기초 이론으로 더 중요하게 다뤄진다. 포병 장교에다 수학 박사 출신인 지 만원 박사 같은 분이 아마 이런 분야의 최고 전문가가 아닐까 싶다.
이 법칙은 스플래시 데미지나 사이오닉 스톰-_- 같은 변수가 있지 않은 한, 왜 일반적으로는 "뭉치면 살고 흩어지면 죽는다"가 성립하는지를 무식하게 시행착오 겪을 필요 없이 수식만으로도 잘 설명해 준다. 5:4로만 붙여도 저 그래프와 같은 처참한 결과가 나오지 않던가?

더 나아가서 어지간히 절체절명의 위급한 상황이 아닌 이상, 스타에서 유닛이 생성되는 족족 적진으로 찔끔찔끔 축차투입을 해서는 절대 안 되며 캐리어 같은 유닛도 반드시 일정 기수 이상 모아야 제 성능이 발휘된다는 것을 보여준다.
또한 전쟁이 나면 전투 직전에야 양 진영이 모두 사기 진작이 매우 중요하기 때문에 "마지막 하나까지 결사항전" 운운하지만.. 대세를 도저히 뒤집을 수 없을 정도로 승부가 너무 기울고 100% 개죽음밖에 선택의 여지가 없을 때는 불가피하게 꼬리 내리고 항복도 하는 것이다.

이상. 란체스터 법칙 하나 갖고 미분방정식에, 쌍곡선함수에 별 얘기가 다 나왔다.
다만, 현실의 전장에서는 수학 숫자놀음 나부랭이보다 예측할 수 없는 외부 변수가 훨씬 더 많이 존재하기 때문에 란체스터 법칙이 절대적인 만능 장땡인 건 아니다. 겉으로 드러나는 병력 열세를 극복하고 B가 A를 이긴 사례도 역사엔 얼마든지 존재한다는 것도 생각할 필요가 있다.
그러니 성경에서 하나님께서 기드온에게 병사 수를 32000명에서 거의 1% 수준인 300명으로 일부러 줄여 버리고도 오히려 전투를 승리로 이끄신 것이 대단한 이야기인 것이다(삿 7). 진짜 300의 원조는 무슨 영화에 나오는 스파르타 군대가 아니라 저 군대였던 셈이다.

Posted by 사무엘

* 옛날 2014년에 썼던 글을 관련 내용을 크게 보강하여 리메이크 한 것이다.

디지털 컴퓨터라는 게 0과 1, 2진법을 사용하다 보니, 2^n이라 하면 정보량과 관련해서 특히 컴퓨터쟁이들에게 아주 친근한 수이다.
그런데 2^n보다 1 더 크거나 작은 수가 소수라면 제각각 수학적으로 좀 독특한 의미를 갖게 된다.

1.
2^n-1 형태인 수를 메르센 수라고 한다. n층짜리 하노이의 탑의 원반을 옆으로 모두 옮기기 위해서는 이 메르센 수만치 지수함수적으로 증가하는 횟수만치 원반을 이동시켜야 한다. 그리고 메르센 수 중에서 소수인 놈을 메르센 소수라고 한다.
얘가 소수이려면 n도 반드시 소수여야 한다. n을 a와 b라는 두 자연수의 곱이라고 생각하고 2^ab - 1을 인수분해해 보면 그래야만 하는 구조적인 이유를 알 수 있다.

(2^ab는 (2^a)^b 와 같다. 2^(a+b)하고 혼동하지 말 것.)

n이 합성수여서 2 이상인 두 자연수 a, b의 곱으로 나타내어질 수 있다면 2^n-1은 빼도 박도 못하고 무조건 합성수가 돼 버린다. 전체 결과가 소수가 되려면 a는 1이고 b는 소수로 귀착되는 것밖에 가능성이 없다. 비록 이 조건이 만족된다고 해서 2^n-1이 언제나 반드시 소수가 된다는 보장은 없지만 말이다.
가장 작은 반례는 2^11-1이다. 11은 소수이지만 2047은 23*89로 소인수분해 되는 합성수이다.

메르센 수는 2^n에서 1이 부족한 형태라는 특성상 2진법으로 나타내면 모든 자리수가 1이다. 컴퓨터에서 취급이 간편하기도 하고, 또 n의 소수 여부를 판정한 뒤에 곧장 무려 2^n-1이라는 방대한 수를 취급할 수 있다는 특성상.. 컴퓨터로 가장 큰 소수를 찾는 프로젝트는 대개 메르센 수를 대상으로 진행되곤 한다. 물론 실제로는 메르센 수가 아닌 소수도 많이 있으며, 반대로 메르센 수 중에서도 메르센 소수는 매우 드물다는 점을 감안할 필요가 있다.

저런 거 찾는 건 거의 애니메이션 렌더링과 같은 급으로 상상을 초월하는 계산량으로 컴퓨터를 열받게 하고 혹사시키는 작업이다. 그나마 양만 많지 내부 과정 자체는 단순무식한 편이니 병렬화가 수월한 건 다행인 점이다.

메르센 소수는 짝수 완전수와 필요충분 관계로 정확히 대응하는 것으로 유명하다. (약수의 합이 자신과 같은 6, 28, 496 같은 수) 메르센 소수 2^n-1에다가 2^(n-1)을 곱하면 완전수가 나오기 때문이다. 괄호 순서에 유의할 것. 즉, 저기서 n에다 소수를 집어넣으면 된다. 천재 수학자 오일러가 모든 짝수 완전수는 이런 형태라는 것을 증명했다.
현재까지 메르센 소수는 약 50여 개가 알려져 있으나, 무한히 존재하는지는 불명이다.

2.
그럼, 다음으로 2^n+1의 경우를 생각해 보자. +1은 -1보다 더 자비심이 없다. n은 소수가 아니라 반드시 2의 거듭제곱 형태여야 그 값이 소수일 일말의 가능성이 생긴다. 이는 n의 소인수 중에 홀수가 절대로 존재해서는 안 됨을 의미한다. 아까 전과 비슷한 방식으로 2^ab + 1을 인수분해해 보면 그 이유를 알 수 있다.

n의 소인수에 홀수가 존재해서 그걸 b라고 설정하면 아까 -1일 때와는 부호만 미묘하게 다르게 저렇게 인수분해가 되며, 이 수는 100% 합성수임이 보장돼 버린다. (2^a - 1)이라면 a=1인 걸로 맞춰서 없앨 수라도 있지만, (2^a + 1)은 도저히 처분할 방법이 없다.

하긴, 고등학교 공통수학 수준의 인수분해 공식을 생각해 봐도, n이 홀수일 때에 한해서 (a^n + b^n)은 a+b로 나눠 떨어지며 인수분해가 된다. 나눠진 몫에 해당하는 항은 a^n에서 b^n으로 a와 b의 차수가 조금씩 늘고 줄고 부호가 교대로 바뀐다.
이를 일반화하면, n이 굳이 홀수가 아니더라도 6이나 10처럼 홀수 소인수가 포함돼 있으면(3, 5) (a^n + b^n)은 굳이 a+b가 아니더라도 (a^2+b^2) 같은 것으로라도 나눠 떨어지며 인수분해가 된다. 그렇지 않고 홀수 소인수가 전혀 없다면 +의 경우는 인수분해를 할 수 없다.

부연 설명 차원에서 인수분해된 식들이 전개되는 양상을 시각적으로 살펴보면 이러하다.
a^n - b^n은 n의 값과 관계없이 언제나 a-b로 나눠 떨어지며, 나눠진 몫의 항들은 부호가 모두 +가 유지된다. 전부 +인 항들이 한 칸 옆으로 물러간 채 -로 바뀌어서 전부 +/-가 상쇄돼 버리고 맨 앞의 +와 -만 남는다
++++
 ----
+...- (a-b)

하지만 a^n + b^n일 때는 +와 -가 교차하는 항들이 한 칸 옆으로 맞물려서 상쇄돼야 맨 앞과 뒤의 +가 남을 수 있다. 그러니 이때는 항이 홀수 개여서 양 끝이 +가 유지돼야 인수분해가 가능해지는 것이다.
+-+-+
 +-+-+
+....+ (a+b)

(쪼개고 쪼개도 분자 단위에서 계속 앞뒤로 + - 극을 갖는 자석 같아 보이기도 하고..;;)
이 두 경우를 모두 종합한 듯이 인상적인 상황은 (a^n - b^n)에서 n이 2의 거듭제곱 형태일 때이다. n=8인 경우를 예로 들어 보면, 이 식은 (a^4 + b^4)(a^2 + b^2)(a + b)(a - b)라고 아주 드라마틱하게 인수분해가 된다. n이 2의 거듭제곱이면 (a^n + b^n)은 -일 때와는 반대로 인수분해가 도저히 더 되지 않는 다항식계의 소수(?) 같은 존재가 된다.

그렇기에 2^n+1도 n이 반드시 2의 거듭제곱 형태여야만 구조적으로 인수분해가 되지 않고 소수일 가능성이 생기는 것이다. 그리고 2^(2^n)+1 형태인 수를 페르마 수라고 하며, 그 중 소수인 놈을 페르마 소수라고 한다. 간단하게 2^n-1로 정의되는 메르센 수와는 양상이 다르다.

그러니, 태생적으로 딱 봐도 페르마 소수는 메르센 소수보다도 더욱 드물 것 같이 생겼는데, 실제로 그러하다.
n에 비례해서 숫자가 넘사벽급으로 너무 폭발적으로 커지는 관계로, 페르마 소수는 n=0..4인 처음 겨우 5개밖에 알려져 있지 않다(3, 5, 17, 257, 65537). n이 아니라 2^n으로 계산한 것이다.

여기서 페르마란 "페르마의 마지막 정리" 내지 추측을 제시했던 17세기 프랑스의 그 엄친아 변호사 겸 아마추어 수학자를 가리키는 거 맞다..
페르마 자신은 저런 형태로 생성된 모든 수들이 소수일 거라고 1637년에 추측하였으나, 그로부터 100여 년 뒤인 1732년, 오일러가 n=5인 2^32+1은 소수가 아니라고 반증을 해 버렸다. 아까 그 메르센 소수와 완전수 관계를 증명한 그 오일러 말이다.
지금이야 그 정도 크기의 수는 컴퓨터로 소수 여부를 아주 간단히 판별할 수 있지만 오일러는 컴퓨터도 없던 시절에 저걸 도대체 어떻게 알아낸 걸까? 찰스 웨슬리가 찬송시 And can it be that I should gain을 쓰기도 전의 일이다(1738).

제곱근인 65536 이내의 모든 홀수들을 브루트 포스 식으로 일일이 주판 돌려서, 제자들까지 멀티코어로 동원해서 나눠 본 건 물론 아니고..
2^32 + 1의 소인수는 반드시 64k+1 의 형태라는 것을 어떤 계기로 알아내고는 찾았다고 한다. 범위를 많이 좁힌 것이다.
실제로 2^32 + 1은 641 * 6700417인데, 이는 (64*10+1)*(64*104694+1)이다.
그는 이를 일반화하여 페르마 수의 소인수는 반드시 "2의 거듭제곱의 a배 + 1"이라는 사실까지 정립했다.

n=5에 속하는 2^32+1에 이어 n=6 (2^64 + 1)의 경우도 합성수라는 게 추가로 밝혀진 건 오일러 이후로 또 100년이 넘게 지난 무려 1855년의 일이다(by Thomas Clausen). 나머지 페르마 수들도 대략 32까지 구해 보니 줄줄이 다 합성수라는 것이 계산을 통해 밝혀졌다. 페르마의 예상과는 정반대로 흘러간 셈이다.
그러니 65537을 끝으로 페르마 소수는 더 존재하지 않는 게 아닌가 추측되고 있으나, 이 역시 홀수 완전수의 존재 여부만큼이나 정식으로 증명된 것은 아니다.

메르센 소수가 짝수 완전수와 동치 관계이듯, 페르마 소수 역시 굉장히 의외의 곳에 큰 의미를 지니고 있다. 이것은 작도 가능한 정다각형의 특성과 관계가 있다. 변의 개수의 소인수가 2 and/or 페르마 소수들로만 이뤄진 정다각형은 눈금 없는 자와 컴퍼스를 이용해 작도 가능하다. 작도 가능한 수는 아무래도 사칙연산과 '제곱근'만으로 기술 가능한 수이니, 제곱근만을 연달아 적용하는 건 2의 거듭제곱만치 또 거듭제곱을 하는 것과 심상면에서 비슷해 보이긴 한다.

그렇기 때문에 작도 불가능한 최초의 정다각형은 정칠각형이며, 반대로 정17각형은 절차가 굉장히 복잡하고 까다롭긴 해도 작도 가능하다. 17은 페르마 소수이니까. 이걸 발견하여 증명한 사람은 오일러...는 아니고 18세기 독일의 천재 수학자인 가우스이며, 그것도 굉장히 어린 나이에 발견했다. sin 1도가 초월수가 아니라 대수적인 수이듯, cos 2*PI/17 역시 형태만 복잡할 뿐, 대수적인 수임을 의미한다.

(그림의 출처: 나무위키)
뭐, 이론적으로만 가능하다는 거지, 실제로 해 보면 누적되는 오차와 지저분한 보조선들 때문에 감당이 어려울 것이다. 하물며 정257각형과 심지어 정65537각형은? 이것도 이론에서나 작도 가능하다는 얘기다.

자, 지금까지 한 얘기들을 요약하면 다음과 같다.

• a^n-b^n은 언제나 a-b로 나눠 떨어지며 2^n-1 역시 그런 꼴의 수이므로, 얘를 소수로 만들려면 a-b가 반드시 1인 상황을 만들어야 한다. 그리고 메르센 수에서 그 경우란 n이 소수인 경우밖에 없다.
• 그리고 2^n+1의 일반형인 a^n+b^n은 아까처럼 한쪽 인수를 1로 만드는 게 불가능한 대신에, 인수분해 가능 여부가 n의 차수에 따라 조건부로 결정된다. 소수를 만들려면 물론 애초에 인수분해를 할 수 없는 상황을 만들어야 하며, n은 단순히 짝수인 정도를 넘어 소인수에 홀수가 전혀 없어야 한다. 그래서 n 자체가 2의 거듭제곱 형태인 것만 남는다.

그러고 보니 페르마뿐만 아니라 메르센도 17세기 동시대를 살았던 프랑스 사람이기 때문에 둘이 공통점이 있다. 메르센은 블레즈 파스칼의 스승이기도 했다. 프랑스, 독일 그쪽은 수학· 과학 쪽으로 그때로부터 지금까지 한가닥 하고 있는 대단한 동네이다.

* 소수 관련 여담

(1) 소수 자체가 안 그래도 수가 커질수록 (log n) / n 급의 스케일로 자연수에서 등장 빈도가 극도로 드물어진다. 그런데 그 소수들 중에서도 굉장히 까다로운 조건을 만족하는 메르센 내지 페르마 소수 같은 것들은 한계치 최대치가 존재한다 해도 이상할 게 없을 것이다. 굳이 수 자체가 특이한 게 아니더라도 2 간격으로 나란히 존재하는 쌍둥이 소수 쌍(5와 7, 11과 13, 17과 19..) 같은 것도 말이다. 그런데 한계치가 있다면 그 최대값이 알려져 있어야 할 텐데 그것이 수수께끼이다.

(2) 오일러의 업적 중에는 소수와 관련해서도 정말 살떨리는 것들이 많다. 자연수의 제곱의 역수의 무한합이 원주율과 관계 있는 수로 수렴한다는 것을 규명했을 뿐만 아니라 이건 소수의 분포와도 관계가 있기 때문에 임의의 두 수가 서로 소일 확률과 같다고 입증한 건 뭐.. 할 말을 잃게 만든다. 예전에 본인의 블로그에서 다룬 적이 있다.

(3) 또한 그는 소수의 개수가 무한한 건 말할 것도 없고, 소수의 역수의 무한합이 무한대로 발산한다는.. 거의 충격과 공포 안드로메다급의 명제도 증명했다. 물론 속도는 이중 로그(로그에다 또 로그) 급으로 끔찍하게 느리니 기대하지 말자. 그냥 자연수의 역수의 합만 해도 얼마나 느린데 하물며 소수의 역수는! 쉽게 말해 10에다 0을 10의 20승개만치 붙인 영역만치 소수의 역수를 더하면 합이 20이 될까말까 한다는 뜻이다. 쟤가 도대체 제곱의 역수의 무한합보다 뭐가 더 나은 구석이 있다고 발산을 하는 걸까?

단, 쌍둥이 소수들의 역수의 합은 유한으로 수렴한다고 한다. 쌍둥이 소수가 유한하다면 당연히 유한 수렴이겠지만, 무한하다 하더라도 얘는 발산하지 못한다고.. 구체적인 값은 모르겠지만 추세가 그렇게 된다는 큰 그림만 증명을 한 것이다. 어떻게 증명했는지는 나한테 묻지 마시길.

(4) 가우스, 오일러 등 인류 역사상 수많은 괴수 천재 수학자들이 초월적인 업적을 남기고 갔지만, 어떤 형태로든 소수 생성 규칙을 표방하는 모든 예측· 추측은 지금까지 하나도 완벽하게 적중한 게 없었다. 저 페르마의 추측처럼 말이다.
소수를 생성하는 규칙을 무슨 정보 검색이나 패턴 매칭에다가 비유해서 설명하자면, 정밀도와 재현율(precision & recall) 어느 것 하나라도 확실하게 잡는 규칙이 지금까지 발견된 적이 없다는 것이다. 정밀도가 100%라면 모든 소수를 커버하지는 못해도 일단 이 규칙이 생성하는 수는 다 소수임이 보장되는 것이고, 재현율이 100%라면 종종 소수가 아닌 놈(false alarm)이 섞여 있더라도 소수는 하나도 빠짐없이 커버한다는 뜻이다.

(5) partition number라는 게 있다. f(2)라면 1+1, 2 이렇게 2가지, f(3)이라면 1+1+1, 2+1, 3 이렇게 3가지, f(4)라면 1 1 1 1, 2 1 1, 2 2, 3 1, 4 이렇게 5... 뭔가 테트리스 조합처럼 올라가는데, 이 수열이 2 3 5 7 11 (15 22...) 이렇게 앞부분은 소수와 굉장히 비슷한 양상으로 시작한다. 무슨 파이의 그럴싸한 근사값을 보는 듯한 느낌이나, 얘는 실제로는 소수와는 수학적으로 아무런 관련이 없는 놈이다.

n에 대해서 f(n)의 값을 구하는 건 다이나믹 프로그래밍으로 해결 가능하다. 피보나치 수열 구하는 것보다는 어렵고 꽤 재미있는 프로그래밍 excercise이므로 관심 있으신 분은 도전해도 좋다. 참고로 점화식 함수 내지 테이블은 보기와는 달리 1변수로는 안 되고 2변수 형태로 짜야 한다.

Posted by 사무엘

* 꽤 오래 전인 블로그 개설 초창기에 썼던 글을 리메이크 한 것이다.

옛날에 컴퓨터 학원에서 GWBASIC을 중급이나 고급까지 공부해 본 분이라면, 마지막 단원인 그래픽을 공부하면서 이런 비슷한 그림을 하나 그려 본 추억 정도는 있을 것이다.
그리는 방법은 간단하다. 세로줄을 하나 그은 뒤, 그 선의 윗점은 아래로 n만치 낮추고 아랫점은 오른쪽으로 동일한 n만치 옮겨서 선을 긋기를 반복하면 된다. 세로줄이 완전히 가로줄로 바뀔 때까지.

그 단순함에 비해서 생긴 결과물은 꽤 '컴퓨터그래픽스럽고' 뭔가 멋지다는 느낌이 들지 않는지?

그런데 여기서 의문이 생긴다.
저런 식으로 선을 한없이 많이 그어 나갈 때, 가장자리에 형성되는 저 둥그런 곡선은 수학적으로 어떤 의미를 갖는 곡선으로 수렴하게 될까? (그림에서 붉은 곡선) 편의상 선을 (0,0)-(0,1)에서 (0,0)-(1,0)까지 긋는 상황을 가정한다면 어떤 곡선이 그려질까? 이거 굉장히 재미있는 문제이다.

x축 (a, 0)와 y축 (0, b)를 지나는 직선의 그래프는 y = -(b/a)*x + b 이며 이건 중학교 수준으로도 알 수 있는 사실이다.
이 그림에서는 0~1 사이의 a에 대해서 (a, 0)과 (0, 1-a) 사이를 지나는 직선이 만들어지므로 방정식은 y = -((1-a)/a)*x + (1-a)가 된다. 이 식을 [1]이라고 설정하자.

그러면 이 a 지점에서 그어진 직선은 우리가 구하고자 하는 미지의 곡선에서는 어느 지점과 만나게 될까? 이걸 생각하는 게 문제를 푸는 열쇠이다.
a 지점에서 그어진 직선이 곡선의 표면에 닿는 지점은 바로.. 그 직선의 바로 극소량 떨어진 옆에 있는 또 다른 직선과의 교점일 것이다. 극한이라는 개념이 필요해진다.

a 지점에서 x축과 y축이 b만치 극미량 전진하여 (a+b, 0)과 (0, 1-a-b)를 지나는 직선의 방정식은 y = -((1-a-b)/(a+b))*x + (1-a-b) 가 된다. 이 식을 [2]라고 한다.
두 직선 [1]과 [2]의 교점을 구하려면 두 식을 연립해서 x, y에 대해서 방정식을 풀면 된다.
그럼 x=a*(a+b), y=(a-1)*(a-1+b)가 나온다.

b가 0에 한없이 가까워져서 두 직선이 근접하게 되면 교점은 결국 (a^2, (a-1)^2)라고 a에 대한 매개변수식으로 귀착된다. 곡선의 궤적이 이렇게 다 구해진 것이다. 게다가 문제 접근 방식의 특성상, x=a^2인 지점에서 곡선의 기울기도 -((1-a)/a)라고 딱 구해졌다.
x의 매개변수식이 a^2이니 (a-1)^2에다가 루트만 씌우면 끝나고, 그리고 기울기의 부정적분을 구해서 f(0)일 때 1이 나오는 상수 C를 덧붙여 줘도 게임 끝이다.

곡선의 방정식은 x-2*sqrt(x)+1, 또는 y = (1 - sqrt(x))^2 이 된다. 오옷~~~ 비슷한 4사분원의 방정식과 비교했을 때 근호와 제곱의 위치만 싹 맞바뀐 형태라는 게 흥미롭다.
이 정도 문제는 난이도가 고등학교 교과 수준이거나 좀 아슬아슬하게 넘는 수준일 것 같다.
임의의 지점에서 기울기가 저렇게 결정되는 곡선을 구한다는 특성상, 제일 확실하게 푸는 방법은 미분 방정식을 동원하는 것이겠지만.. 그 정도면 확실하게 고등학교 수준은 아니다.

곡선의 식이 정확하게 나왔으니 곡선의 성질도 다 알 수 있다. 저 선들이 차지하는 면적은 1/6이 된다(0부터 1까지 식을 적분한 값). 곡선과 y = x와의 교점, 다시 말해 곡선의 기울기가 정확하게 -1이 되는 지점이며 곡선 내부에 존재할 수 있는 가장 큰 정사각형의 한 변 길이는 1/4임을 알 수 있다.

그리고 또 하나 짚고 넘어갈 점이 있다.
위의 그림에서 빨간 곡선은 내가 손으로 그었을 리는 없고.. 어떻게 그린 걸까?
(a^2, (a-1)^2)라는 궤적은 베지어 곡선의 한 형태이다. 근사가 아니라 2차 베지어 곡선과 수학적으로 완벽하게 일치한다.

시작점 P0, 제어점 P1, 끝점 P2로 이뤄진 2차 베지어 곡선의 식은 (1-t)^2*P0 + 2*t*(1-t)*P1 + t^2*P2 (0<=t<=1)이다.
참고로 임의의 n차 곡선의 식은 각 항의 계수가 1, 3, 3, 1 등 이항정리 계수의 형태로 변하면서 t의 거듭제곱은 증가하고, (1-t)의 거듭제곱은 감소하는 형태로 생성된다.
저 식을 점들의 좌표가 아니라 t에 대해서 풀면 (P0 - 2*P1 +P2)*t^2 + (2*P1 - 2*P0)*t + P0 이 남는다.

문제의 곡선의 매개변수 식을 보면 x축은 a^2로, 2차항 t^2의 계수만 1이고 나머지는 0이다[1, 0, 0]. 따라서 P0은 답정너 0이 되어야 함. 일차항도 P0이 0으로 소거되고 없으면서 전체 계수가 0이 돼야 하므로 P1 역시 0이 된다.
한편, 이차항은 P0과 P1이 모두 0인 상태에서 계수가 1이 돼야 하므로 혼자 남은 P2는 0이 된다. P0, P1, P2의 x축 좌표는 각각 (0, 0, 1)로 정해졌다.

y축으로 가 보면, (a-1)^2는 a^2 - 2*a + 1이므로 맞춰야 하는 계수는 [1, -2, 1]이 됐다. 이로써 상수항 P0은 1부터 시작한다. 그 다음으로 2*P1 - 2*P0이 -2가 되어야 하는데 P0이 이미 1이라면.. P1은 0이 돼야 0-2 = -2가 될 수 있다.
P0도 값이 자동으로 정해진다. P0 - 2*P1 + P2 = 1이어야 하고, P0이 1이므로 P1뿐만 아니라 P2도 0으로 결정된다. P0, P1, P2의 y축 좌표는 각각 (1, 0, 0)이 된다.

이게 무슨 뜻인가? (a^2, (a-1)^2) 매개변수 곡선은 시작점 (0, 1), 제어점 (0, 0), 끝점 (1,0)인 아주 기초적인 2차 베지어 곡선과 동일하다는 얘기이다. 아니 그러고 보니, 베지어 곡선을 수식이 아니라 직관적으로 그리는 방법 중에도 한 선분을 저 그림과 비슷한 방식으로 다른 선분으로 점진적으로 변화시켜서 그 궤적을 연결하는 게 있었다. 심오함이 끝이 없구나..!

보통 그래픽 프로그램에서는 제어점을 2개를 둬서 2차보다는 더 범용적인 3차 베지어 곡선을 지원하는데, 3차 베지어 곡선의 표현력은 당연히 2차 곡선의 그것의 상위 호환이다.
3차 베지어 곡선의 방정식을 역시나 t 변수에 대해서 나타낸 뒤 2차 베지어 전개식과 계수가 일치하도록 방정식을 풀어 보면.. 시작점 P0과 P2는 동일하고 중간점이 P1일 때,
C1 = (2*P1+P0)/3 , C2 = (2*P1+P2)/3
이라는 식이 나온다. 이렇게 두 중간점을 잡아 주면, 3차 베지어 곡선으로 2차 베지어 곡선을 정확하게 나타낼 수 있다.

베지어 곡선으로 수학적으로 100% 완벽하게 표현할 수 없는 유명 요소가 두 가지가 있는데.. 하나는 원/원호이고 다른 하나는 다른 베지어 곡선과 굵기만 다르면서 평행한 파생 곡선이다. 쉽게 말해서 철도 선로의 한 곡선 궤조에 대응하는 다른쪽 궤조 말이다.
그에 반해 저렇게 직선을 찍찍 그어서 자연스럽게 만들어진 곡선 궤적은 매개변수로 표현하나 일변수 형태로 표현하나 식이 딱 구해지고 초월함수 그딴 거도 안 나오고 부정적분도 구해지고.. 마음대로 요리가 되는 게 좋다.

사이클로이드(최단 강하 궤적)라든가 현수선 같은 곡선 문제도 수학 해석적 관점에서 아주 재미있는 주제인데 이것도 나중에 다룰 기회가 있으면 좋겠다.
이 글은 5년 전에 썼던 오리지널에 비해 베지어 곡선 얘기도 들어가고 그림도 GDI가 아닌 GDI+의 앤티앨리어싱이 들어간 것으로 바꾸는 등 내용의 품질을 대폭 향상시켰다. ^^

Posted by 사무엘

※ 이 글의 내용은 예전에 썼던 <확률과 조합에서 발견한 자연대수 e>와 <원에 대한 적분 외>의 연장선상에 있다.

1차원 선에서 0부터 1까지의 선분의 길이는 두 말할 나위 없이 1이다.
2차원 공간에서 원점, (1,0), (0,1)을 지나는 이등변삼각형의 넓이는 1의 절반인 1/2이다.
이를 더 확장해서 3차원 공간에서 원점과 (1,0,0), (0,1,0), (0,0,1)을 꼭지점으로 갖는 사면체의 부피는 1/6이다.
이를 일반화해서 n차원 적분을 생각해 보면, 차원이 하나 올라갈 때마다 n차원 축을 한 칸씩만 점유하는 초입방체의 부피는 1/(n!)로 팩토리얼의 역수가 되고,  전체 초면체와의 비는 기하급수적으로 감소한다는 걸 알 수 있다. x^n의 부정적분은 (x^(n+1)) / (n+1) + C이다.

한편, 한 변의 길이가 2인 정사각형의 넓이는 4이고, 그 안에 들어가는 반지름이 1인 원의 넓이는 잘 알다시피 pi이다. 원과 사각형의 넓의 비는 pi/4, 즉 78.5% 정도 된다.
이를 공간으로 확장하면 한 변의 길이가 2인 정육면체의 부피는 8이고, 그 안에 들어가는 반지름이 1인 구의 부피는 4*pi/3이다. 구와 정육면체의 부피 비율은 pi/6 (약 52.3%)으로, 넓이일 때보다 비율이 더 작아진다. 이 비율 역시 차원이 증가할수록 더욱 작아진다는 것은 두 말할 나위가 없을 것이다.

그럼 혹시 4차원, 5차원, n차원 초구의 부피를 구할 수도 있지 않을까? 몰론 있다.
원의 방정식의 핵심이라 할 수 있는 f(x) = sqrt( r^2 - x^2 ) 라는 함수를 먼저 정의하자. 얘는 x가 0에서 r로 갈 때 임의의 구간에서 원의 높이를 나타내는, 즉 '둥긂'을 수학적으로 기술하는 함수이니까 말이다.

반지름이 r인 원의 넓이는 잘 알다시피 int( 2*f(x), x=-r..r) 로 나타내어지며 pi*r^2이라는 유명한 공식이 나온다.

그럼 반지름이 r인 구의 부피는 pi*r^2에서 r 대신 f(x)를 다시 집어넣어서 적분을 하면 된다.
int(pi*f(x)^2, x=-r..r) 가 (4/3)*pi*r^3이 된다.

4차원부터도 동일한 방식으로 적분을 계속하면 된다. 수많은 구들이 4차원에 있는 원 표면의 높이 변화량만치 연속적으로 쌓여 있는 것이므로.. 저 r 대신에 또 f(x)를 집어넣으면
int(4*pi*f(x)^3/3, x=-r..r) 은 드디어 파이까지도 제곱이 되어 4차원 초구의 부피는 (1/2)* pi^2 * r^4가 나온다. 한 변의 길이가 2인 4차원 초정육면체와의 부피 비율은 약 30.8%대로 곤두박질친다.

5차원 초구는? int( pi^2 * f(x)^4 / 2, x=-r..r)의 결과는 (8/15) * pi^2 * r^5 (약 16.4%)
6차원 초구는 pi^3 * r^6 / 6 (약 8%)가 된다. 사면체의 부피만큼이나 이것도 비율이 갈수록 곤두박질친다.
요렇게 비율이 한데 수렴하고 특히 짝수차일 때와 홀수차일 때 번갈아가며 무슨 특성이 발견되는 건 리만 제타 함수의 값하고도 비슷해 보인다. 게다가 리만 제타 함수도 n이 짝수일 때는 나름 pi^n의 유리수배가 되기도 하니, 반지름 길이가 1인 n차원 초구의 부피하고도 비록 수학적 의미는 딴판일지언정 좀 비슷해 보이는 구석이 있다.

수학 전공자 중에는 위의 적분들을 직접 손으로 푸는 용자도 있다. 그나마 짝수 승일 때는 루트가 없어지기 때문에 계산이 더 쉬워지는 편. 난 차마 손으로 풀어 볼 시간이나 자신은 없어서 그냥 수학 패키지를 돌려서 답을 구했다.
딱 보면 알겠지만 식에는 규칙성이 있다. 홀수승일 때와 짝수승일 때를 따로 생각해서 각각 차수가 2씩 증가할 때마다 pi에 붙는 제곱도 1씩 증가하고 계수는 2/n씩 증가한다고 보면 정확하다. 짝수승일 때는 1/2 (4차원), 1/24 (6차원)처럼 상수 계수가 1/n!으로 깔끔하게 증가하는 반면, 홀수승일 때는 계수가 좀 복잡하게 올라간다.

울트라 초천재가 아니고서야 4차원이 넘어가는 초구의 존재를 인간의 머리로 제대로 상상하고 실감하기는 거의 불가능할 것이다. '넘사벽'이라는 말이 괜히 있는 게 아니다~!
눈과 귀로 직감할 수 없는 차원이라는 게 신앙의 영역에 있다면, 이해가 안 되더라도 말 그대로 믿음으로 받아들일 수밖에 없을 것이다. 그러나 수학은 그런 게 아니라 고도의 논리와 이성의 영역에 있다.

아쉬운 대로 고차원 공간을 시뮬레이션 할 수 있는 방법은 프로그램을 작성하는 것이다. 다음 코드는 n차원 공간을 -1부터 1까지 점을 순서대로 마구 찍은 뒤, 원점으로부터 거리가 1 이내인 점의 개수를 세서 부피 비율을 구한다. 깔끔한 재귀호출 대신 사용자 정의 스택으로 구현했다.

double GetVolume(int dim, double delta)
{
    double buf[8], vl; int pos=0, i;
    double initv=-1.0-delta;
    __int64 x=0,y=0; buf[0]=initv;
    while(pos>=0) {
        if(pos==dim) {
            for(vl=0, i=0; i<dim; i++) {
                vl+=buf[i]*buf[i]; if(vl>1.0) break;
            }
            if(i==dim) ++x; ++y; --pos; //1 이내에 들면.
        }
        else {
            buf[pos+1]=initv;
            if( (buf[pos]+=delta) > 1.0) --pos; else pos++;
        }
    }
    return (double)x/y;
}

그래서 이렇게 찍으면 결과는 다음과 같이 나온다.

printf("%f\n", GetVolume(2, 0.01)); //0.785075
printf("%f\n", GetVolume(3, 0.01)); //0.523467
printf("%f\n", GetVolume(4, 0.03)); //0.302340
printf("%f\n", GetVolume(5, 0.05)); //0.164649

처음엔 -1부터 1까지 0.01씩 움직이니까 200등분을 했지만 4차원과 5차원으로 갈수록 66등분, 40등분으로 간격을 늘린 이유는.. 당연히 4승, 5승으로 급격히 증가하는 계산량을 감당할 수 없기 때문이다. 그래서 2차원과 3차원은 값이 상당히 정확히 나온 반면, 4차원과 5차원은 오차가 좀 큰 편이다.
그래도 계산이 워낙 단순무식하고 간단하므로 OpenMP 지시자를 집어넣거나 직접 손으로 코드 차원에서 스레드를 강제 분배하든가 해서 멀티코어+병렬화 최적화로 계산 속도를 몇 배 정도 끌어올릴 여지는 존재한다.

사실은 4차원 이상으로 갈 필요도 없이, 3차원 공간에 구가 여러 개 포개어져 있는 장면을 상상하는 것도 쉽지 않다.
학교 수학 시간에 집합 사이의 bool 관계를 구하는 문제에서 집합의 개수는 3개를 넘어간 적이 없었다. 왜냐하면 2차원 평면에서 집합들의 모든 소속 가짓수를 벤 다이어그램으로 그릴 수 있는 한계가 3개이고 2^3, 총 8가지 가짓수이기 때문이다.

그러나 3차원 공간에서 구를 4개 포개어서 입체 벤 다이어그램을 그리면 16가지 가능성을 모두 표현할 수 있다. 구 3개가 8가지 가짓수를 만들고, 거기에 위에다 4개의 구를 적당히 겹쳐 놓으면 8개에다가 넷째 구와 겹치는 놈 8가지가 또 추가되어서 16개가 되니까 말이다. 이 역시 코드로 작성해서 무식하게 확인하면 다음과 같다.

struct SPHERE { double x,y,z; };
const SPHERE fp[4]={
    {0,0,0},
    {0.4,0,0},
    {0.2,0.4,0},
    {0.2,0.2,1.5}
};
auto Square = [](double x) { return x*x; };
SPHERE d;
bool bitfl[16]={false,};
for(d.x=-1; d.x<=1.5; d.x+=0.02)
    for(d.y=-1; d.y<=1.5; d.y+=0.02)
        for(d.z=-1; d.z<=1.5; d.z+=0.02) {
            int bt=0;
            for(int i=0; i<4; i++)
                if( Square(fp[i].x-d.x)+Square(fp[i].y-d.y)+Square(fp[i].z-d.z) <=1) bt|=(1<<i);
            bitfl[bt] = true;
        }
for each(int n in bitfl)
    printf("%d ", n);

반지름은 모두 1이고, (0,0,0), (0.4,0,0), (0.2,0.4,0), (0.2,0.2,1.5)인 4개의 구를 설정한다. 그리고 -1부터 1.5까지 0.02 간격으로 뺑뺑이를 돌려서.. 각 점별로 자기가 속하는 구의 번호에 해당하는 2진수 비트들(8+4+2+1)의 합을 구한다. 그 뒤 그 합에 해당하는 플래그를 켠다.

나중에 플래그의 값을 출력해 보면 모든 비트들이 1로 바뀌었음을 알 수 있다. 즉, 어느 구에도 속하지 않은 놈, 모든 구에 속한 놈, 1, 3, 4번 구에만 속한 놈, 2, 3번 구에만 속한 놈 등등 16가지 가능성이 실제로 모두 존재한다는 뜻이다. 어찌 보면 당연한 얘기이다. 그 반면 구가 5개를 넘어가면 그 32, 64가지 가능성을 한꺼번에 3차원에서 표현할 수는 없게 된다.

반지름이 수십~수백 정도에 달하는 충분히 큰 구의 복셀의 표면을 보는 느낌은 어떨까 문득 궁금해진다.
수학 패키지 소프트웨어들은 3차원 음함수의 그래프를 아무래도 폴리곤+와이어프레임 형태로 근사해서 보여 줄 것이다. 하지만 곡선/곡면을 폴리곤이 아니라 아예 계단현상을 볼 수 있는 복셀로 근사해서 보면 또 느낌이 굉장히 이색적일 것 같다.

표면에는 역시나 원들 무늬가 그러져 있구나!
앞서 보다시피 5차원~6차원 이상으로 가면 단순무식하게 점을 때려박는 것도 계산이 너무 많아서 도저히 감당할 수 없다.
이럴 때 정확한 초구의 부피를 구할 수 있는 건 역시나 수학 해석적인 방법이라는 것을 알 수 있다.
미분 내지 역함수인 부정적분을 할 때 변수의 차수와 계수가 왜 저렇게 변하는지는 다항함수의 차이 극한값을 구해 보면 알 수 있다. 극한부터 시작해서 미분· 적분이라는 개념을 생각해 낸 건 정말 위대한 발견인 것 같다.

Posted by 사무엘

1. 평행사변형의 넓이, 평행육면체의 부피

2*2 크기의
(a b)
(c d)
행렬이 있을 때, 이 행렬의 행렬식이라고 불리는 D 값은 a*d - b*c로 정의된다. ax+by = 얼마, cx+dy = 얼마 요런 방정식의 근을 구하는 식을 세워 보면 행렬식은 x, y의 분모에 들어가 있다. 그러니 이 값이 0이면 근은 부정이나 불능으로 빠지게 된다.

한편, 행렬식에는 기하학적인 의미가 있다. 원점에서 (a,b)를 잇는 선분이 가로변, 원점에서 (c,d)를 잇는 선분이 세로변인 평행사변형의 넓이를 나타내기 때문이다.

그도 그럴 것이 이 행렬은 한 변의 길이가 1인 (0,0), (1,0), (1,1), (0,1)이라는 정사각형을 (a,b), (a+c, b+d), (c,d)라는 평행사변형으로 옮긴다. (a+b)*(c+d)라는 전체 직사각형에다가 주변의 합동인 삼각형 두 쌍의 넓이를 빼면, 평행사변형의 넓이로 남는 것은 ad-bc뿐이다. 아래 그림을 보시라.

(a+c)(b+d) - b(a+c) - c(b+d) = d(a+c) - c(b+d) = ad + cd - bc - cd = ad-bc

이 평행사변형에서 대각선을 구성하는 (a,b)와 (c,d)를 연결하면 사각형을 반으로 쪼갤 수 있다. 다시 말해 원점과 (a,b), (c,d)를 꼭지점으로 하는 삼각형의 넓이는 ad-bc의 절반이 된다.

다음으로..
저렇게 두 점 A(ax, ay)와 B(bx, by)가 있을 때, A-원점-B 자취의 방향을 판단하는 공식이 있다(시계 방향인지 반시계 방향인지). bx*ay - by*ax이며, 여기에는 배후에 삼각함수 sin( alpha-beta )가 숨어 있다.

그런데 위의 두 점 (a,b), (c,d)도 코싸인/싸인 alpha와 코싸인/싸인 beta라는 극좌표 형태로 표현하면, 행렬식 a*d-b*c 역시 결국은 sin( alpha-beta )과 패턴이 동일함을 발견할 수 있다. 두 쌍의 숫자를 각각 서로 엇갈리게 곱해서 빼는 것 말이다.
이렇듯, 행렬식에 두 벡터의 사잇각에 대한 삼각함수 값이 들어있으니, 벡터의 길이만 정규화하면 각도를 구할 수 있다. 또한 두 변의 길이와 그 사이의 끼인각을 알고 있는 삼각형의 넓이는 A*B*sin(theta)/2로 간단하게 결정된다.

그리고 이 식을 확장하면 삼각형뿐만이 아니라 여러 삼각형들로 분해 가능한 단순다각형(선분들이 서로 만나지만 않으며 볼록하거나 오목할 수 있음) 넓이 내지 폴리곤 패스 방향을 구할 수도 있다. 넓이와 방향(넓이의 부호)이 같이 구해진다.

2차원에서는 이 정도로 분석이 되고, 3차원으로 가면 어떨까?
짐작했겠지만 3*3 행렬의 행렬식은 그 행렬을 구성하는 3개의 벡터들을 축 내지 기저로 삼는 평행육면체의 부피와 같다. 직교좌표에서 모든 점들의 최대치에 해당하는 직육면체의 부피에다가 또 모서리 주변의 온갖 사면체들의 부피를 빼야 하니 식이 굉장히 복잡할 것이다. 3*3 행렬의 행렬식이 항이 6개나 되고 2*2의 것보다 훨씬 더 복잡한 것은 이 때문이다.

하지만 3차원에서도 언제나 부피만 구하는 건 아니다.
차원만 2차원이 아닌 3차원으로 확장한 뒤, 원점에서 출발하는 두 벡터를 가로변 세로변 축으로 삼는 평행사변형의 넓이는 어떻게 구하면 좋을까? (삼각형의 넓이도 당연히 자동으로 포함) 즉, 3차원 공간 안에서의 2차원 평면인 것이다. 이건 2*2 행렬식보다는 어렵겠지만 3*3 행렬식보다는 쉬울 것이다.

그리고 이것이 바로 벡터의 '외적'(벡터곱) 연산이 하는 일이다. 아마 고등학교에서는 내적까지만 하지 외적은 안 배우지 싶다. 단, 내적부터 먼저 개념을 좀 복습해 보자.

2. 벡터의 내적

왜 각 성분을 차례대로 곱한 것을 더하면 내적이 나오는 걸까?
이 원리의 배후에는 코싸인 제2법칙이 있다.
아까 두 변의 길이(두 선분의 길이를 각각 A와 B라 하자)와 그 사이의 끼인각을 아는 삼각형의 넓이를 구했는데, 이 경우 삼각형이 유일하게 결정되었으므로 나머지 한 변의 '길이' C도 당연히 구할 수 있다. 그 삼각형의 모든 특성이 파악 가능한 것이다. C^2 = A^2 + B^2 - 2*A*B*cos(theta) 이다.

이건 피타고라스의 정리의 일반적인 경우이며, 증명하는 방법이 상당히 많다. 여기에서는 제일 직관적인 해석학적 방법 하나만 소개하고 넘어가겠다.
선분 A와 B가 원점을 지나고 선분 A는 x 축에 평행하다고 한다면 선분 A는 (0,0)과 (a,0)을 지나게 될 것이며, 0도인 선분 A로부터 theta도만치 떨어진 선분 B는 선분 B는 (0,0)과 (b*cos(theta), b*sin(theta))를 지난다. 임의의 차원의 임의의 위치에 있는 어떤 삼각형 ABC라도 변환을 통해 그렇게 2차원 평면에서의 일반화가 가능하기 때문이다.

그럼 선분 C의 길이는 저 (a,0)과 (b*cos(theta), b*sin(theta)) 사이의 거리와 같다. 그러므로 길이의 제곱은 (a - b*cos(theta)^2 + (b*sin(theta))^2 가 된다.
이 식을 풀면 a^2 - 2*a*b*cos(theta) + b^2*cos(theta)^2 + b^2*sin(theta)^2 가 된다.
b^2항은 cos(theta)^2 + sin(theta)^2 이므로 1로 약분돼 없어지고, 결국 코싸인 제2제곱 공식이 고스란히 나온다.

그럼, A, B, C를 이제 벡터라고 생각하고 2차원이 아니라 각 축별 좌표를 코싸인 제2제곱 공식에다 대입해 보자.
A=(a1,...,an), B=(b1,...,bn) 같은 식이다. C는 두 벡터의 차이 A-B와 같다.
벡터의 절대값의 제곱은 잘 알다시피 거리의 제곱과 같기 때문에 각 성분들의 제곱을 모두 더한 것과 같다. 그러므로

∑ [i=1..n] (ai^2 + bi^2 - 2*ai*bi) = ( ∑ [i=1..n] (ai^2 + bi^2) ) - 2*A*B*cos(theta) 로 식이 대충 떨어진다.

A와 B에서 각 성분들의 제곱을 합을 구하는 부분은 좌우변 공통이므로 소거되고.. 남는 것은
2*A*B*cos(theta) = ∑ [i=1..n] 2*ai*bi 이다. 여기서 양변을 2로 나눠 주면 내적 공식이 아주 깔끔하게 유도된다. 콜?

벡터의 내적은 그냥 숫자 하나(스칼라)만으로 답이 떨어지며, 벡터의 각 성분들을 차례대로 곱해서 더하기만 하면 된다. 내적에는 두 벡터의 사이각의 '코싸인' 값이 들어있기 때문에, 두 벡터가 서로 수직인지를 벡터의 길이와 무관하게(= 정규화 안 하고도) 간편하게 판별할 수 있다. 코싸인 90도는 0이므로!

내적은 계산이 딱히 어렵지 않을 뿐만 아니라, 2차원이고 3차원이고 어느 차원이든지간에 계산법이 동일하다는 것도 큰 장점이다. 두 벡터의 사이각을 구하는 용도로는 완전 딱이다. cos(alpha-beta) = cos(alpha) cos(beta) + sin(alpha) sin(beta) 인 것에도 2차원일 때의 내적 공식이 숨어 있다는 걸 발견할 수 있다.
또한, 생긴 모양 덕분에 벡터의 내적을 행벡터(행이 하나. 수평선-_-)와 열벡터(열이 하나. 수직선)의 곱으로 표기하기도 한다. (행과 열뿐만이 아니라 횡과 종도 어느 게 어느 건지 종종 헷갈릴 때가 있다만..;;)

3. 벡터의 외적

그에 반해 외적은 결과값도 벡터이다. 그리고 3차원일 때에만 정의된다. 계산값의 각 차원과 피연산자들이 일대일로 딱 밀착해 있는 관계로 3차원 말고는 선택의 여지가 없기 때문이다.

성분이 (a1,a2,a3)인 벡터 A와, 성분이 (b1,b2,b3)인 벡터 B의 외적은
(a2*b3-a3*b2, a3*b1-a1*b3, a1*b2-a2*b1)이라고 정의된다.
어 그런데 이거, 두 쌍의 숫자를 각각 서로 엇갈리게 곱해서 빼는 게 2*2 행렬식을 구하는 것과 비슷해 보인다. 맞다.
그래서 벡터 A, B가 동일 평면상에 있어서 a3와 b3 같은 게 동시에 0이기라도 하면, 해당 변수가 포함된 항은 모두 소거된다. 이 경우 외적은 그냥 2*2 행렬식과 동일해진다.

또 생각할 점은.. 3*3 행렬식을 구하는 것도 특정 row와 col을 제외한 2*2 행렬식을 구하는 것의 연속이라는 점이다. 그래서 외적 구하는 공식을
(i  j  k )
(a1 a2 a3)
(b1 b2 b3)

의 행렬식이라고 표현하기도 한다. 물론 여기서 i~k는 스칼라값이 아니라 각각 (1,0,0), (0,1,0), (0,0,1)에 해당하는 단위벡터이다. 그러니 스칼라와 벡터가 뒤섞여 있는 저 행렬은 대수적인 의미는 딱히 없다. 외적 구하는 공식을 좀 더 뽀대나게 표현하는 용도로만 쓰이는 셔틀일 뿐이다. 그래도 결국은 3*3 행렬식과 닮긴 닮았다.

행렬식을 구하는 공식에서 j에 해당하는 부분은 더하는 게 아니라 뺀다. 그렇기 때문에 외적 공식에서는 1,3이 아니라 3,1 순서로 쓴 뒤에 더하는 것으로.. 다시 말해 양수를 빼는 게 아니라 음수를 더한다고 표현을 달리 했다. 둘 다 동일한 의미이므로 부호에 주의하기 바란다.

벡터는 스칼라와는 달리 '크기'뿐만 아니라 '방향'이라는 정보가 추가로 들어있다.
외적 연산을 통해 구해진 벡터는 일단 크기는 두 벡터의 크기의 곱에다가 사잇각의 sin값을 곱한 것과 같다. 그러므로 3차원 공간에서 두 3차원 벡터가 만드는 평행사변형/삼각형의 넓이를 구할 수 있다.

외적 식을 전개해서 크기의 제곱을 해 보면, 각각의 두 벡터의 크기의 제곱을 곱하고 거기에다 벡터의 내적값(양 벡터의 각 성분들을 서로 곱해서 더함)의 제곱을 뺀 것과 같다고 식이 전개된다. A^2 - B^2 꼴이 되기 때문에 (A+B)(A-B)로 인수분해를 하고 싶은 충동이 느껴지지만 여기서는 식을 다른 형태로 바꿔야 된다.

내적에는 역시 두 벡터의 크기의 곱에다가 사잇각의 cos이 들어 있으니 이것의 제곱이라면 두 항이 결국 |A|^2 * |B|^2를 공통으로 갖고 있고 (1  - cos^2 )가 남는다. 그리고 이것이 sin^2과 같다는 건 두 말하면 잔소리이고.

외적의 크기에 벌써 이렇게 유용한 정보가 들어있는데, 방향은 더욱 흥미롭다.
짐작하겠지만 두 벡터의 외적의 방향은 두 벡터와 수직이다. 물론 위쪽도 수직이고 아래쪽도 수직인데, 해당 좌표계의 동일 부호가 향하는 쪽으로 방향이 결정된다. 두 기저 벡터에 대한 외적을 구하면 나머지 기저 벡터가 튀어나온다.

애초에 두 벡터의 외적은 그 두 벡터와의 내적이 모두 0인 벡터 중에 크기가 저렇게 AB sin(theta)로 나오는 놈을 구한 것이다. a1*c1 + a2*c2 + a3*c3 = 0과 b1*c1 + b2*c2 + b3*c3 = 0을 만족하는 (c1,c2,c3)을 직접 구해 보면 안다. 저것만으로는 식보다 미지수 개수가 더 많으니 (c1,c2,c3)가 하나로 딱 떨어지지 않고 c1과 c2가 c3의 배수인 것처럼 관계식만 나온다. 그런데 c3의 특정값일 때 c1,c2에 있던 분모가 싹 소거되고 c1~c3이 저렇게 아주 대칭적이고 깔끔하게 나오는데 그게 바로 외적값이다.

이런 유용함 때문에 외적이 3차원에서의 전유물이라고 여겨지는 것이다. 이항연산에 딱 최적화돼 있지 않은가.
물론, 외적은 수직이라는 게 위아래가 모두 존재한다는 특성상 교환 법칙이 성립하지 않고 A×B=-B×A이다. 뭐, 4차원 이상에서는 두 벡터와의 내적이 모두 0인 벡터는 3차원일 때처럼 일직선상의 형태로 유일하게 떨어지지가 않는다. 그러니 외적과 같은 접근 방식이 큰 의미가 없어져 버린다.

끝으로, 3차원에서 벡터의 내적과 외적은 삼중곱이라는 연산을 통해 한데 만난다. 3개의 벡터 A,B,C를 축으로 하는 평행육면체의 부피를 구하고 싶으면 아까처럼 벡터들을 3차원 행렬의 행렬식으로 표현해도 되지만, 밑면에 속하는 두 벡터 A×B의 외적을 구한 뒤 거기에다 C와 내적을 구하면 된다. (A×B)·C! 그게 결과적으로 행렬식을 구한 것과 같은 계산 결과가 도출된다. 왜 그런지는 아까 그 외적 구하는 행렬과 일반 행렬의 행렬식을 늘어놓고, 거기에다가 내적을 구하는 공식까지 적용한 뒤 서로 비교하며 생각해 보면 된다.

Posted by 사무엘

sin 1°는 어떤 무리수일까?

답부터 말하자면, sin 1도는 일반적인 통념과는 달리 초월수가 아니다. 이는 임의의 정수 각도도 마찬가지이다.
유한 번의 사칙연산과 거듭제곱/제곱근으로 표현 가능한 대수적 수라는 뜻이다. (사실, π나 e 같은 초월수도 사칙연산· 거듭제곱· 근호의 꼴로 나타낼 수 있다. 단지 그게 무한히 반복되는 급수의 형태가 될 뿐이지..)

삼각함수는 삼각형을 이루는 두 변의 각도가 이러할 때 변의 길이를 비율이 어떻게 되는지를 나타내는 함수이다. 기하학에서는 그야말로 필수 중의 필수 도구이지만, 대수적으로는 직관적이지 않은 굉장히 기괴한 특성을 많이 지닌다. 그래서 학교에서 수포자를 양산하는 원흉이기도 하다.

삼각함수에다 일반 자연수나 유리수를 집어넣으면, 지수나 로그함수와 마찬가지로 우리가 의미를 알 수 없는 괴랄한 초월수가 함수값으로 튀어나온다. 그러나 pi의 유리수 n배 내지 1/n배에 속하는 각도에 대해서는 꼭 그렇지만은 않다. 이미 입력값인 pi부터가 대수적이지 않은 괴랄한 수여서 그런 게 아닐까 싶다.

먼저, 특수한 각도에 대해서는 함수값이 깔끔한 수 내지 심지어 유리수 범위로 떨어질 때가 있다. 특히 15 내지 30도 간격인 0, 30, 45, 60, 90도일 때 sin 값은 각각 sqrt(n)/2 (n은 0 이상 4 이하)로 딱 떨어진다. 가장 단순한 형태다.

여기에서 파생된 각, 다시 말해 레퍼런스 각의 n배나 절반, 1/3 따위에 해당하는 각은 위대하신 삼각함수의 덧셈 정리를 통해 cos/sin 값을 구할 수 있다. 덧셈 정리라는 게 당연히 대수적인 조작들만 있으므로 대수적인 수에 대수적인 조작을 하면 그 수도 대수적인 것은 당연지사. 정수 계수 대수방정식의 근이 될 수 있다.

그리고 15도 단위 계열뿐만 아니라 18도 단위에 계열에 대해서도 삼각함수는 비교적 간단한 형태의 값이 나온다. 세배각 공식이어서 원래는 3차 방정식을 풀어야 하지만 이 각도는 그나마 1차식과 2차식으로 인수분해되는 경우이기 때문이다.

이를 이용하면, 18도와 15도의 차인 sin 3도까지도 약간 복잡하지만 답이 나온다. (그림: 영문 위키백과)

하지만 정수 도에서 그나마 해피한 결과가 나오는 정밀도의 한계는 여기까지.
sin 1도 정도가 되면 유한한 사칙과 거듭제곱, 근호만으로 정확한 값을 묘사하는 게 불가능하지는 않으나 의미가 없어진다.
반복되는 패턴에 대한 매크로 치환을 하고도 항이 열몇 개에 달할 정도로, 정말 미치도록 복잡한 형태가 되기 때문이다.

3도 간격의 수로부터 1도 단위의 삼각함수 값을 구하려면 아까 18도의 경우처럼 각을 3등분을 해야 하는데 이제는 인수분해가 되지 않는다
얄짤없이 3차 방정식이 되며(삼각함수의 3배각 공식은 3차식!), 작도 불가능한 것으로도 잘 알려져 있다. 복잡함이란 본질적으로 이런 데서 유래되는 게 아닌가 싶다. 그냥 내 감이 그렇다는 뜻.

3차 방정식의 근의 공식은... 2차 방정식의 그것하고는 비교조차 할 수 없을 정도로 머리 터지게 복잡하다. 그래서 3차 방정식의 근인 sin 1도의 값도 끔찍하게 복잡한 형태로 산출되는 것이다.

* 끝으로 보너스.
arctan 1 + arctan 2 + arctan 3 = pi 임을 증명하시오.

arctan 1이야 45도의 특성상 pi/4가 되는 게 잘 알려져 있다만, 저런 관계는 도대체 어떻게 성립하는 걸까?
세 각도의 합이 180도라는 뜻이므로, 기울기가 1, 2, 3인 세 각은 일정 비율의 닮은 삼각형을 결정하는 각이 될 수 있음을 보이면 되겠다.

삼각형의 두 꼭지점의 각의 기울기(=탄젠트)가 x, y라면, 나머지 꼭지점의 각도는 기울기가 1/x인 각과 1/y인 각 두 개의 합으로 표현된다. (나머지 꼭지점에서 맞은편 변으로 수선을 내려 보면 직관적으로 이해됨)

그런데 삼각함수의 덧셈법칙에 따라
tan(a+b) = (tan(a)+tan(b)) / (1 - tan(a)*tan(b))
이므로.. 이 공식으로 두 탄젠트를 합성하면, 나머지 꼭지점의 탄젠트는

(y+x)/(x*y-1)로 표현될 수 있다.

x,y에 1,2를 넣으면 저 값은 3이 되고, 2,3을 넣으면 값은 1이, 1,3을 넣으면 값은 2가 된다. 사실, 식의 특성상 (x,y)->z만 성립하면 (x,z)->y와 (y,z)->x는 일일이 체크하지 않아도 자동으로 성립하긴 한다.
따라서 어떤 경우든 기울기가 1, 2, 3인 세 각은 닮은 삼각형을 결정하는 각이며, 그 합은 삼각형의 내각의 합인 180도, 즉 pi임을 알 수 있다.
내가 생각하는 것보다 더 간단하게 증명하는 방법도 물론 있을 것이다.

Posted by 사무엘

a*x + b*y + M = 0
c*x + d*y + N = 0

이라는 두 개의 이원(x, y) 일차방정식이 있다고 치자. 흔히 연립방정식이라고도 불린다.
이 방정식을 풀려면 x, y 중 하나의 계수를 a나 c, 아니면 b나 d로 맞춰 줘서 한 변수를 소거해야 한다. 그래서 일원 일차방정식으로 바꿔서 반대편 변수의 근을 구한 뒤, 그 값을 대입하여 원래 변수의 근까지 구하면 된다.

이를 일반화하여 위의 방정식의 '근의 공식'을 구하면 다음과 같다. 뭔가 규칙성이 있는 것 같으면서도 미묘하게 잘 안 외워진다.

x = (N*b-M*d) / (a*d-b*c)
y = (N*a-M*c) / (a*d-b*c)

분모를 보니 생각나는 게 없는가?
그렇다. 이것은

[ a b ]
[ c d ]

라는 원소로 구성된 2*2 정방행렬의 행렬식을 구하는 공식이다.
이 행렬식의 값이 0이라는 건 a:b와 c:d의 비율이 동일하다는 뜻이다. 따라서 이 행렬을 구성하는 벡터들은 서로 일차(선형) 독립을 이루지 못하며, 상수항이 어떻냐에 따라서 이 방정식은 근이 무수히 많거나 근이 존재하지 않게 된다.

이런 행렬을 거친 일차변환은 2차원 평면을 1차원 선이나 점으로 찌그러뜨린다. 이런 행렬은 영벡터(모든 원소의 값이 0)가 아닌 벡터 중에서도 자신과의 곱을 영벡터로 만드는 물건이 무수히 존재하게 된다(Ax=O).
예를 들어 연립방정식 x+2*y = 0 과 3*x+5*y = 0의 근은 x와 y가 모두 0인 trivial solution 단 하나밖에 없으나, x+2*y = 0과 3*x+6*y = 0은 두 식이 동치나 마찬가지이기 때문에 x = -2*y이기만 하면(가령 2와 -1) 식이 성립한다. non-trivial solution들이 존재한다는 뜻이다. 결국, 근이 무수히 많을 수 있다는 말과 본질적으로 동일하다.

이들은 모두 필요충분조건 관계에 있으며, 이외에도 이런 행렬의 엄밀한 특성에 대해서는 선형대수학 시간에 많이 배우게 된다.

말이 길어졌는데, 그럼 변수가 세 개 이상이 되면 근을 구하는 양상이 어떻게 바뀔까?
그야말로 폭발적으로 복잡해진다.

변수가 2개일 때는 x, y 근에 최대 두 변수의 곱(최대 2차)으로 이뤄진 항이 분자와 분모에 2개씩 있었다.
그러나 3개일 때는 세 변수의 곱으로 이뤄진 항이 분자와 분모에 6개씩 들어간다.
그리고 이를 일반화하면, n원 1차 연립방정식의 근은 n개의 변수의 곱으로 이뤄진 항이 분자와 분모에 무려 n! (팩토리얼)개씩 들어간다!
이것이 '폭발적'이라는 단어의 의미이다. 예를 들어,

[ a b c ]
[ d e f ]
[ g h i ]

라는 3*3 정방행렬의 행렬식은 다음과 같다. 어떤 규칙성이 있는지, 어떻게 하면 잘 외울 수 있겠는지 한번 생각해 보시라.;;

a*e*i - a*f*h - b*d*i + b*f*g + c*d*h - c*e*g

a가 속한 행과 열을 제낀 2*2 행렬(e f / h i)의 행렬식에다가 a를 곱해서 더하고,
다음으로 b가 속한 행과 열을 제낀 2*2 행렬(d f / g i)의 행렬식에다가 b를 곱해서 빼고,
끝으로 c가 속한 행과 열을 제낀 2*2 행렬(d e / g h)의 행렬식에다가 c를 곱해서 더하면.. 이 행렬 전체의 행렬식이 나오긴 한다. 2*2 행렬식이 2개의 항으로 구성돼 있는데 그런 식이 3개가 늘어나니 총 6개가 되는 게 맞다.

이런 방식으로 행렬을 쪼개면 그 어떤 크기의 행렬의 행렬식도 구할 수는 있다. 하지만 크기가 3을 넘어가는 행렬에 대해 행렬식 내지 방정식을 푸는 일반적인 공식을 구하려는 생각은 포기하는 게 좋다. 머리 터진다..;;

참고로 1변수 n차 방정식의 경우를 생각해 보자. 2차 방정식은 잘 알다시피 비교적 외우기 쉬운 근의 공식이 존재하는 반면 3차와 4차는 근의 공식이 있기는 하나 인간의 머리로 도저히 외울 수 없을 수 없을 정도로 미치도록 복잡한 형태이다. 게다가 서로 인접한 차수끼리 규칙성 같은 것도 아예 존재하지 않는다. 5차 이상부터는 대수적인 방법만으론 깔끔하게 풀 수조차 없다.
그에 반해 n변수 1차 연립방정식은 비록 그 정도로 카오틱하게 복잡한 건 아니지만, 그래도 좀 다른 양상으로 복잡해진다는 게 오묘한 점이다.

그리고, 이건 일반적인 공식을 구하려 할 때 딸려 나오는 식이 지수함수 급으로 복잡해진다는 소리다. 일반적인 경우가 아니라 그때 그때 특정 숫자가 주어진 행렬의 행렬식을 구하는 알고리즘의 시간 복잡도가 지수함수라거나 NP 완전 문제 급이라는 뜻은 아니다. 둘은 서로 다른 개념이다.

변수가 3개를 넘어가는 방정식은 어떻게 풀어야 할까?
가령, 변수가 x, y, z라고 치면 일단 모든 방정식의 x의 계수를 1이든, 맨 위의 식의 계수로든 어쨌든 하나로 일치시켜야 한다. “등식에서 같은 수를 더하거나 빼도 등식은 성립한다.” / “등식에서 같은 수를 곱해도 등식은 성립한다” 라고.. 초등학교 산수 시간에 배우는 지극히 당연하고 기본적인 원리를 이용해서 방정식을 푸는 것이다.

그렇게 해서 x 변수를 없는 놈 취급할 수 있게 만든 뒤, 다음 방정식에 대해서 y 변수의 계수를 일치시킨다.
이런 절차를 반복하여 변수를 z만 남겨서 z 값을 구하고, 다음으로 y, x의 순으로 재귀적으로 근을 구하면 된다.
행렬이라는 물건 자체가 이런 연립방정식을 푸는 동작을 간략하게 모델링하는 과정에서 고안되었다.
앞서 말한 절차를 행렬 용어로 표현하자면, 가우스-조던 소거법으로 행렬을 대각화하는 것과 같다.

행렬이 대각화가 되고 나면 방정식을 다 푼 것이나 다름없을 뿐만 아니라, 행렬식의 값은 그 행렬의 대각선 원소들의 곱으로 쉽게 구할 수 있게 된다.
행렬을 대각화하는 데 드는 시간 복잡도는 일반적으로 O(n^3)으로, 행렬 곱셈의 비용과 같다.
이 작업을 숫자를 대상으로 곧장 곧장 업데이트하는 게 아니라, 기호를 이용해서 일반적인 경우를 다 고려하여 표현하려다 보면 항 개수가 아까 같은 팩토리얼 급으로 증가하게 되는 것일 뿐이다.

연립방정식 하니까 응용수학 내지 산업/경영공학 같은 데서 다루는 그 이름도 유명한 선형 계획법(LP)이 생각난다.
이런 데서 다루는 문제는 대체로 변수의 개수가 식의 개수보다 더 많고, 식도 등식이 아니라 부등식이다. 애초에 해 자체는 무한히 많을 수밖에 없는데 그래프의 능선을 따라다니면서 주어진 조건을 최대한 만족하는 영역을 찾는 게 목적이다. 이런 문제는 실용적인 가치도 무진장 높다.

이런 걸 푸는 제일 간단한 알고리즘으로는 simplex method가 있는데, 그 이상의 디테일은 본인도 비전공자인 관계로 잘 모른다. 변수의 차원이 최대 2차원 정도일 때나 그래프를 그려서 생각할 수 있지, 이 역시 3차원 이상으로 가면 머리에 쥐 난다. 고등학교에서 행렬을 2*2까지밖에 다루지 않는 것, 그리고 전산학에서 간단한 bool 대수 연산을 다룰 때 변수를 3개까지밖에 넣지 않는 게 다 이유가 있어서 그런 것이다.

Posted by 사무엘

퇴근길에 문득 든 아주 기초 수학 생각이다.
아래 그림은 포물선 2개 x^2+2*x (x=-2..0), -x^2+2*x (x=0..2)와, sin(x*PI/2) (x=-2..2)를 한데 포개 놓은 것이다.
원래 sin, cos 부류의 삼각함수는 주기가 2*PI인데, 이를 4로 좁혀 놓았다.
이렇게 보니까 포물선도 싸인파 곡선과 형태가 생각보다 꽤 비슷해질 수 있다는 걸 느꼈다.

0부터 2까지 구간의 넓이를 정적분으로 구해 보면 이차함수인 포물선의 면적은 4/3인 반면, 진짜 싸인파의 면적은 4/PI이다. 즉, 포물선에 속하는 면적이 약간 더 크다.

그러나 이 두 곡선은 비슷하게 생겨도 그 본질은 굉장히 다르다. 미분을 해 보면 안다. 이들의 도함수를 그래프로 그리면 다음과 같다.

싸인파는 도함수도 기준 위치와 진폭만 다를 뿐, 여전히 전구간이 미분 가능한 매끄러운 싸인파이다.
그러나 두 포물선을 인위적으로 연결한 함수는 도함수가 직선으로 바뀌었고, x=0 지점은 연속이긴 하지만 기울기의 좌극한과 우극한의 값이 서로 달라서 미분이 불가능한 점이 되었다. 마치 절대값이 들어있는 일차함수처럼 된 셈이다.

이걸 또 미분하면 어떻게 될까?
싸인파는 역시 또 싸인파이지만 저 직선은 아예 양수 아니면 음수의 상수함수로 바뀌고, x=0 지점은 이제 연속이지도 않게 된다. 마치 인간이 만든 아무리 매끄럽고 뾰족한 바늘도 확대하고 또 확대해서 보면 울퉁불퉁한 표면이 드러나듯이 말이다.

우리가 자연에서 흔히 볼 수 있는 물체의 운동 양상은 관성에 의한 등속 직선, 아니면 힘을 한 쪽으로 균일하게 받는 포물선 형태가 있다. 하지만 출렁이는 물결이나 음파 같은 진동은 삼각함수에 속하는 싸인파가 자연스러운 움직임이다. 오히려, 포물선 두 개를 갖다붙인 것에 불과해서 미분하면 딱딱한 절대값 직선으로 바뀌어 버리는 곡선이야말로 인위적이고 부자연스러운 형태인 것이다.

왜 싸인파가 자연스러운 움직임일까?
삼각함수는 무한소나 무한대로 발산하지 않고 주기를 갖고 -1에서 1 사이를 한없이 진동만 한다.
그러면서도 전구간이 단절 없이 연속이고 미분 가능하다. 미분을 해도 심지어 도함수조차 형태를 바꾸면서 주기적으로 자기 자신으로 돌아오기를 반복하기 때문이다.
내가 수학적인 통찰력이 부족해서 그 원리를 다 '이해'와 '실감'은 못 하겠지만, 적어도 이런 함수는 돼야 정말 매끄러움의 본질을 수학적으로 표현한 게 아닌가 하는 막연한 추측까지는 한다.

해석학적으로 볼 때 x^n의 x에 관한 미분은 n*x^(n-1)로 떨어진다. 지수함수 exp는 알다시피 (1/ n!)*x^n의 무한합으로 정의되어, x에 대해 미분하더라도 예전항이 바로 다음항의 미분 결과와 같은 꼴이 되는 형태이다.

그런데, 삼각함수인 sin과 cos는 exp를 홀수승 항과 짝수승 항으로 분할함과 동시에 각 항의 부호를 또 +, -로 교대로 오고 가게 바꾼 형태이다. 그래서 함수가 무한대나 무한소로 발산하지 않고 진동하게 된다. 신기하기 그지없다.

미적분학을 공부하면 삼각함수와 더불어 쌍곡선함수라는 물건도 배우게 된다.
얘는 sin과 cos에다가 h를 붙여서 sinh, cosh처럼 쓰는데, 지수함수를 이루는 무한급수에서 각각 홀수승항과 짝수승항만 쪼개서 취한 함수이다. 삼각함수와의 차이는 부호 스위칭이 없다는 점이 전부다.

그래서 쌍곡선함수는 비록 그래프의 모양은 삼각함수와 완전히 다르지만 삼각함수와 굉장히 비슷한 특성을 갖게 된다. sinh와 cosh는 미분하면 부호 스위칭이 없이 서로 상대편으로만 탈바꿈하며, 삼각함수의 덧셈정리와 비슷한 특성도 가진다. 삼각함수가 cos(x)^2 + sin(x)^2 = 1이듯이 cosh(x)^2 - sinh(x)^2 = 1이다. 전자가 원스럽다면 후자는 정말 쌍곡선스러운 형태이지 않은가?

쌍곡선함수는 사실상 수학 해석학적인 의미 때문에나 배우지, 삼각함수에 비해 실생활에서 유용한 구석은 별로 없는 것 같다. 그러나 얘도 자연에서 의외로 중요한 곳에서 자주 볼 수 있다. cosh가 바로 현수선의 방정식을 나타내는 함수이기 때문이다.

현수선이란 밀도가 균일한 줄이 자기 길이보다 짧은 간격으로 양 끝이 어떤 중력장 안에 매달렸을 때, 자신의 무게로 인해 중력의 방향(아래)으로 축 늘어짐으로써 형성되는 선을 말한다.
이것도 포물선과 비슷해 보여서 혼동되기 쉽지만, 포물선하고는 수학적인 성질이 완전히 다르다. 현수선은 증가의 폭이 이차함수가 아니라 지수함수와 같은 스케일이다.

알고 보면 아치도 포물선이 아니라 현수선을 뒤집은 모양이다. 현수선 모양으로 구조물을 건설하는 게 모양이 역학적으로 가장 안정적으로 형성된다고 한다.
왜 현수선이 cosh 함수의 형태로 형성되는지 수학적으로 증명하려면 물리학, 미적분학 등 여러 방면의 이론이 동원돼야 하지 않을까 싶다.

어찌 보면 당연한 말이지만, 현수선은 일부만 잘라 내도 그 모양이 그대로 유지된다. 다시 말해 U자 모양으로 된 현수선의 양 끝의 일부를 잘라내서 u부분만 잡고 있더라도 기존 부위가 받는 힘은 변함없으며, 그 구간의 선 모양이 바뀌지 않는다는 뜻이다.

삼각함수와 쌍곡선함수가 각자 자기 분야에서 포물선과는 다른 매끄러움, 출렁거림 등을 표현하고 있다는 게 경이롭다.
자연 현상으로부터 얻은 물리량이라는 게 태생적으로 연속적인 데이터의 형태이다 보니, 물리학의 발전을 위해서는 수학, 특히 미적분학의 발전이 반드시 선행되어야 했다는 게 느껴진다.

Posted by 사무엘

수학에서 행렬은 굉장히 흥미로운 물건이다.
행렬끼리의 덧셈이나 행렬의 상수배는 어려울 게 없는 쉬운 연산이지만, 행렬끼리의 곱셈은 그렇지 않다. 행렬 A와 B사이의 곱셈은 A의 가로 크기와 B의 세로 크기가 같아야 정의되며, 새로 생기는 행렬의 크기(dimension)는 반대로 B의 가로 크기와 A의 세로 크기로 결정된다.

이런 특성상 행렬의 크기는 세로, 즉 row부터 먼저 써 주는 게 직관적이다. 세로 x줄 가로 y줄짜리 x,y 행렬과 y,z 행렬의 곱은 x,z 크기가 된다고 표기가 가능하기 때문이다.

또한, 앞에 있는 행렬과 뒤에 있는 행렬이 원소가 서로 연산되는 방향이 다르기 때문에 행렬의 곱셈은 교환 법칙이 성립하지 않는다. A×B가 일반적으로 B×A와 같지 않다는 뜻. 그러나 결합 법칙은 성립한다. (A×B)×C와 A×(B×C)는 동일하므로, 같은 방향만 유지하면 아무 순서로나 행렬을 곱해 줘도 된다.

그래서 이것과 관련하여 흥미로운 문제가 하나 있다.
크기가 들쭉날쭉 다르지만 순서대로 곱셈은 가능한(= 인접한 행렬끼리는 앞 행렬의 가로 크기와 뒤 행렬의 세로 크기가 일치) N개의 행렬들이 있다. 우리는 이들을 모두 최소의 계산량만으로 곱하고 싶다.

역행렬이나 행렬식 값을 구하는 비용에 비할 바는 아니겠지만 행렬의 곱셈은 꽤 비싼 연산이다. 일반적으로 x,y 크기와 y,z 크기의 행렬을 곱하는 데는 원소들간에 x*y*z회의 곱셈이 필요하다. n 크기의 정사각행렬의 경우 이는 n^3으로 귀착된다. (뭐, 분할 정복법을 활용하여 n^2.x승으로 줄이는 복잡한 알고리즘이 있긴 하지만 이것은 초기 준비 오버헤드가 굉장히 크기 때문에 행렬이 무진장 클 때에나 의미가 있다.)

예를 들어 A는 4*2 크기, B는 2*3 크기, C는 3*1크기의 행렬/벡터라고 치자.
이것을 A*B*C 순으로 진짜 순서대로만 곱하면 A*B를 곱하는 데 4*2*3=24회의 곱셈이 동원되고, 그 결과물인 4*3 행렬을 C와 곱하느라 12회의 곱셈이 필요해서 계산량은 총 36이 된다.

그러나 B*C부터 먼저 곱한 뒤 A를 거기에다 곱하면 열수가 적은 C 덕분에 B*C는 겨우 6회 만으로 끝나고, 거기에다 4*2*1=8회의 곱셈이 추가되어 총 14의 계산량만으로 A*B*C를 구할 수 있다. 답은 결국 똑같은데도 (AB)C보다 A(BC)가 훨씬 더 나은 전략인 것이다.

신기하지 않은가? 그래서 이런 configuration을 일반화하여 {4, 2, 3, 1}이라고 표현하고, 더 나아가 n>=3인 n개의 자연수라고 치자.
이 입력에 대해서 최소 곱셈 횟수와 실제 곱셈 순서를 구하는 것이 문제이다.

정올 공부를 한 분이라면 아시겠지만, 이것은 다이나믹 프로그래밍, 혹은 동적 계획법이라는 알고리즘 설계 방법론을 학습하면서 예시로 다뤄지는 아주 기본 문제이다. 다이나믹 프로그래밍은 다음과 같은 경우에 유용하다.

• 전체 구간에 대한 최적해가 부분 구간의 최적해에다가 추가 연산을 함으로써 구하는 게 가능하다.
• 그리고 한번 답을 구해 놓은 부분 구간의 최적해는 더 바뀌지 않는다는 게 보장된다.

이 행렬의 곱셈 문제에서 가장 작은 구간은 3이며, 이때의 답은 그냥 두 말할 나위 없이 세 정수의 곱이다.
그리고 전체 구간 [1..n]에 대해서 최적해는 바로..

• 1을 [2..n]과 곱했을 때의 계산량 (맨 앞의 행렬과 나머지)
• [1..n-1] 과 n을 곱했을 때의 계산량 (앞의 행렬들과 맨 뒤의 행렬)

중 더 작은 놈이라고 간주하면 된다.

그럼 [2..n]과 [1..n-1]은? 각 구간에 대해서 또 동일한 해법을 적용하여 재귀적으로 구간을 계속 쪼개 나가는 것이다. 언제까지? 구간의 길이가 3이 될 때까지 말이다.
이렇듯, 다이나믹 프로그래밍은 재귀성을 띠고 있다. 이것은 수학적으로는 점화식으로 표현되며, 코드로는...

const int dat[]={4,2,3,1,2,6,5,8,3,2}; //배열

int GetMin(int f, int t)
{
    int i=t-f, j;
    if(i<3) return 0; //should not reach here
    else if(i==3) return dat[f]*dat[f+1]*dat[f+2]; //obvious case
    else {
        //사실은 i가 3인 경우도 이 조건의 특수한 케이스라고 간주할 수 있다.
        //단지 GetMin값이 0이고, t-2와 f+1이 동일한 값이 될 뿐이다.
        i=GetMin(f,t-1) + dat[f]*dat[t-2]*dat[t-1]; //(A*B)*C
        j=GetMin(f+1,t) + dat[f]*dat[f+1]*dat[t-1]; //A*(B*C)
        return i<j ? i:j;
    }
}

int answer = GetMin(0, 10);

과연 이렇게 하면 답이 구해질까?
프로그램을 돌려 보면, 10개의 정수로 표현된 9개의 서로 다른 크기의 행렬들의 곱은..
146회의 곱셈만으로 계산이 가능하다고 나온다.

구체적인 계산 순서는 이러하다.

4 (2 (3 (((((1 2 6) 5) 8) 3) 2)))

이 경우, 각 단계별 계산 순서는 다음과 같이 되기 때문에,

x	y	z	x*y*z
1	2	6	12
1	6	5	30
1	5	8	40
1	8	3	24
1	3	2	6
3	1	2	6
2	3	2	12
4	2	2	16

곱을 전부 합하면 진짜로 146이 맞다!
참고로, 이런 전략을 쓰지 않고 진짜 FM대로 앞에서부터 뒤로 행렬을 순서대로만 곱하면 계산량은 최적해의 세 배를 넘는 492에 달한다.
이것이 바로 알고리즘이 만들어 내는 차이이다.

다이나믹 프로그래밍에는 반드시 수반되어야 하는 작업이 있다. 바로 예전에 구했던 구간 계산값들을 배열에다 저장해 두는 것이다. 그렇게 하지 않으면, 마치 피보나치 수열을 f(x) = f(x-1)+f(x-2)라고만 구현하는 것만큼이나 계산량이 n이 커짐에 따라 기하급수적으로 커지게 된다. 그것도 예전에 한번 했던 똑같은 계산을 매번 반복하느라 말이다.
그래서 이 방법을 사용한 알고리즘은 대체로 시간 복잡도와 공간 복잡도가 모두 O(n^2)이 된다. 시간 복잡도가 지수함수에서 그래도 다항함수로 바뀐다.

구간별로 최적해 자체뿐만이 아니라 구간 분할을 어떻게 했는지에 대한 정보도 따로 보관해 놓으면 아까와 같은 구체적인 계산 순서도 그 정보를 추적함으로써 구할 수 있다.

정올에서 다이나믹 프로그래밍의 중요성은.. 두 말하면 잔소리이다.
본인은 20세기에 정올 공부를 한 세대인지라 그 시절의 문제밖에 기억을 못 한다만..

1997년 한국 정보 올림피아드의 고등부 3번인 벽장 문제는 최적해를 구하고자 할 경우 공간과 시간 복잡도가 O(n^3)인 다이나믹 프로그래밍으로 풀 수 있다. 이 때문에, 16비트 환경임을 감안하더라도 이 문제는 입력의 범위가 작다. 벽장의 개수와 벽장 사용 순서가 최대 겨우 20까지밖에 안 올라가는 소규모이다. 실용적인 상황에서는 이런 부류의 시뮬레이션 문제는 휴리스틱이 동원되어야 할 것이다.

이 외에,

1999년 고등부 1번 검은 점 흰 점 연결,
2000년 고등부 1번 수열 축소

도 다이나믹으로 푸는 문제이다.
국제 정보 올림피아드의 기출 문제 중에는
10회(1998)의 둘째 날 마지막 문제인 폴리곤 게임,
11회(1999)의 첫째 날 첫 문제인 꽃 진열이 기억에 남는다. 특히 꽃 진열은 상당히 기초적인 다이나믹 프로그래밍 문제로, <날개셋> 타자연습의 문장 정확도 측정도 이와 거의 같은 발상의 알고리즘을 사용하고 있다.

난 이 바닥은 손 놓은 지가 너무 오래 돼서 기억이 가물가물하다.
정보 올림피아드에서 경시와 공모는 마치 과학과 공학, 어학과 문학의 차이와 비슷한 것 같다.

Posted by 사무엘

원점 O에서 시작하는 벡터 A, B가 있다. 그런데 A와 B가 형성하는 내각을 이등분하는 중앙을 지나는 벡터 C를 구하려면 어떡하면 좋을까? 각도를 결정하는 방향만 정확하게 나오면 되며, 길이가 어떻게 되는지는 신경 쓰지 않아도 된다.

단순히 벡터 A와 B를 더하기만 해서는 내각을 정확하게 이등분할 수 없다는 것을 알 수 있다.
더하기만 해서 얻은 벡터는 삼각형 OAB의 '무게중심'을 지나게 된다.
그러나 내각을 이등분하는 벡터는 삼각형 OAB의 '내심'을 지나게 해야 하기 때문이다.

이 문제는 의외로 어렵지 않다.
선분 AB의 위에 있는 점 C를 설정하되, 선분 OA: OB의 길이의 비와 선분 AC: BC의 길이의 비가 일치하는 지점 C를 찾으면 된다. 그러면 원점에서 시작하는 벡터 C가 바로 벡터 A와 B의 내각을 이등분하는 벡터가 된다.

그렇게 되는 이유를 해석학적으로 따져 보면 다음과 같다.

위의 그림에서 점 A의 좌표는 (1, tan α)이고 B의 좌표는 (1, tan(α+2β) )이다.
그리고 선분 OA의 길이는 피타고라스의 정리에 따라 sqrt(1 + (tan α)^2)이요, 선분 OB의 길이는 더 복잡한 sqrt(1 + (tan (α+2β))^2)가 되는데..

이 둘의 비율이 AC와 BC의 길이의 비와 같다는 뜻이다. AC와 BC는 각각 (tan α+β - tan α), (tan α+2β - tan α+β)로 표현될 것이다.
한쪽은 탄젠트값의 제곱에다가 제곱근이 나오고, 다른 한쪽은 제곱 연산은 없지만 서로 다른 탄젠트 함수의 뺄셈이 나온다. 언뜻 보기에 둘은 서로 비슷한 구석을 찾을 수 없다. 그렇다면 이들이 비율이 서로 일치한다는 걸 어떻게 보일 수 있을까?

여기서 탄젠트 제곱과 제곱근을 쉽게 정리하는 방법이 있다. tan x = sin x / cos x이므로, 1을 분모와 분자가 모두 cos^2 x 인 분수로 간주하여 1 + tan^2 x는 (cos^2 x + sin^2 x)/cos^2 x라고 볼 수 있다.
그럼 분자는 얼씨구나 1로 약분된다. 근호 안에는 1/cos^2 x밖에 남지 않으니, 전체 식은 단순히 1/cos x로 줄어든다.

비례식에서 내항과 외항의 곱은 같아야 하므로, 내항의 곱을 분자에, 외항의 곱을 분모에다 얹은 분수를 설정해 보겠다. 이 수의 값이 1이면 목적이 달성되는 것이므로 어느 걸 분자에, 어느 걸 분모에 얹을지는 그리 중요하지 않다.
식에서는 α+2β, α+β, α라는 세 종류의 각이 쓰이는데, 일단 시각적인 혼동을 줄이기 위해서 앞의 두 아이템을 이제부터는 각각 A, B라는 매크로로 치환하였다.

이제 예전보다 문제가 꽤 단순해졌다.
분자와 분모가 또 분수로 구성되어 있는데, 이것을 통분하는 방법은 간단하다. 분자와 분모에 모두 똑같이 cos A cos B cos α를 한꺼번에 곱해 주면 된다.
그러면 각 분자와 분모에 이중으로 분모로 남아 있던 cos α나 cos A는 약분되어 없어지고, tan 함수도 내부적으로 갖고 있던 cos 나눗셈이 약분되면서 sin으로 바뀐다. 그리고 약분되지 않은 변수에 속하는 cos만이 남는다.

그 뒤의 절차는 일사천리이다.
sin 함수와 cos 함수의 곱이 규칙적인 패턴으로 남는데, 이것은 딱 정확하게 sin(x-y) 꼴로 정리가 된다.
그리고 이제야 매크로 A, B를 원래의 각으로 전개해 보면, A-B와 B-α의 각은 애초에 같은 값이었다는 것을 알 수 있다. 따라서 분자와 분모는 동치이고 원래의 비례식도 항등식으로서 성립한다는 게 밝혀진다.

뭔가 당연한 사실을 필요 이상으로 너무 복잡하게 파헤친 거라는 느낌이 든다. =_=
삼각함수, 벡터 이런 쪽은 컴퓨터에서 기하를 다루는 데 없어서는 안 될 마법과 같은 도구임이 분명하다.

Posted by 사무엘