세 집단 A, B, C의 규모가 모두 1이다. 처음 각 집단에 한 자리를 주고, 이후 아래 우선순위가 가장 큰 집단에 한 자리씩 더한다. a_i는 그 집단의 현재 자리 수다. 총자리 4 때 동점은 A부터, 총자리 5 때는 B, C, A 순으로 처리해 처음부터 다시 계산한다. 총자리를 늘리면 어느 집단도 줄지 않는가? 두 계산 모두 같은 동점 순서를 쓸 때의 일반 결론도 증명하라.
처음 세 우선순위는 모두 1/√2다. 총자리 4 계산은 A에 추가하여 (2,1,1)로 끝난다. 총자리 5 계산은 B에 먼저 추가한다. 그러면 B의 우선순위만 1/√6으로 내려가고 A, C는 1/√2여서 C가 다음 동점에서 이긴다.
추가 자리마다 기존 것을 빼지는 않았는데 서로 다른 두 재계산을 비교하면 A가 한 자리 줄었다. 앞 계산의 배분 경로를 이어 간 것이 아니기 때문이다.
반대로 규모들·초기배분·동점 순서를 두 계산에서 고정하면 첫 추가 자리의 선택이 같고, 그 결과 상태도 같다. 상태가 같을 때 다음 우선순위와 동점 선택이 같으므로 귀납적으로 같은 추가 단계까지 모든 선택이 일치한다. 총자리 하나가 더 많은 계산은 이 동일한 경로 뒤에 한 자리만 더한 것이어서 어느 집단도 줄지 않는다. 이는 규모가 서로 달라도 성립한다.
Census는 우선순위로 다음 자리를 배정하는 계산을 설명한다. 총량에 따라 동점 순서를 바꾸는 절차는 이 글에서 만든 비교용 변형이며 실제 Census가 그런 처리를 한다거나 실제 동점 사례를 보고한 것이 아니다.
교사는 “하나씩 더했으니 줄지 않는다”라는 문장에 두 계산이 같은 접두부를 공유하는 조건을 붙이게 한다. 종료 목표만 바뀌었는지, 앞 단계의 결정 규칙까지 바뀌었는지를 확인하면 말로만 보인 단조성 증명이 왜 실패하는지 드러난다.
착안 원문: U.S. Census Bureau: Computing Apportionment. 집단 규모와 총자리 수, 동점 처리 순서의 비교는 자체 교육용 예이며 실제 Census 배분이나 실제 동점 사례를 보고한 것이 아니다.