지류 열여섯 개가 모인 강, 합류 순서에 따라 등급도 달라질까요?

지류 열여섯 개가 하나로 모인 강을 두 개 그린다고 해 볼까요? 지류의 개수가 같으면 출구에서의 등급도 같을까요? 합류 순서까지 알아야 할 수 있어요.

실제 강의 측량 자료 대신, 합류를 나타내는 자체 연결 그림을 정해요. 처음 시작하는 지류는 모두1등급이에요. 한 합류점에는 두 물줄기만 들어오고 하나가 나가요. 같은 등급 두 개가 만나면 등급이1 올라가고, 다르면 큰 쪽 등급을 그대로 써요.

그림은 하나의 출구를 가진 유한 나무다. 물줄기가 갈라지거나 되돌아오는 길, 호수, 한 물줄기만 통과하는 합류점은 넣지 않아요. 시작 지류의 수를 n, 출구 등급을 k라 해 볼까요? 시작점에서 출구까지 거치는 합류점 수를 모든 경로에서 세고, 그중 가장 큰 값을 H라 해요. H는 실제 거리도, 모든 경로의 공통 길이도 아니에요.

지류가16개이고 가장 긴 경로가 정확히 다섯 합류 단계인 그림에서, 출구는 몇 등급일 수 있나요? 가능한 등급마다 실제 그림을 만드는 방법도 제시해 보세요. 정보가 ‘다섯 단계 이하’로 바뀌면 답도 바뀌나요?

더 일반적으로 모든 정수 H≥0,n≥1,k≥1에서 이 세 값이 함께 가능한 조건을 구해 볼까요? 최소와 최대만 비교하지 말고, 그 사이의 지류 수가 빠짐없이 만들어지는지도 증명해요. 이 조건은 교육용 연결 모형이며 실제 하천의 유량이나 홍수를 예측하는 것이 아니에요.

먼저 두 가지 수를 구별해 봐요. 지류의 수 n은 전체 시작점 수예요. 등급 k는 같은 등급끼리 몇 차례 모였는지에 따라 달라져요. 큰 등급에1등급 지류를 계속 붙이면 지류 수와 합류 깊이는 늘어도 큰 등급은 그대로예요.

k등급을 만드는 데는 적어도2^(k−1)개 지류가 필요해요. 같은 k−1등급 두 개가 만나 k등급을 처음 만들기 때문이에요. 또 그 등급까지 올라간 한 경로에는 적어도 k−1번의 합류가 있어야 해요. 이 두 알려진 하한만으로는 H가 더 클 때의 답을 전부 정하지 못해요.

다음 두 수를 정의할게요. C(H,i)는 이항계수이며 i>H이면0으로 둬요.

H=0이면 합류점이 없으므로 n=k=1입니다. H≥1에서는 2≤k≤H+1이고 m(H,k)≤n≤M(H,k)일 때, 그리고 그때만 세 값이 함께 가능해요. 여기의 H는 정확한 최장 단계예요.

왜 위쪽 한계에 이항계수가 나올까요? 잠시 등급은 k 이하, 최장 단계는 H 이하라는 더 넓은 그림들을 생각해 봐요. 가능한 최대 지류 수를 M(H,k)라 해요. 등급1만 허용하면 지류 하나뿐이고, 합류가0단계여도 하나뿐이에요. 그 밖의 그림을 출구의 두 작은 그림으로 나눠요.

두 작은 그림의 등급은 모두 k 이하이며, 적어도 한쪽은 k−1 이하예요. 양쪽이 모두 k등급이면 출구가 k+1이 되어버리기 때문이에요. 높이는 각자 H−1 이하이므로 최대 지류 수는 두 용량의 합이에요.

M(0,k)=M(H,1)=1에서 시작해 이 식을 반복하면 앞의 이항계수 합이 나와요. 제공 교재의 이항계수는 이 표기를 설명하는 기초예요. 합류 등급의 정의와 이 용량식은 알려진 나무의 성질을 쓰는 것이며 새 학술 정리라고 주장하지 않아요.

이 넓은 조건에서는1부터 M(H,k)까지 모든 지류 수를 만들 수 있어요. 작은 두 그림이 각각1부터 자기 용량까지의 모든 수를 가진다고 해 볼까요? 합친 지류 수는2부터 두 용량의 합까지 빠짐없이 나와요. 지류 하나는 합류 없는 그림이에요. 작은 높이부터 이 구성을 반복하면 중간 지류 수에도 빈틈이 없다는 것이 증명돼요.

이제 정확한 높이 H와 등급 k의 아래쪽 한계를 볼까요? H=k−1이면 지류 수는2^(k−1)로 고정돼요. 등급 하한만큼은 필요하고, 그 높이의 이진 나무에는2^H개보다 많이 담을 수 없기 때문이에요. 완전히 균형 잡힌 합류가 실제로 그 값을 만들어요.

H가 더 크면 작은 그림의 경우를 나누어 m(H,k) 이상의 지류가 필요함을 보여요. 가장 깊은 경로가 들어 있는 작은 그림의 높이는 H−1입니다. 그쪽 등급이 k이면 이전 높이의 최소 지류 수에 다른 쪽 지류 하나 이상이 더해져 m(H−1,k)+1=m(H,k)입니다.

