홀짝 분할은 충돌 없음과 모든 방의 도달을 동시에 보장한다.

그림에서 무엇을 볼까요?

생각그림 8 · 홀짝 분할은 충돌 없음과 모든 방의 도달을 동시에 보장한다.

배정표가 그럴듯해 보여도 두 검사를 통과해야 한다. 첫째, 기존 손님 두 명은 서로 다른 짝수 방으로 가고 새 손님 두 명은 서로 다른 홀수 방으로 가며, 홀수와 짝수는 겹치지 않는다. 따라서 한 방에 두 명이 배정되지 않는다. 둘째, 모든 양의 정수는 홀수이거나 짝수이므로 어느 방도 빠지지 않는다. 짝수 2r에는 기존 r번 손님이, 홀수 2r−1에는 새 r번 손님이 정확히 들어온다. 이 역함수 확인까지 해야 “모두 수용했다”는 결론이 완성된다.