Some Generalizations of the Bridge and Torch Problem

가장 흥미로운 퍼즐이 숨겨진 보물을 찾는 것이나 살인 사건을 해결하는 것이 아니라, 해가 뜨기 전까지 친구 무리가 어둡고 위태로운 다리를 건너는 것이라고 상상해 보십시오. 이것은 조합 최적화(combinatorial optimization)의 영역으로, 이 분야는 "엄격한 규칙이 있을 때 무언가를 수행하는 가장 완벽한 방법은 무엇인가?"라는 질문을 던집니다. 이것을 궁극의 테트리스 게임이라고 생각하십시오. 다만 블록 대신 사람들을 시간대에 맞추어 끼워 넣는 것이며, 목표는 가능한 한 짧은 시간 안에 레벨을 완료하는 것입니다. 이 게임의 고전적인 버전인 "다리와 횃불 문제(Bridge and Torch Problem)"는 기만적일 정도로 단순한 규칙으로 유명합니다. 한 무리의 사람들이 단 하나의 손전등만을 가지고 밤에 다리를 건너야 합니다. 다리는 좁아서(한 번에 두 명만 가능) 동시에 건널 수 없고, 누군가 건널 때마다 반드시 손전등을 지녀야 하며, 두 사람이 함께 건널 경우 두 사람 중 더 느린 사람의 속도에 맞춰 이동해야 합니다. 쉬워 보이지만, 가장 빠른 일정을 찾는 것은 타이밍과 전략의 까다로운 춤과 같아서 많은 이를 곤혹스럽게 만들었습니다.

이제 그 똑같은 퍼즐을 가져와서 난이도를 높여본다고 상상해 보십시오. 만약 다리가 세 명까지 수용할 수 있다면 어떨까요? 혹은 단 하나의 다리 대신, 거미줄처럼 여러 개의 바퀴살이 달린 허브 형태의 구조라면 어떨까요? 사람들이 동시에 서로 다른 목적지로 건너갈 수 있는 구조 말입니다. 이것이 바로 Thang Pang Ern과 Gerard Sayson이 논문에서 탐구한 내용입니다. 그들은 모든 사람이 1부터 $n$까지의 특정 횡단 시간을 가진 고전적인 "2인용 다리" 퍼즐을 단순히 해결한 것에 그치지 않고, 어떤 인원수에도 적용되는 정확한 최소 시간을 예측하는 마법 같은 공식을 찾아냈습니다. 그 후 그들은 경계를 더 넓혀, 세 명을 수용하는 다리에 대한 규칙과 별 모양의 경로 네트워크에 대한 규칙까지 파악했습니다. 그들은 답이 복잡해질 수는 있지만, 하나의 방정식으로 쓸 수 있는 아름답고 반복적인 패턴을 따른다는 사실을 발견했습니다.

고전적인 2인 댄스

먼저 원래의 퍼즐부터 시작해 봅시다. $n$명의 사람들이 있고, 그들의 횡단 시간은 단순히 숫자 $1, 2, 3, \dots, n$입니다. 시간이 1인 사람은 스프린터이고, 시간이 $n$인 사람은 느림보입니다. 목표는 모든 사람을 왼쪽 강변에서 오른쪽 강변으로 옮기는 것입니다.

저자들은 이 특정한 설정에 대해, 최소 시간 $T(n)$을 계산할 수 있는 완벽한 폐쇄형 공식(closed-form formula)이 존재함을 증명했습니다. 이는 단순한 추측이 아닙니다. 그들은 문제를 더 작은 덩어리로 나눔으로써 이를 도출했습니다. 그들은 최적의 전략이 가장 빠른 두 사람(1과 2)을 먼저 보내고, 그중 한 명이 횃불을 들고 돌아오며, 가장 느린 두 명을 함께 보내고, 그다음 다른 빠른 사람이 돌아오는 방식이라는 것을 깨달았습니다. 이 "블록" 형태의 움직임은 가장 느린 두 명을 처리하고 남은 그룹에 대해 과정을 반복할 준비를 마칩니다.

이러한 블록들의 비용을 모두 더함으로써, 그들은 $n$명의 총 시간 $T(n)$을 다음과 같이 찾아냈습니다:
$$T(n) = \frac{n^2}{4} + 3n - \frac{5 + (-1)^n - 1}{8}$$
이 공식은 $n \ge 2$인 모든 인원수에 대해 작동합니다. 그들은 생성된 시간의 수열(1, 2, 6, 11, ...)이 수학계에서 알려진 패턴임을 언급하면서도, 왜 이 특정 공식이 작동하는지에 대한 신선하고 직접적인 증명을 제공했습니다. 흥-미롭게도, 그들은 가장 빠른 사람이 다른 모든 사람과 함께 계속 왔다 갔다 하는 "표준" 전략이 항상 최선은 아니라는 점을 보여주었습니다. 예를 들어, 4명의 경우 표준 방식이 영리한 "블록" 방식보다 더 오래 걸립니다.

