사다리타기에는 누구도 의심하지 않는 암묵의 약속이 하나 있다. "두 사람이 같은 곳에 도착하는 일은 없다." 이 약속은 우연이 아니라, 수학적으로 반드시 성립한다.
왜 그럴까. 답은 가로줄 하나의 정체에 있다. 사다리에서 가로줄 한 개는 '이웃한 두 세로줄의 자리를 맞바꾸는 것'과 정확히 같다. 수학에서는 이렇게 두 원소만 자리를 바꾸는 연산을 호환(互換, transposition)이라 부른다. 아래로 내려가며 가로줄을 하나 만날 때마다, 이동 중인 두 갈래가 서로 자리를 한 번 맞바꾸는 것이다.
맞바꿈(호환)의 결정적 성질은 되돌릴 수 있다는 것이다. 두 자리를 바꿨다면, 같은 자리를 한 번 더 바꾸면 원래대로 돌아온다. 되돌릴 수 있는 연산은 일대일 대응(전단사, bijection)이다. 그리고 일대일 대응을 여러 번 이어 붙여도 결과는 여전히 일대일 대응이다.
사다리 전체는 결국 이런 맞바꿈을 위에서 아래로 죽 이어 붙인 것에 지나지 않는다. 그러므로 출발점 전체와 도착점 전체 사이에는 언제나 완벽한 일대일 대응이 성립한다. 즉 (1) 서로 다른 두 출발점은 절대 같은 곳에 도착하지 않고, (2) 모든 도착점은 빠짐없이 누군가에게 배정된다. 사다리타기의 '공정함'은 바로 이 두 문장이다.
결과가 겹치지 않는다는 것과, 원하는 어떤 결과든 나올 수 있다는 것은 다른 이야기다. 다행히 후자도 참이다. 수학에는 "임의의 순열(順列)은 이웃한 것들의 맞바꿈을 여러 번 반복해 만들 수 있다"는 정리가 있다. 정렬 알고리즘 중 버블 정렬이 정확히 이 원리로 작동한다. 뒤집어 말하면, 가로줄만 충분히 그으면 사다리는 어떤 순서(배열)든 표현할 수 있다. 자리를 완전히 뒤바꾸는 극단적인 결과조차, 가로줄을 알맞게 배치하면 만들어진다.
한 가지는 짚어 두자. 가로줄을 무작위로 그었을 때 나올 수 있는 모든 순서가 완벽히 같은 확률로 나오는 것은 아니다. 가로줄이 적으면 이동 폭이 좁아 가까운 자리로 갈 확률이 높다. 다만 가로줄(복잡도)을 늘릴수록 분포는 점점 고르게 퍼진다. 그래서 사다리를 '더 복잡하게' 섞을수록 결과는 더 무작위에 가까워진다. 핵심은, 균등함은 복잡도에 달려 있어도 '겹치지 않음'은 가로줄이 한 개든 백 개든 항상 보장된다는 점이다. 700년을 살아남은 놀이의 공정함에는, 이렇게 단단한 수학이 깔려 있다.
🪜 복잡도를 높여 직접 확인하기 →