d라이브러리

Q

어느 캄캄한 밤, 격류가 흐르는 강가에 네 사람이 도착했다. 눈앞에 보이는 낡은 다리는 겨우 두 사람만 지날 수 있는데 설상가상으로 손전등은 하나뿐이어서 누군가 손전등을 갖고 되돌아오는 일을 반복해야만 했다. 네 사람의 걷는 속도는 모두 달라서 각각 다리를 건너는데 1분, 2분, 5분, 10분이 걸린다. 예를 들어 1분 걸리는 사람과 10분 걸리는 사람이 같이 다리를 건너면 10분이 걸리게 된다. 네 사람 모두 무사히 강을 건너려면 최소 몇 분이 필요할까?

A

손전등을 던져 준다느니, 모두 라이터를 갖고 있었다느니 하는 식의 풀이를 생각하신 분이라면 다시 풀어 보시길. 난센스가 아니라 수학퍼즐이니까. 이 문제는 여러 가지 다른 형태로 알려져 있다. 필자가 아는 가장 오래된 형태는 다고 아키라의 ‘두뇌의 체조’에 등장하는 것으로 무선 조종되는 우주선을 옮기는 내용이다.

이후 배 네 척을 반대쪽 강가로 옮기는 문제로 알려지기 시작하더니 미국 마이크로소프트(MS)가 입사 지원자 면접에서 위 문제를 사용했다고 알려지면서 유명해졌다. 물론 MS가 정말로 이 문제를 썼는지는 알 수 없는 일이지만.

이 문제를 처음 접하는 사람들은 대개 속도가 제일 빠른 사람이 손전등을 갖고 왕복해야 시간이 최소로 걸린다고 생각한다. 따라서 다리를 건너는 데 1분이 걸리는 사람이 나머지 세 사람을 데리고 다리를 건너갔다가 다시 되돌아오기를 반복하면 그 시간이 바로 최단 시간이 돼야 한다.

이때 걸리는 시간은 10+1+5+1+2=19(분)이다.

하지만 놀랍게도 더 짧은 시간에 모두 강을 건널 수 있다. 핵심 아이디어는 가장 느린 두 사람을 같이 움직이게 해서 걸리는 시간을 줄이는 것이다. 먼저 1분 걸리는 사람과 2분 걸리는 사람이 같이 다리를 건넌다. 그 다음 1분 걸리는 사람이 되돌아온다. 여기까지 3분.

다음으로 10분 걸리는 사람과 5분 걸리는 사람이 같이 건너가고, 먼저 도착해 있던 2분 걸리는 사람이 되돌아온다. 여기까지 총 15분. 이제 1분 걸리는 사람과 2분 걸리는 사람이 마지막으로 다리를 건너면 된다. 이렇게 건너면 17분밖에 걸리지 않는다.

이 문제는 간단하지만 그 풀이가 직관의 허점을 찌르는 멋진 것이어서 많은 사람들이 다양한 관점에서 학문적으로 연구해왔다. 2002년 6월 뉴질랜드의 크리스찬과 엘레나 칼루데 부부가 처음으로 이 문제의 일반적인 풀이법을 제시했다. 그런데 불행히도 겨우 두 달 뒤 독일의 귄터 로테 교수는 그들의 풀이가 틀렸음을 밝혔다. 로테 교수는 자신의 논문 ‘밤에 다리 건너기’(Crossing the Bridge at Night)에서 올바른 풀이를 제시했다.

당연한 일이겠지만 최소 시간을 구하는 식은 꽤나 복잡하게 생겼다.

아무튼 간단한 퍼즐이 논문 주제가 될 수 있다니 재미있는 일이다.

지난달 정답 _ 5