이번 글에서 다룰 문제는 겉보기에는 매우 복잡해 보이지만 원리만 알면 초등학생도 풀 수 있는 문제이다.
1m 길이의 가느다란 봉 위에 25마리의 개미들이 아무 곳에나 서있다. 이들 개미는 출발신호와 함께 왼쪽, 또는 오른쪽으로 1cm/s 속도를 유지하며 봉 끝에 떨어질 때까지 걸어나간다.(좌우 선택은 무작위) 단, 걸어가던 두 개미가 봉 위에서 충돌하면 각자 진행하던 방향을 바꿔 반대로 걸어나간다.
왼쪽에서 오른쪽으로 순서대로 1, 2, ... 25번으로 개미들을 이름붙이자. 13번 개미가 봉에서 떨어졌으리라 확신하려면 최소 몇 초간 기다려야 하는가?
문제 속에서 개미의 크기는 무시한다.
풀이
정답은 100초이다.
이 문제를 단순히 접근하면 13번 개미의 움직임이 너무 복잡하여 풀기가 어렵다. 이 개미는 좌우로 각각 12마리의 개미가 있으므로 계속 이들 개미와 부딪치며 수십번 방향을 바꿀 수 있기 때문이다.
각 개미를 관찰하지 말고 거시적인 관점에서 문제를 바라보자. 개미가 모두 떨어졌으리라 확신하려면 되소 몇 초간 기다려야할까?
문제를 복잡하게 하는 것은 부딪침과 방향전환이다. 여기서 꾀를 내어 문제 속에서 개미들이 부딪치지 않고 서로 스쳐지나간다고(!) 생각해보자. 이 위험천만한 발상은 잘 곱씹어보면 전혀 시간을 더하거나 덜지 않는다는 걸 알 수 있다. 왜냐하면 충돌 전 두 개미의 속도는 모두 1cm/s이고 충돌 이후에도 똑같은 속도를 유지하기 때문이다.
결국 모든 개미가 떨어지는 데 걸리는 시간의 최댓값은 각 개미가 방해 없이 봉을 걷다가 그 끝에서 떨어지는 시간의 최댓값과 같다. 이는 개미가 한 쪽 끝에서 반대쪽 끝으로 걸어가 떨어질 때 벌어지므로 1m/(1cm/s) = 100초이다.
아무리 못해도 100초를 기다리면 모든 개미가 떨어졌을 것이고 따라서 우리가 주목하는 13번 개미 역시 떨어졌으리라 확신할 수 있다.
극단적인 예를 생각해보자. 모든 개미가 왼쪽 끝에 다닥다닥 붙어있다고 가정하자.(개미의 크기를 무시하므로 그렇게 생각할 수 있을 것이다.) 이 개미무리가 한꺼번에 오른쪽 끝으로 간다면 당연히 아무 부딪침없이 모두 100초간 걸어 오른쪽 끝에서 떨어질 것이다. 따라서 이런 경우를 생각하면 아무리 못해도 100초는 걸린다는 걸 알 수 있다.
약간 고전적인 문제로, 퍼즐책 이곳 저곳에서 등장한다. 필자가 고른 책은 Mathematical Mind-Benders(Peter Winkler 지음)이다.
