표류 중인 어부 문제 (Lost Fisherman Problem)

친한 형이 오랜만에 연락이 와서 다음 유튜브 영상을 공유해주었습니다. 이 영상에서 소개된 첫 번째 문제가 개인적으로 흥미로워서 공유해 보고자 이 글을 쓰게 되었습니다. 재미있는 문제를 소개해준 형한테 고맙다는 말을 전합니다.

출처 : Zach Star on Youtube (youtu.be/6O8Jyrr9LRc)

문제는 다음과 같습니다. 한 어부가 나침반도 없이 바다로 나섰는데, 얼마 지나지 않아 갑자기 해무가 자욱하게 끼기 시작하였습니다. 더이상 조업을 할 수 없다고 판단한 어부는 해변으로 돌아가기로 결정하였습니다. 해변가는 직선으로 곧게 뻗어 있고 어부는 해변가에서 수직으로 정확히 1㎞ 떨어진 지점에 있는 상황입니다. 문제는 어부가 나침반을 갖고 오지 않아서 도무지 어느 방향으로 가야 해변가가 나오는지 전혀 모른다는 겁니다.

그림 1. 어부가 처한 상황.

대신 이 어부는 이 상황을 타개할 만한 기술을 두 가지 갖고 있습니다. 하나는 원하는 거리만큼 정확히 직선으로 가는 것이고, 다른 하나는 아무 원의 호를 따라서 원하는 만큼 움직일 수 있는 것이죠.(쩌네요.) 우리의 목표는 어부가 최대한 짧은 거리를 움직여 해변에 다다르는 방법을 찾는 것입니다.

영상에서 소개된 방법

위 영상에서 소개된 방법을 설명드리도록 하겠습니다. 아이디어는 간단합니다. 처음 위치를 중심으로 1 ㎞ 이상의 반지름을 갖는 원을 따라 움직이면 언젠간 해변에 다다른다는 것입니다. 첫 번째 방법으로, 먼저 아무 방향을 정한 후 정확히 1 ㎞를 직진한 후에 처음 위치를 중심으로 반지름이 1 ㎞인 원을 따라 시계 방향으로 움직여 보도록 하겠습니다.

그림 2. 첫 번째 방법의 예시.

현재 위치가 해변으로부터 정확히 1 ㎞ 떨어져 있으므로 이 방법은 반드시 해변에 도착할 것입니다. 그러면 과연 이 방법을 통해서는 최악의 경우 얼마큼 움직이게 될까요? 네, 만약 어부가 해변으로 곧장 향하는 방향에서 약간 오른쪽으로 뱃머리를 틀었다면, 안타깝게도 해변에 바로 도착하지 못하고 원의 거의 대부분을 한 바퀴 돌아야 할 것입니다. 이때 이동한 거리가 \((1 + 2\pi) \approx 7.283 \) ㎞가 된다는 사실은 그다지 어렵지 않게 보일 수 있습니다.

그림 3. 첫 번째 방법의 최악의 경우의 예시.

여기서 좀더 잘할 수 있을까요? 위 방법에서 우리가 쉽게 바꿀 수 있는 것 중에 하나는 반지름입니다. 우리가 1 ㎞보다 좀더 먼 거리를 직선으로 이동한다면 어떻게 될까요? 그러면 직진하는 중에 해변에 도달할 확률이 높아진다는 것을 알 수 있습니다. 하지만 해변에 도달하지 못했다면 아무래도 더 긴 반지름을 갖는 원을 따라 움직여야 하므로 실패했을 때에는 더 큰 부담으로 다가올 겁니다. 따라서 이 트레이드오프(trade-off) 관계의 평형을 이루는 거리를 구하면 아마 위 방법보다 좀더 좋은 방법을 얻을 수 있을 것입니다.

 

