높은 고개를 피하는 길, 두 후보만 비교하면 될까요?

높은 고개를 피하려고 두 길을 비교했는데, 더 낮은 길이 둘 사이에 숨어 있다면? 교사는 종이에 다섯 지점 S·A·B·C·T를 표시해요. S에서 T로 갈 때, 가장 높은 곳의 고도를 가능한 한 낮추는 길을 직접 만들어 볼까요?

등고선은 같은 높이의 점을 이은 선이에요. 다음은 실제 지도를 읽어 추정한 값이 아니라 자체 길망이에요. 지점은 모두 고도 30m이고, 아래 일곱 길만 양방향으로 통해요. 각 숫자는 그 길 전체의 정확한 최고 고도(m)입니다. 지점을 되풀이해 방문하지 않아요.

한 경로를 P, 길 e의 최고 고도를 h(e)라 쓸게요. 제공 교재의 함수처럼 경로 하나에 최고 고도 하나를 대응시킨다. 높이들을 더하지 않고 그중 가장 큰 값을 H(P)로 정해요. 허용 상한 b도 m 단위이며

처음 제안한 S→A→T는 140m, S→B→C→T는 110m까지 오른다. 둘 중 고르면 두 번째지만, 이것으로 전체 최소라고 끝내도 될까요? SA 다음 AB로 건너가 BC·CT를 이어 볼까요?

답은 S→A→B→C→T입니다. 더 낮은 길이 없는 이유도 필요해요. T로 들어오는 마지막 길은 AT·BT·CT뿐이고 각각 140·120·100m입니다. 어느 경로도 100m 아래에 머물 수 없어요. 찾은 길이 그 하한을 실제로 달성해요.

100m 이하 길만 남기면 SA·AB·BC·CT가 한 줄로 이어져요. 반복 방문을 금한 조건에서 최소를 달성하는 경로는 이 하나뿐이에요. 교사는 ‘찾은 길’과 ‘더 낮은 길이 불가능한 이유’를 함께 적게 해요. 거리·누적 상승량·시간·안전은 주어진 최고 고도만으로 정하지 않아요.

착안: Ordnance Survey, Map Reading의 「Reading contours and relief」 두 쪽 전체. 일곱 길과 높이표는 자체 구성이고 원문 지도·도판은 옮기지 않았어요.