시험만 아니라면, 수학은 재미있다
[책을 읽고] 이언 스튜어트, <최고의 수학자가 사랑한 문제들> (1)
이 책은 천재 수학자 이언 스튜어트가 손수 모은 수학 수수께끼집이다. 모든 문제에 대해 답이 있는 것은 아니다. 예컨대 모순 명제에 관한 제4장은 오픈 엔딩이다.
수수께끼 모음에 대해 인트로를 늘어놓는 것이 무슨 소용인가. 문제로 당장 뛰어들어 보자.
워밍업: 케이크를 공평하게 나누기
케이크를 둘이 공정하게 나누는 방법은 잘 알려져 있다. 나누는 사람과 먼저 고르는 사람이 다르면 된다. 그런데 3명일 때는 어떻게 할까? 2명일 때의 방법을 약간 비틀면 되지만, 직관적이지도 않고 번거롭다.
더 간단한 방법은 경매를 이용하는 것이다. 케이크 한쪽에서부터 눈금이 느린 속도로 움직인다. 눈금까지의 양이 1/n 이상이라 판단하는 사람은 재빨리 손을 들면 된다. 이 방법은 케이크 모양이 어떻든 상관이 없고, n이 어떤 정수이든 상관 없이 작동한다. 그리고 직관적이다.
재미는 없겠지만, 게임을 만들어 내는 수학자들
제7장에 나오는 쿼드(Quod) 게임은 아주 흥분시키는 수준은 아니겠지만 꽤 재미있는 게임으로 보인다. 그래서 이 게임은 분명히 앱스토어에 있을 것이라 생각했다. 그러나 찾아보니 없어서 꽤 실망했다.
한 가지 생각한 것은, 쿼드 게임에서 쓰이는 쿼저를 오목에 도입해도 좋지 않을까 하는 것이다. 쿼저는 쿼드가 성립되는 것을 방해하지만, 누구의 것도 아니다. 오목에 대입해 말하자면, 쿼저는 상대의 오목이 성립하는 것을 막을 수는 있지만 내 오목의 구성원이 되지는 못한다. 말하자면 중립 수인 셈이다. 2명이 하는 오목이라면 흑백이 아닌 제3의 색으로 하면 될 것이다.
쿼드는 대각선을 포함해서 머릿속으로 사각형을 그려야 하기 때문에 상당한 집중력, 그리고 무엇보다 공간 지각 능력이 필요한 게임으로 보인다. 공간 지각 능력이 매우 모자라는 나로서는, "재미없지만" 시도해 볼 가치가 있는 게임이다.
헉, 아마존. 재고 있음!m-pire 문제: 시간 낭비 장난인가, 실용적 게임인가
4색 문제의 확장 버전인 m-파이어 문제도 흥미롭다. 이 문제에서 모든 국가는 각각 1개의 식민지 영토를 가진다. 식민지 영토는 다른 대륙(내지 다른 별)에 있다. 이웃한 국가들을 다른 색깔로 칠하는 데까지는 4색 문제와 같지만, 이 문제의 복잡성은 이웃하는 식민지 영토들 역시 서로 다른 색깔이어야 하고, 동시에 본국과 식민지가 같은 색깔이어야 한다는 데 있다.
이 문제는 쾨니히스부르크 다리 문제와 마찬가지로 결국 노드 연결의 문제다. 모든 가능성에 대한 (무식한) 반복 연산에 의해 증명된 4색 문제와 마찬가지로, m-파이어 문제 역시 무식한 반복 연산에 의해 해결될 것으로 보인다.
이미 1890년에 퍼시 히우드는 m>=2일 때 6m개의 색이면 충분하다, 즉 최대 6m개의 색이 필요하다는 사실을 증명했다. 그러나 수학자들이 원하는 것은 충분조건이 아니라 필요충분조건이다.
이런 쓸데없어 보이는 일에 왜 에너지를 써야 하나 하는 생각이 드는 게 당연하다. 그래서, 바로 다음 장인 제10장에서 이언 스튜어트는 이런 공상이 쓸 데 있다는 점을 보인다.
전자기판을 입체적으로, 즉 층적할 경우에 도움이 된다는 것이다. 잘 알려져 있다시피, 요즘 반도체는 평면 기판이 아니라 층층이 쌓인 3차원 형태다. 이 상황에서 합선 여부를 확인하려면 대체 얼마나 전류 테스트를 해야 할까? n개의 노드가 있다면 최대 2^n번 테스트를 해야 한다는 암울한 시나리오부터 떠오른다.
바로 이 문제를 m-pire 문제로 해결할 수 있다. 각각의 층, 즉 평면 기판에서의 합선은 비교적 쉽게 알 수 있다. 눈에 보이기 때문이다. 문제는 다른 층과의 합선이다. 예컨대 1층의 어떤 노드가 2층이나 3층의 다른 노드와 연결되어 있을 수 있기 때문이다.
서로 연결되는 노드들은 하나의 제국에 해당한다. 식민지 역시 마찬가지다. 본국(1층)이든 식민지(2층)이든 같은 제국 소속이라면 서로 연결되어도 좋다. (연결되어야 한다.) 반면, 다른 제국과는 본국이든 식민지든 연결되면 안 된다.
정확히 m-pire 문제다.
m-pire 문제의 실전 적용
어떤 기판이 12개의 "제국"을 가진다고 상상해보자. 12개의 제국들이 서로 독립성만 유지하면 된다. 따라서 12개의 탐침에 대해 2개씩 연결하여 전기가 흐르는지 확인하면 된다. 12개에서 2개를 고르는 조합, 즉 12*11/2=66회 검사로 충분하다.
하지만 확 더 줄일 수 있다. <소년 탐정 김전일>의 한 에피소드가 생각나는 대목이다. 10개의 금화 주머니에 금화가 각각 100개씩 들어 있는데, 단 한 개의 주머니만 가짜 금화로 채워져 있다. 진짜 금화와 가짜 금화는 무게가 다르다. 저울을 몇 번 사용하면 가짜 금화 주머니를 확인할 수 있을까?
답은 한 번이다. (왜 그런지는 생각해 보자. 힌트를 주자면, 주머니가 10개든 100개든 5억 개든 한 번으로 알아낼 방법이 있다.)
비슷한 방식으로 12개 제국을 가진 기판 합선 검사를 단 11회로 끝낼 수 있다. 해답은 책을 찾아보라.
웨스트미시건 대학교의 앨런 슈벵크는 11회를 4회로 또 줄였다. 힌트는 10진법에서 벗어나라는 것이다. (힌트를 하나 더 주자면, 16개 제국 기판까지도 4회에 가능하다. 이 힌트는 좀 너무 나갔나?)
수학은 천재들의 놀이터다.
사진: Unsplash의Henry Be