이 아이디어를 활용한 두 번째 방법을 소개하겠습니다. 첫 번째와 마찬가지로 아무 방향을 잡은 후 이번에는 \(x\) ㎞만큼 직진합니다. 여기서 \(x\)는 나중에 정하도록 하겠습니다. 대신 \(x \geq 1\)이어야 하겠죠. 그렇지 않으면 해변에 닿지도 않을 테니 말입니다. 직진하는 와중에 해변에 도달하지 않으면 그후 출발 지점을 중심으로 하는 반지름 \(x\) ㎞의 원을 따라 시계 방향으로 움직여 줍니다. 

그림 4. 두 번째 방법의 예시.

이 방법을 사용하면 최악의 경우 얼마큼 움직여야 할까요? 첫 번째 방법에서 논의한 것과 비슷하게 이번에도 직선 항해로 해변에 도달할 수 있는 방향에서 약간 오른쪽으로 벗어난 방향으로 이동한 후 바다 부분과 겹치는 원의 호를 따라 움직인 거리가 최악의 경우가 될 것입니다.

그림 5. 두 번째 방법에서 직선 항해로 곧장 해변에 도달할 수 있는 각도의 최댓값.

먼저 직선 항해로 해변에 도달할 수 있는 방향을 구해보도록 하겠습니다. 이는 그림 5를 보면 쉽게 알 수 있습니다. 빗변의 길이가 \(x\) ㎞, 밑변의 길이가 1 ㎞인 직각삼각형에서 이 두 변의 끼인각을 \(\tau\)라고 하겠습니다. 다시 말해, \[ \tau := \cos^{-1} \left( \frac{1}{x} \right)\]입니다. 그러면 수평 방향을 곧장 해변에 도달할 수 있는 기준 방향으로 정했을 때, 좌우로 \(\tau\) 이내의 방향으로 움직였다면 곧장 해변에 도착할 수 있게 됩니다.

그림 6. 두 번째 방법의 최악의 경우.

이를 이용하면 두 번째 방법을 사용했을 때 최악의 경우 얼마큼 움직여야 하는지를 알 수 있습니다. 일단 직선으로 움직인 거리는 \(x\) ㎞입니다. 그리고 만약 수평 방향을 기준으로 뱃머리를 오른쪽으로 \(\tau\)보다 약간 더 돌렸다면 거의 \( x (2 \pi - 2 \tau) \)의 거리를 움직이게 됩니다. 따라서 \(x\)가 주어졌을 때, 두 번째 방법이 움직이는 거리는 최대 \[ d(x) := x + x(2\pi - 2\tau) = (1 + 2\pi) x - 2 x \cos^{-1}\left( \frac{1}{x} \right) \]가 됩니다. 위 식은 \(x \approx 1.044\)일 때 \( d(x) \approx 6.995 \)를 최솟값으로 갖습니다. 따라서 두 번째 방법은 \(x\)를 \(1.044\) 정도로 잡았을 때 첫 번째 방법보다 최악의 경우에도 약 \(0.288\) ㎞ 정도 더 짧은 경로를 탄다는 것을 알 수 있습니다.

확률 활용하기

영상에서는 두 방법을 소개한 후에 다음과 같이 말합니다.

우리는 여전히 더 잘할 수 있습니다.
We can still do better.

그래서 어떻게 하면 더 잘할 수 있을지 저도 한번 고민해 봤습니다. 그리고 제가 낸 결론은 확률을 이용하면 지금보다 더 좋은 거리를 '기대'할 수 있겠다고 생각했습니다. 이 절에서는 제가 생각한 것을 공유해 보고자 합니다. 참고로 나중에 확인해 본 결과 이는 채널 주인이 의도한 답은 아니더군요. 채널 주인이 소개하는 더 좋은 방법은 글의 말미에 밝혀 두었습니다.

 

