컴퓨터는 물리적인 소자의 숫자를 줄이기 위해서 2진법을 사용한다. 우리에게는 10진법이 익숙하고 편리하지만 기계의 언어로는 2진법이 실용적이고 효과적인 모양이다. 이런 모양의 시계를 보자.

이것은 2진법 시계인데, 윗줄이 시간을 의미하고 아랫줄이 분을 의미한다. 지금 이 시계의 시간은 12시 20분이다. (4+8 =12시, 4+16 = 20분) 불이 들어오는 작은 전구를 생각한다면 모두 10개의 전구로 시간과 분을 나타낼 수 있다. 더 적은 개수로 시간을 나타낼 수 있는지는 모르겠지만, 10진법보다는 확실히 적은 수의 물리적인 전구를 이용한 것이다. 2진법의 효과적인 활용을 생각할 수 있는 문제 하나를 소개한다.

 

 

독이 든 포도주 찾기

옛날에 포악한 왕이 있었다. 그는 아주 귀한 포도주 1,000병을 창고에 보관하고 있었다. 그에게는 적이 많았었는데, 이웃 나라의 여왕이 포도주에 독을 타서 악한 왕을 죽이려고 첩자를 보냈다. 다행히 악한 왕의 호위병사들이 첩자를 잡았다. 그러나 불행히도 첩자는 이미 1,000병의 포도주 중 딱 한 병에 독을 넣은 다음이었다. 독이 들어간 포도주 병이 다른 병과 똑같아서 호위병사들은 그것을 눈으로 구별할 수 없었다. 포도주에 들어간 독은 맹독이라서 백만분의 1로 희석해도 여전히 사람을 죽일 수 있으며, 그 독의 특징은 1달이 지나서 그 효력이 나타나는 독이었다.

 

무자비한 왕의 궁전에서는 5주 뒤에 큰 잔치가 열리기로 되어 있다. 악한 왕은 포도주를 전부 없애버릴 수 없어서 고민하기 시작했다. 한참 고민하다가 마침내 악한 왕은 어쩔 수 없이 죄수들에게 포도주를 조금씩 마시게 하여 독이 든 포도주 병을 찾기로 했다. 왕의 궁전에는 죄수들을 가둔 감옥이 있었는데, 사형수는 10명뿐이었다. 감옥의 다른 죄수까지 모두 합해도 겨우 100명이 조금 넘는 숫자였다. 포악한 왕은 일반인까지 끌어들여서 1,000명을 만들어 어떤 포도주에 독이 들었는지를 알아내려 했다. 그때 왕국의 현자가 왕에게 말했다.

 

“왕이시여, 지하 감옥에 갇혀있는 사형수 10명만 희생시키면 어떤 병이 독이 든 포도주인지 알아낼 수 있습니다.”

 

[질문] 그는 도대체 어떤 방법으로 사형수 10명만 희생하여 독이든 포도주 병을 찾을 수 있다고 한 것일까?

 

 

상황을 이렇게 생각해보자. 10병의 포도주가 있는데 그 중 독이 들어있는 한 병을 찾기 위해서는 어떻게 하면 좋을까? 10명에게 1번부터 10번까지의 포도주를 각각 먹여보는 것이 방법일 것이다. 하지만, 2진법을 사용하면 다음과 같이 할 수 있다. 먼저 1부터 10까지를 2진법으로 써보자.

10명에게 포도주를 마시게 하지 말고, 4명에서 위와 같이 마시게 하자. 1번 포도주는 4번 죄수에게만 마시게 하고, 2번 포도주는 3번 죄수에게 마시게 하고, 3번 포도주는 3번 죄수와 4번 죄수에게 마시게 하는 거다. 예를 들어, 5번 포도주는 2번 죄수와 4번 죄수에게 마시게 하고, 9번 포도주는 1번 죄수와 4번 죄수에게 마시게 하는 거다.

 

이렇게 하면 만약 한달 후에 2번 죄수와 3번 죄수가 죽는다면 독이 든 포도주는 6번인 것을 알 수 있다.

 

 

10개의 포도주 중 독이 들어있는 포도주를 4명의 죄인에게 먹임으로써 알아냈던 아이디어를 1,000병의 포도주 중 독이 들어있는 한 병을 찾는 것에 적용해보자. 먼저 생각할 것은 1부터 1,000까지를 모두 2진법으로 표현하는 것을 생각해봐야 한다. 2를 10번 곱한 것이 1024다. 따라서 포도주가 모두 1,000병이라면 포도주를 먹일 죄수는 10명이면 충분하다.

 

 

1에서 1,000까지의 수를 2진법으로 나타내자. 그리고 앞에서 했던 것처럼 각 단위 자리에 10명의 죄인을 한 명씩 지정한다.

1번 사형수는 2진법으로 나타냈을 때 1의 자리가 1인 포도주 병에서 한 모금씩 마신다.

2번 사형수는 2진법으로 나타냈을 때 2의 자리가 1인 포도주 병에서 한 모금씩 마신다.

3번 사형수는 2진법으로 나타냈을 때 4의 자리가 1인 포도주 병에서 한 모금씩 마신다.

4번 사형수는 2진법으로 나타냈을 때 8의 자리가 1인 포도주 병에서 한 모금씩 마신다.



10번 사형수는 2진법으로 나타냈을 때 512(2의 9제곱) 자리가 1인 포도주 병에서 한 모금씩 마신다.

 

예를 들어 924번 포도주 병을 마시는 사형수는 3,4,5,8,9,10이다.

사형수                     10 9 8 7 6 5 4 3 2 1

포도주 924                 1 1 1 0 0 1 1 1 0 0

 

만약 924번 병에 독이 들었다면 이 사람들만 죽게 된다. 이런 방법으로 한 달이 지난 다음 몇 번 사형수가 죽었는지 조사하면 어떤 병에 독이 들었는지 알 수 있다.

 

 

이런 문제를 2진법에 대한 경험 없이 그냥 풀 수 있는 사람은 아마 없을 거다. 비슷한 문제의 경험이 있는 사람이라도 쉽게 생각할 수 있는 건 아닐 거라고 생각한다. 생소하고 어려운 문제일지 몰라도 아이디어를 따라 읽어보고 이해하는 것도 재미있다.

 

나는 2진법처럼 둘 중 하나로 생각하는 것을 좋아한다. 그것이 매우 효과적이라는 경험도 한다. 세상에는 2종류의 사람이 있다. 남자와 여자. 말하고 듣는 걸 좋아하는 사람과 쓰고 보는 걸 좋아하는 사람. 외향적인 사람과 내향적인 사람. 직관적인 걸 좋아하는 사람과 논리를 중시하는 사람. 세상을 둘 중 하나로 나누는 것만큼 바보스러운 것이 없는 것 같아도, 이렇게 몇 가지 기준으로 세상을 보면 모르던 것이 좀 더 잘 이해되는 경험을 하게 된다.

 

 

ⓒ 한경닷컴, 무단전재 및 재배포 금지