세 명을 수용하는 다리

다음으로 저자들은 "다리가 더 넓어진다면 어떨까?"라고 물었습니다. 그들은 다리가 한 번에 최대 3명까지 수용할 수 있지만, 여전히 손전등은 하나뿐인 상황을 가정했습니다. 이는 게임의 양상을 완전히 바꿉니다. 세 명의 경우, 세 명의 그룹을 보낼 수는 있지만 여전히 누군가는 빛을 가지고 돌아와야 합니다.

그들은 이 "수용량 3" 버전의 경우, 최적의 시간 $T_3(n)$이 다른 더 복잡한 리듬을 따른다는 것을 발견했습니다. 이 공식은 이차 곡선(예: $n^2/6$)과 코사인 및 $(-1)^n$을 포함한 물결치는 파동 항의 혼합을 포함합니다. 구체적으로 $n \ge 7$일 때, 시간은 다음과 같습니다:
$$T_3(n) = \frac{n^2}{6} + 2n - \frac{181}{36} + \frac{(-1)^n}{4} - \frac{2}{9} \cos\left(\frac{2n\pi}{3}\right)$$
이 공식은 매우 독특하여 온라인 정수 수열 사전(OEIS)에 새로운 수열(A392834)을 만들어냈습니다. 저자들은 최적의 전략이 6명씩 그룹을 지어 특정 주기로 이동하며, 문제를 $n$명에서 $n-6$명으로 예측 가능한 비용을 더하며 줄여나가는 방식임을 보여줌으로써 이를 증명했습니다. 또한 공식이 시작 부분과 잘 맞는지 확인하기 위해 작은 숫자들(1에서 6까지)을 브루트 포스(brute force) 방식으로 확인했습니다.

그들은 4명을 수용하는 다리에 대해서도 잠시 살펴보았지만, 패턴이 매우 복잡해져서 아직 간단한 공식을 찾지 못했다고 인정했습니다. 그들은 공식이 존재할 것이라고 추측하지만, 이를 찾는 것은 훨씬 더 어렵습니다.

별 모양의 네트워크

마지막으로, 이 논문은 단일 다리에서 벗어나 거대한 도약을 시도합니다. 중앙 허브(기차역 같은)가 있고, 여러 개의 도로(바퀴살)가 다양한 목적지(잎 노드)로 연결되어 있다고 상상해 보십시오. 이것을 "스타 그래프(star graph)"라고 부릅니다. 이 버전에서는 $n$명의 사람이 중앙에 있고, $k$개의 도로가 있으며, $t$개의 손전등이 있습니다.

여기의 규칙은 조금 다릅니다: 한 "단계(step)"에서, 두 사람이 같은 도로를 사용하지 않고 한 사람이 두 곳에 동시에 존재하지 않는 한, 서로 다른 도로를 통해 사람들을 동시에 보낼 수 있습니다. 그 단계의 시간은 해당 단계에서 움직이는 가장 느린 사람에 의해 결정됩니다.

저자들은 최소 시간이 손전등과 도로의 개수에 크게 좌우된다는 것을 발견했습니다. 만약 모든 사람을 한 번에 보낼 수 있을 만큼 충분한 손전들과 도로가 있다면, 시간은 단순히 가장 느린 사람의 시간($n$)이 됩니다. 하지만 제한이 있다면, 시간은 대략 $n^2$에 비례하여 증가합니다. 그들은 다음과 같은 하한(lower bound) 공식을 도출했습니다:
$$T(n, k, t) \ge sn - ms(s-1)$$
여기서 $m$은 도로 수와 손전등 수 중 더 작은 값이며, $s$는 모든 사람을 내보내는 데 필요한 "라운드"의 수입니다.

이 섹션의 가장 멋진 부분 중 하나는 이 문제가 순수 수학과 어떻게 연결되는가 하는 점입니다. 스타 그래프 문제에서 생성된 숫자들을 살펴볼 때, 그들은 "바닥 함수(floor function, 숫자를 내림하는 함수)"와 관련된 유명한 수학적 항등식들을 재현하고 있다는 것을 깨달았습니다. 예를 들어, 특정 인원수와 도로 수에 대해 퍼즐을 해결함으로써, 그들은 알려진 바닥 함수의 합에 관한 항등식을 "재발견"했으며, 이는 재미있는 스케줄링 퍼즐이 어떻게 수의 패턴에 관한 깊은 진리를 드러낼 수 있는지를 보여줍니다.

요약하자면, 이 논문은 고전적인 수수께끼를 가져와 정밀한 공식으로 해결하고, 더 넓은 다리로 확장하며, 다시 다중 경로 네트워크로 회전시키면서 그 과정에서 숨겨진 수학적 아름다움을 발견해 냅니다. 이는 단순한 다리 건너기 게임 안에서도 전략과 구조의 층위가 기다리고 있음을 보여줍니다.