제 아이디어는 어부가 어느 방향을 취하는지에 따라서 움직이는 거리가 달라진다는 것에서 시작하였습니다. 예를 들어, 첫 번째 방법에서 최악의 경우는 1 ㎞를 직진한 후에 반지름이 1 ㎞인 원을 (거의) 모두 지나 해변에 도달하는 것이었습니다. 하지만 만약 어부가 해변으로 곧장 도달하는 기준 방향의 정확히 반대 방향으로 배를 몰았다면 직진으로 이동한 거리에 반원의 길이만 더해주면 됩니다. 운이 좋다면 기준 방향의 약간 왼쪽으로 틀어진 방향으로 배를 몰아서 거의 1 ㎞에 근사하는 거리를 이동했을 수도 있습니다. 따라서 최악의 경우만 고려해서는 이 방법을 제대로 평가하는 것이 아닐 수 있습니다.

그림 7. 첫 번째 방법이 방향에 따라 서로 다른 이동 거리를 갖는다는 것을 보여주는 예시.

이런 경우에는 대체로 확률을 도입하여 이동 거리의 기댓값을 구하게 됩니다. 예를 들어, 첫 번째 방법에서 아무 방향을 선택하는 대신 \( [0, 2\pi) \)에서 균등한 확률(uniformly at random)로 \(\theta\)를 골라 해당 각도를 방향으로 삼아보도록 하겠습니다. 이때 배가 움직인 거리를 \(d (\theta) \)라고 하면, 우리는 \[ d(\theta) = 1 + \theta \]라는 사실을 쉽게 얻을 수 있고, 이를 통해 \[ \mathbb{E}[d(\theta)] = \int_{0}^{2 \pi}(1 + \theta) \frac{1}{2 \pi} d\theta = 1 + \pi\]가 된다는 것을 알 수 있습니다. 다시 말해 이 방법은, 최악의 경우에는 물론 \( (1 + 2\pi) \approx 7.283 \) ㎞를 이동하지만, 평균적으로 \( (1 + \pi) \approx 4.142 \) ㎞ 정도를 이동할 것으로 기대되는 방법이라는 것이죠.

 

이와 비슷한 방식으로 두 번째 방법을 분석하면 위 절에서 구한 결과와는 사뭇 다른 결과를 얻을 수 있습니다. 직선으로 이동할 최대 거리 \(x\)는 미리 주어졌다고 가정하겠습니다. 나중에 이동 거리의 기댓값을 최소화하는 \(x\)를 선정하도록 하겠습니다. \(x\)가 정해지면 직선 거리로 해변에 도달할 수 있는 최대 각도인 \( \tau := \cos^{-1} \left( \frac{1}{x} \right) \)도 정해지게 됩니다. 참고로 \(x \geq 1\)이므로, \[ 0 \leq \tau < \frac{\pi}{2} \tag{1} \]가 된다는 점도 확인하시기 바랍니다. 그후에는 앞에서와 비슷하게 \( [-\tau, 2 \pi - \tau) \)에서 균등한 확률로 \( \theta \)를 골라 해당 각도를 방향으로 배를 움직이도록 하겠습니다.(여기서 \( [0, 2\pi) \)가 아닌 \( [-\tau, 2\pi - \tau) \)에서 뽑은 이유는 아래 분석을 좀더 편히 쓰기 위해서입니다. 음수 각도는 기준 방향을 기준으로 오른쪽으로 돌아가는 각도로 생각하시면 되겠습니다.)

 

이제, \(x\)와 \(\theta\)가 정해졌을 때 이 방법이 이동하는 거리 \(d_x(\theta)\)를 구해보도록 하겠습니다. 이는 직선 항해로 바로 해변에 도착하는 경우와 호를 따라 항해를 조금이라도 하는 경우로 나눌 수 있습니다.

그림 8. 수정된 두 번째 방법이 \( -\tau \leq \theta \leq \tau \)일 때 이동하는 거리의 예시.

첫 번째로 직선 항해로 바로 해변에 도착하는 경우입니다. 이는 \( -\tau \leq \theta \leq \tau  \)일 때 발생하며, 그림 8에서 확인할 수 있듯이, 그때의 거리는 \[ d_x (\theta) = \frac{1}{\cos \theta} \tag{2} \]가 됩니다.

그림 9. 수정된 두 번째 방법이 \( \tau < \theta < 2 \pi - \theta \)일 때 이동하는 거리의 예시.

