사다리타기는 자리바꿈의 원리 노하우, 사다리타기는 왜 중복이 되지않는것일까요??

사다리타기 게임의 원리

사다리 타기는 돈 낼 사람을 정할 때, 상을 줄 때, 혹은 짝짓기를 할 때 자주 동원하는 방법이다. 사다리 타기를 할 때에는 위쪽과 아래쪽에 동일한 개수의 항목을 적어놓고 세로줄과 가로줄을 그린 뒤, 다음 두 가지 규칙을 따라 짝을 짓는다.

첫째, 세로줄의 위에서 아래로 진행한다. 둘째, 세로줄을 따라 가다 가로줄을 만나면 그 가로줄을 따라 바로 옆의 세로줄로 이동한다.


그림의 모양이 복잡해지면 혹시 술래로 두사람이 나오거나, 한 항목이 여러 개와 연결되거나, 아무 것과도 연결되지 않는 '꽝'이 나올지 모른다는 생각이 들기도 한다. 그러나 예상과 달리, 어떤 모양으로 사다리를 그려도 각기 위와 아래 항목이 하나씩만 짝지어진다는 사실에는 변함이 없다. 이런 이유로 사다리 타기는 반드시 하나씩만 연결되어야 하는 상황에 이용된다.


1, 2, 3, 4 와 a, b, c, d 를 짝짓기 위하여 위의 왼쪽 그림과 같이 사다리 타기를 한다고 가정해보자. 앞의 규칙에 따라 이동을 하면 1은 b와 c를 거쳐 d로 연결된다. 또 2는 c를 거쳐 b로 연결되며, 3은 d를 거쳐 c로, 4는 c와 b를 거쳐 a로 연결된다(아래 단의 a, b, c, d가 일렬이 되게).


오른쪽 그림과 같이 사다리를 각 단계별로 나누어 보면(점선으로 표시) 하나의 세로선은 옆의 세로선과 연결되어 있다. 이를 통해 바로 옆의 것과 자리바꿈을 하는데, 수학적으로는 '호환'이라고 한다.


이러한 자리바꿈을 두세 번 반복하여도 서로 하나씩 맞바꾼다는 점에는 변화가 없다. 수학적으로 표현하면 '호환'을 '합성'하여도 서로 하나씩만 대응되는 '일대일 대응'이 된다. 따라서 처음에 일대일 대응으로 시작하면 아무리 복잡한 사다리를 거치더라도 그 결과는 일대일 대응이 된다.