어느 작은 그림도 k등급이 아니면 둘 다 k−1등급이어야 해요. k≥3에서는 깊은 쪽에 m(H−1,k−1), 다른 쪽에2^(k−2)개가 필요해 합이 m(H,k)입니다. k=2에서 두 쪽이 모두1등급이면 H=1뿐이라 앞의 출발 경우에 포함돼요.

남은 경우는 깊지 않은 쪽이 k등급이고 깊은 쪽은 더 작은 등급인 때예요. k등급 쪽은2^(k−1)개 이상을 가져요. 높이 H−1인 다른 쪽은 적어도 H개 지류를 가져요. 가장 긴 경로의 합류점마다 옆에 지류가 하나 이상 있어야 하기 때문이에요. 따라서 이 경우에도2^(k−1)+H≥m(H,k)입니다. 출구를 만들 수 있는 경우를 모두 나누었으므로 아래쪽 한계가 필요하다는 것이 증명됐어요.

하한과 상한 사이의 모든 정수 n도 만들 수 있을까요? H≥k일 때, 한쪽에 높이가 정확히 H−1이고 등급이 k인 작은 그림을 둬요. 다른 쪽은 높이가 H−1 이하이고 등급은 k−1 이하인 그림으로 둬요. 첫 그림 때문에 합친 높이가 정확히 H가 되고, 두 등급이 다르므로 출구는 k등급을 유지해요.

첫 그림의 지류 수 p는 m(H−1,k)부터 M(H−1,k)까지, 두 번째의 q는1부터 M(H−1,k−1)까지 모두 가능해요. 합 p+q는 m(H,k)부터 M(H,k)까지의 모든 정수가 돼요. 원하는 n에 맞춰 실제로 나누는 식도 있어요.

n이 허용 범위 안이면 p와 q도 각자의 범위 안이에요. p는 두 번째 용량을 넘치지 않게 선택되고, n≥m(H−1,k)+1이므로 q≥1입니다. n≤두 용량의 합이어서 p도 첫 용량을 넘지 않아요. 더 작은 높이의 그림을 이렇게 다시 나누고, 마지막 균형 그림이나 지류 하나에 도달하면 원하는 합류 그림이 만들어져요. 이는 양 끝만 보여 주는 예가 아니라 모든 중간 정수를 위한 구성이에요.

처음의 H=5,n=16을 표로 확인해 볼까요?

16이 들어 있는 등급은3과4뿐이에요. 3등급은 최장 네 단계인3등급·지류11개 그림과2등급·지류5개 그림을 합쳐 만들어요. 앞의 용량 구성을 쓰면 두 그림을 만들 수 있고, 마지막 합류 뒤 최장 단계가5가 돼요.

4등급도 만들 수 있어요. 지류8개를 완전히 균형 있게 합쳐4등급·세 단계로 만든 뒤, 지류 하나를 더 합쳐4등급·네 단계·9개로 만들어요. 여기에 최장 세 단계인3등급·지류7개 그림을 합쳐요. 결과는 지류16개,4등급, 정확히 다섯 단계예요.

반대로5등급은 처음부터16개가 필요하지만, 정확한 높이가5이면 최소17개여야 한다.16개를 모두 균형 있게 모으면5등급을 얻지만 최장 단계는4입니다. 그래서 ‘다섯 단계 이하’로 바꾼 질문에서는5등급도 가능해진다. 그때의 답은3·4·5등급이에요.

일반적인 ‘H단계 이하’에서 k등급을 만드는 지류 수 범위는2^(k−1)부터 M(H,k)까지예요. 정확한 높이 j=k−1,k,…,H에서의 범위를 합치면 돼요. 다음 높이의 최소는 이전 최소보다1 클 뿐이고 이전 최대는 그 이전 최소 이상이므로, 두 정수 범위 사이에는 빠지는 수가 없어요. 단 k=1은 높이 상한이 얼마든 합류 없는 지류 하나뿐이에요.

모든 경로가 H단계라는 뜻으로 바꾸면 또 다른 문제가 돼요. 이번 조건은 가장 긴 경로 하나가 H단계이고 나머지는 더 짧아도 돼요. 실제 지도에서도 경로 길이, 지류 수, 등급을 서로 같은 숫자로 다루지 않는 것이 중요해요.

교사는 먼저 시작점 수 n, 최장 합류 횟수 H, 출구 등급 k를 서로 다른 색으로 표시하게 해요. 등급의 알려진 계산법을 적용한 뒤, 가능한 범위의 양 끝과 그 사이의 그림을 만드는 방법을 구분해 확인해요. 실제 흐르는 물의 양이나 생태 상태를 등급만으로 계산한 활동은 아니에요.

착안: NSW Government Water, An introduction to Strahler stream order. 원문의 같은 등급·다른 등급 합류 규칙을 배경으로 삼았어요. 정확히 두 물줄기만 합치는 유한 나무, 최장 합류 단계, 지류 수의 모든 가능 조합은 자체 교육용 질문과 증명이에요. 원문의 도판·사진·홍수 설명·법적 허가 안내는 옮기지 않았어요.