두 번째는 직선 항해로 바로 해변에 도착하지 못하는 경우입니다. 이는 \( \tau < \theta < 2 \pi - \tau\)일 때 발생하게 됩니다. 그림 9에서 볼 수 있듯이, 이때 배가 이동하는 거리는 직선 거리에 원을 따라 돌아가는 거리를 더한 것이므로 \[ d_x (\theta) = x + x(\theta - \tau) \tag{3} \]라는 것을 알 수 있습니다.

 

식 2와 3을 활용하여 \( d_x (\theta) \)의 기댓값을 구하면, \[ \begin{array}{rl} \mathbb{E}_\theta [ d_x (\theta) ] & \displaystyle = \int_{-\tau}^{2\pi - \tau} d_x(\theta) \frac{1}{2 \pi} d\theta \\ & \displaystyle = \int_{-\tau}^{\tau} \frac{1}{\cos \theta} \frac{1}{2\pi} d\theta + \int_{\tau}^{2\pi - \tau} [x + x(\theta - \tau)] \frac{1}{2 \pi} d\theta \\ & \displaystyle = \frac{1}{\pi} \int_{0}^{\tau} \frac{1}{\cos \theta} d\theta + \frac{x}{2 \pi} \int_{\tau}^{2\pi - \tau} (\theta - \tau + 1) d\theta \\ & \displaystyle = \frac{ \ln [\sec \tau + \tan \tau] }{\pi} + x(\pi - \tau) \left( \frac{1 - \tau}{\pi} + 1\right) \end{array} \]가 됩니다. 이때, 세 번째 등식이 성립하는 이유는 \( \frac{1}{\cos \theta} \)가 짝함수(우함수)이기 때문이고, 마지막 등식이 성립하는 이유는 식 1 때문입니다.

 

과연 \( \mathbb{E}_\theta[d_x(\theta)] \)를 최소화시키는 \(x\)는 얼마일까요? 흥미롭게도 \(x \approx 1.141\)일 때, \( \mathbb{E}_\theta[ d_x(\theta) ] \approx 3.655 \)로 최솟값을 갖게 됩니다. 이는 위 절에서 구한 결과와 약간 다른 결과임을 알 수 있습니다. 위 절에서 이동하는 거리의 최댓값을 최소화하기 위해서는 \( x \approx 1.044 \)로 두어야 한다는 결과를 얻었습니다. 하지만 방향을 균등하게 고르는 방법이 이동하는 거리의 기댓값을 최소화하기 위해서는 \( x \approx 1.141 \)로 두어야 합니다. 목표가 무엇이냐에 따라서 전략이 바뀌게 되는 것을 확인할 수 있습니다.

 

그림 10. 거리 \(x\)에 대해 두 번째 방법이 최악의 경우 이동해야 하는 거리(빨간색)와 수정된 두 번째 방법의 이동 거리의 기댓값(초록색).  빨간색 선은 \(x \approx 1.044\)일 때 \(6.995\)의 최솟값을 가지며, 초록색 선은 \( x \approx 1.141 \)일 때 \( 3.655 \)의 최솟값을 갖는다. (https://www.desmos.com/calculator)

마치며

이번 글에서는 표류 중인 어부 문제를 함께 고민해 보았습니다. 참고로 최악의 경우에 이동해야 하는 거리를 더 줄이는 방법도 존재한다고 합니다. 같은 채널에 이 방법을 소개한 영상이 있는데, 관심 있으신 분들은 이 링크를 참조하시기 바랍니다.

 

간단하면서도 흥미로운 문제라고 생각해서 정리해 보았습니다. 이 문제를 소개해준 행님한테 다시 한 번 고맙다는 말을 전합니다. 혹여나 잘못된 점이 있거나, 궁금하신 점이 있으시면 댓글로 알려주시기 바랍니다. 읽어 주셔서 고맙습니다. :)

출처

모든 그림의 배[船] 아이콘은 Flaticon의 Freepik이 제작하였음을 밝힙니다.