A에서 다른 지역으로 이사한 사람은 3명, B로 들어온 사람도 3명이에요. 그러면 A에서 B로 간 사람은 3명까지 가능할까요? 다른 지역의 합계가 그 답을 줄일 수 있어요.
실제 인구 자료 대신 다음 자체 표를 쓸게요. 두 시점의 거주 지역이 달라진 사람을 출발 지역과 도착 지역으로 한 번만 세어요. 같은 지역 안에서 주소만 바뀐 사람은 제외해요. A·B·C·D 밖으로 나가거나 밖에서 들어온 사람, 출생·사망, 중간에 몇 번 이사했는지는 이 모형에 넣지 않아요.
| 지역 | 다른 지역으로 나간 사람 | 다른 지역에서 들어온 사람 |
|---|---|---|
| A | 3 | 2 |
| B | 2 | 3 |
| C | 4 | 4 |
| D | 1 | 1 |
나간 사람도, 들어온 사람도 총 10명이에요. 이 합계들을 모두 만족하면서 A에서 B로 간 사람은 몇 명일 수 있나요? 최솟값과 최댓값뿐 아니라 그 사이의 모든 정수도 실제 이동표로 만들 수 있는지 확인해 볼까요?
일반적으로 지역 수는 정수 n≥2입니다. 지역 i의 출발 인원을 r_i, 도착 인원을 c_i라 하고 모두 0 이상의 정수로 둬요. 출발에서 도착으로 가는 표의 성분을 x_ij라 쓸게요. 대각선은 같은 지역으로 가는 칸이므로 모두 0입니다.
모든 지역의 합계가 함께 가능한 조건을 먼저 구하고, 가능할 때 서로 다른 두 지역 a,b의 x_ab가 가질 수 있는 모든 값을 구해 볼까요? 0인 합계나 총량 0도 제외하지 않아요.
처음의 표에서는 C에 들어온 4명과 C에서 나간 4명이 같은 이동일 수 없어요. 한 이동이 C에서 출발하면서 C에 도착한다면 제외한 대각선 칸이 되기 때문이에요. 그래서 전체 10번의 지역 간 이동 중 8번은 C에 들어가거나 C에서 나가요.
A에서 B로 간 이동은 C에 닿지 않아요. 따라서 그 수는 남은 2번보다 많을 수 없어요. A의 출발 3명과 B의 도착 3명만 보고 3명까지 가능하다고 한 답은 C의 조건을 빠뜨렸어요.
실제로 0·1·2명이 모두 가능해요. 다음 세 표에서 행은 출발, 열은 도착 지역이며 순서는 A·B·C·D입니다. 각각 A→B의 칸은 0·1·2이고, 모든 행과 열의 합계는 처음 표와 같아요.
따라서 답은 0·1·2명이에요. 합계가 같다는 사실만으로 표 전체가 같아지지는 않고, 원하는 한 칸의 범위에도 다른 지역들이 관여해요.
일반적인 합계의 양립 조건부터 볼까요? 한 지역 i에서 나간 r_i명은 도착 자리 c_i개를 사용할 수 없어요. 따라서 다음 조건은 필요해요.
이 조건은 충분하기도 해요. 충분성을 확인하려고 사람의 출발표와 도착 자리를 하나씩 구별해 놓아요. 지역 i의 출발표 r_i개와 지역 j의 도착 자리 c_j개 사이에는 i≠j일 때만 연결을 허용해요. 모든 출발표에 서로 다른 도착 자리를 붙이면 원하는 정수 이동표가 돼요.
여기에는 알려진 유한 짝짓기의 조건을 써요. 어떤 출발표들을 함께 골라도 그 표 수 이상으로 연결 가능한 도착 자리가 있어야 하고, 그 조건이 모든 선택에 맞으면 전체 짝짓기가 가능해요. 이 조건 자체를 새로운 발견으로 소개하지 않아요.
왜 충분한지는 짧게 증명할 수 있어요. 최대한 많이 짝지었는데 출발표 하나가 남았다고 해 볼까요? 그 표에서 가능한 자리로 간 뒤, 이미 쓰인 자리라면 그 자리의 출발표로 되돌아가는 길을 따라가요. 비어 있는 자리에 도달하면 그 길을 따라 짝을 뒤집어 하나 더 붙일 수 있으므로 최대라는 가정에 어긋나요.
비어 있는 자리에 도달하지 못하면 도달한 자리들은 모두 도달한 출발표들과 짝이에요. 처음의 남은 표만 짝이 없으므로 도달한 출발표가 자리보다 하나 더 많아요. 도달한 표에서 가능한 모든 자리도 이미 이 집합 안에 있어요. 따라서 그 출발표들의 자리 수가 부족하다는 뜻이고, 처음의 조건에 어긋나요. 이로써 조건의 충분성이 증명됐어요.
같은 지역의 출발표들은 가능한 도착 지역이 같아요. 출발표 일부를 골랐을 때 그 표들이 속한 지역의 출발표를 전부 추가해도 연결 가능한 도착 지역은 변하지 않아요. 따라서 지역 묶음별 조건만 검사해도 돼요.
지역 하나 i만 고르면 도착 자리 수는 T−c_i입니다. 앞의 부등식이 정확히 이 조건이에요. 서로 다른 지역을 둘 이상 고르면 어느 도착 지역에도 그곳과 다른 출발 지역이 하나 이상 있어요. 도착 자리 전체 T개를 사용할 수 있고, 골라 놓은 출발표 수는 T 이하라서 더 검사할 조건이 없어요. 모든 지역의 합계가 같은 T이고 r_i+c_i≤T이면 실제 정수 표가 존재해요.
이제 합계가 가능한 상태에서 x_ab=t를 지정하자. 그 칸에 t명을 먼저 놓은 뒤 지역 a의 남은 출발표를 r_a−t개, 지역 b의 남은 도착 자리를 c_b−t개로 바꿔요. 남은 총량은 T−t입니다. 남은 표에서는 a→b도 더 이상 사용할 수 없게 막아야 그 칸이 정확히 t로 끝나요. 따라서 t≥0이고 t≤r_a,c_b여야 해요.
지역 a의 남은 출발표는 a와 b의 도착 자리를 모두 피해야 해요. 사용할 수 있는 자리 수는 T−c_a−c_b이므로 첫 번째 하한을 얻어요. 또한 출발 지역 a와 b를 함께 골랐을 때에는 둘 다 도착 지역 b를 사용할 수 없어요. 이 두 지역의 표 수에서도 두 번째 하한이 나와요.
지역 i가 a,b 둘 다 아니면 그곳의 출발 r_i개는 남은 도착 자리 T−t개 중 자기 지역 c_i개를 피해야 해요. 이것은 t≤T−r_i−c_i라는 상한이에요.
다른 조건을 놓치지는 않았을까요? 남은 표에서 금지하는 도착 지역은 출발 a에게 a,b 두 곳, 다른 출발 i에게는 자기 지역 i 한 곳이에요. 출발 지역 두 곳을 함께 골랐을 때 공통으로 금지된 도착 지역이 남는 것은 a,b 쌍뿐이에요. 그 밖의 두 지역 묶음과 모든 세 지역 이상 묶음은 도착 자리 전체를 사용할 수 있어요. 그들의 출발표 수는 남은 총량 이하라서 추가 제약을 주지 않아요. 출발 지역 b 하나의 조건은 r_b≤T−c_b로, 이미 맞춰 둔 원래 합계 조건이에요.
그러므로 n≥3에서 가능한 값은 다음 두 끝점 사이의 모든 정수입니다.
끝점 식만 비교해서 중간값을 가능하다고 선언한 것은 아니에요. L≤t≤U인 정수 하나를 고르면 남은 표의 모든 지역 묶음 조건이 맞아요. 앞에서 증명한 짝짓기로 실제 정수 표를 만든 뒤 a→b의 t명을 돌려놓으면 돼요. 따라서 양끝뿐 아니라 그 사이의 정수 하나하나가 모두 달성돼요. 실수 표 두 개를 평균 내어 인원수를 소수로 만드는 논증도 필요 없어요.
처음의 표에는 L=0이고 U=min(3,3,2,8)=2입니다. C의 출발·도착 합계 8이 상한을 2로 줄였어요. 또 출발과 도착 합계가 모두 (3,1,1,1)이고 T=6인 자체 표에서는 A→B의 L=U=1입니다. 이때 그 한 칸은 합계만으로 1명이라고 정해져요. 일반적으로 한 칸의 값이 유일한 조건은 L=U입니다. 표 전체의 유일성까지 같은 조건으로 주장하지 않아요.
지역이 두 곳뿐이면 이동은 서로의 지역으로만 가요. 가능한 합계라면 r_1=c_2, r_2=c_1이고 두 대각선 밖 칸이 바로 정해져요. 위 식에서 a,b 밖의 지역에 대한 최소를 빼고 읽어도 같은 답이지만, 두 지역 경우를 먼저 따로 계산하면 더 쉬워요.
총량 T=0이면 모든 성분이 0입니다. 출발 r_a나 도착 c_b가 0인 칸도 0으로 정해져요. 다른 지역의 합계가 0인 경우에도 짝짓기 증명과 끝점 조건은 그대로 맞아요. 반대로 출발·도착 총량이 다르거나 어떤 r_i+c_i가 T를 넘으면, 그 합계로는 표가 처음부터 존재하지 않아요. 없는 표에 한 칸의 범위 식을 적용해서는 안 돼요.
교사는 A의 출발 합계와 B의 도착 합계만 가리고 먼저 범위를 예상하게 한 뒤, C의 출발·도착 합계를 보여 줄 수 있어요. C에 닿는 이동이 왜 겹칠 수 없는지 설명하고, 가능한 값에는 실제 표를 붙이게 해요. 한 칸을 알아내는 것과 표 전체를 복원하는 것도 구별해요.
착안: 아일랜드 Central Statistics Office, Census of Population 2022 Profile 1의 Internal Migration에서 이전 거주 지역과 도착 지역을 구별하는 관점을 읽었어요. 공식 자료의 수치·지도·사진은 옮기지 않았어요. 지역 간 두 시점의 이동만 세는 조건, 인원수 예시, 정수 표와 전체 범위 증명은 자체 교육용 구성이에요.