자리의 무게가 오른쪽부터 1, −2, 4, −8이라면 0100의 값은 4이고 1000은 −8입니다. 왼쪽에 1이 있다는 이유만으로 큰 수라고 읽을 수 없어요. 이 규칙으로 쓴 모든 표기를 값의 크기대로 정렬하려면 어떻게 해야 할까요?
자체 문항에서는 길이 m을 고정하고 앞의 0도 유지해요. 각 자리는 0 또는 1이며 오른쪽 자리 번호를 0부터 세어요. 정수 거듭제곱의 반복 곱셈으로 자리값을 정해요.
홀수 번호 자리에서만 0과 1을 바꾼 새 표기를 만들어요. 이 표기를 보통 양의 이진 자리값으로 읽은 수를 U라 해 볼까요? 홀수 자리에서 U와 V의 차이는 원래 숫자와 관계없이 2^j입니다. 짝수 자리의 차이는 0입니다.
여기서 K_m은 m보다 작은 홀수 번호 j의 2^j를 모두 더한 일정한 수예요. 모든 값에 같은 수를 더했으므로 U의 순서가 곧 V의 순서예요. m=4이면 K_m=10이고 0100은 1110으로, 1000은 0010으로 바뀌어요. U는 각각 14와 2이므로 원래 값 4와 −8의 순서도 바로 확인돼요.
이 반전은 되돌릴 수 있어요. 따라서 모든 표기는 0부터 2^m−1까지의 U와 일대일로 대응해요. V의 값 전체는 −K_m부터 2^m−1−K_m까지 모든 정수이며 각 값은 한 번만 나타나요.
교사는 한 숫자의 변환에서 끝내지 않고, 일정한 차이가 전체 순서를 보존하는 이유까지 물어요. 이 방법은 길이를 고정한 비교예요. 길이가 다르면 K_m도 달라지므로 변환한 U만으로 바로 비교하지 않아요.
출처·착안: Exploding Dots 9.5 Going Really Wild. 원문의 관점을 참고해 질문·조건·논증을 새로 구성했다.