사다리타기는 왜 항상 1:1로 짝지어질까? 사다리에 숨은 수학
사다리타기를 해 본 사람이라면 한 번쯤 이런 생각을 해 봤을 거예요. 가로줄을 아무렇게나 잔뜩 그었는데도 왜 두 사람이 같은 칸에 도착하는 일은 한 번도 없을까? 가로줄이 두 개든 스무 개든, 참가자가 셋이든 열둘이든 결과는 언제나 정확히 한 사람에 하나씩 돌아가요. 우연처럼 보이지만 사실은 수학적으로 반드시 그렇게 될 수밖에 없는 구조예요.
이 글에서는 사다리타기에 숨어 있는 수학을 어렵지 않게 풀어 볼게요. 두 길이 절대 합쳐지지 않는 이유, 사다리와 순열·호환의 관계, 버블 정렬과의 뜻밖의 연결고리, 그리고 손으로 그린 사다리가 생각만큼 공정하지 않은 이유까지 차례로 살펴봐요.
사다리의 규칙 다시 보기
먼저 규칙을 정확히 짚고 넘어갈게요.
- 세로줄을 참가자 수만큼 긋고, 위쪽 끝에는 이름을, 아래쪽 끝에는 결과를 적어요.
- 이웃한 두 세로줄 사이에 가로줄을 여러 개 그어요.
- 각자 자기 세로줄 꼭대기에서 출발해 아래로 내려가다가, 가로줄을 만나면 반드시 그 줄을 따라 옆 세로줄로 건너간 뒤 다시 아래로 내려가요.
- 맨 아래에 도착한 칸이 그 사람의 결과예요.
여기에 암묵적인 규칙이 하나 더 있어요. 한 세로줄의 같은 높이에 양쪽으로 가로줄이 동시에 붙으면 안 된다는 거예요. 그런 지점에 도착하면 왼쪽으로 갈지 오른쪽으로 갈지 정할 수 없으니까요. 종이에 그릴 때 가로줄 높이를 조금씩 엇갈리게 긋는 것도 이 때문이에요. 이 규칙 덕분에 어떤 위치에서든 다음에 갈 길이 딱 하나로 정해져요.
두 길이 절대 합쳐지지 않는 이유
설명 1. 가로줄은 ‘자리 바꾸기’일 뿐이에요
참가자 모두가 동시에 출발해 같은 속도로 내려간다고 상상해 보세요. 누군가 가로줄을 만나면, 그 가로줄의 반대편 끝에 있던 사람도 같은 높이에서 같은 가로줄을 만나요. 두 사람은 가로줄을 따라 서로 반대 방향으로 건너가요. 결과적으로 가로줄 하나는 이웃한 두 사람의 자리를 맞바꾸는 일만 해요.
처음에는 세로줄마다 정확히 한 사람씩 서 있어요. 자리를 맞바꾸는 일은 몇 번을 반복해도 ‘세로줄마다 한 사람’이라는 상태를 깨뜨리지 않아요. 그러니 맨 아래에 도착했을 때도 세로줄마다 정확히 한 사람씩 서 있게 되고, 두 사람이 같은 결과를 받는 일은 생길 수가 없어요.
설명 2. 거꾸로 올라가도 길이 하나로 정해져요
이번엔 아래에서 위로 사다리를 거슬러 올라가 보세요. 올라가다 가로줄을 만나면 건너가는 규칙은 똑같이 적용되고, 역시 갈 길이 하나로 정해져요. 만약 두 사람의 길이 어느 지점에서 합쳐진다면, 그 지점에서 거꾸로 올라갈 때 갈 수 있는 길이 두 갈래가 되어야 해요. 하지만 거꾸로 가는 길도 항상 하나뿐이니 합쳐지는 지점은 존재할 수 없어요. 위에서 아래로도, 아래에서 위로도 길이 하나로 정해진다는 것이 바로 1:1 대응의 증거예요.
사다리는 ‘순열’을 만드는 기계예요
참가자 n명을 결과 n개와 1:1로 짝짓는 방법의 수를 수학에서는 순열이라고 하고, 그 개수는 n!(n 팩토리얼)이에요. 사다리 하나는 이 가운데 딱 한 가지 짝짓기를 만들어 내는 장치라고 볼 수 있어요.
| 참가 인원 | 가능한 짝짓기의 수 (n!) |
|---|---|
| 3명 | 6가지 |
| 4명 | 24가지 |
| 5명 | 120가지 |
| 6명 | 720가지 |
| 8명 | 40,320가지 |
| 10명 | 3,628,800가지 |
| 12명 | 479,001,600가지 |
그리고 앞에서 본 ‘이웃한 두 사람의 자리 바꾸기’를 수학에서는 호환(transposition)이라고 불러요. 즉 사다리는 호환을 위에서부터 차례로 이어 붙여 하나의 순열을 만드는 도구예요. 예를 들어 가, 나, 다 세 사람이 있고 위에서부터 ‘1–2번 줄 사이’, ‘2–3번 줄 사이’에 가로줄이 하나씩 있다면 다음과 같이 움직여요.
- 처음: 가 / 나 / 다
- 1–2번 사이 가로줄: 나 / 가 / 다
- 2–3번 사이 가로줄: 나 / 다 / 가
결국 가는 3번, 나는 1번, 다는 2번 결과에 도착해요. 가로줄 순서를 바꿔 ‘2–3번’을 먼저, ‘1–2번’을 나중에 그리면 다 / 가 / 나가 되어 전혀 다른 결과가 나와요. 같은 가로줄이라도 높이 순서가 결과를 바꾼다는 점이 흥미로운 부분이에요.
버블 정렬과 사다리의 뜻밖의 관계
프로그래밍을 배워 본 분이라면 버블 정렬을 들어 봤을 거예요. 줄지어 선 숫자에서 이웃한 두 수를 비교해 순서가 뒤바뀌어 있으면 맞바꾸는 일을 반복해 결국 전체를 정렬하는 방법이에요. 버블 정렬이 사용하는 동작은 오직 ‘이웃한 두 원소 맞바꾸기’뿐인데도 어떤 뒤죽박죽 배열이든 정렬해 낼 수 있어요.
이 과정을 거꾸로 돌려 보면 사다리에 대한 중요한 사실을 알 수 있어요. 이웃끼리의 맞바꾸기만으로 어떤 배열이든 정렬할 수 있다면, 반대로 정렬된 상태에서 출발해 이웃끼리의 맞바꾸기만으로 어떤 배열이든 만들 수 있어요. 다시 말해 가로줄만 적절히 그으면 n! 가지 짝짓기 중 어떤 것이든 사다리로 만들 수 있어요.
그렇다면 가로줄은 최소 몇 개가 필요할까요? 버블 정렬에서 맞바꾸기 횟수는 배열 안의 ‘순서가 뒤집힌 쌍’(역순쌍)의 개수와 같아요. 가장 많이 뒤집힌 경우는 순서가 완전히 거꾸로인 배열로, 역순쌍이 n(n−1)/2개예요. 그래서 참가자 순서를 완전히 뒤집는 사다리를 만들려면 가로줄이 적어도 n(n−1)/2개 필요해요. 5명이면 10개, 12명이면 66개예요. 반대로 말하면 가로줄이 적은 사다리로는 만들 수 없는 짝짓기가 있다는 뜻이기도 해요.
손으로 그린 사다리는 공정할까?
여기서 중요한 질문이 나와요. 종이에 대충 그린 사다리에서 모든 사람이 모든 결과를 받을 확률이 정말 같을까요? 답은 “가로줄이 충분히 많지 않으면 그렇지 않다”예요.
이유는 직관적이에요. 가로줄 하나를 만날 때마다 옆으로 딱 한 칸씩만 움직일 수 있어요. 맨 왼쪽에서 출발한 사람이 맨 오른쪽 결과에 도착하려면, 가로줄을 여러 번 만나면서 그때마다 오른쪽으로 건너가야 해요. 가로줄이 적으면 그런 경로가 드물기 때문에 사람들은 대체로 출발한 자리 근처에 도착하는 경향이 생겨요.
세 줄 사다리로 직접 계산해 보기
가장 단순한 3명짜리 사다리로 정확하게 계산해 볼게요. 가로줄을 하나씩 위에서부터 그리는데, 매번 동전을 던져 ‘1–2번 사이’ 또는 ‘2–3번 사이’ 중 한 곳을 같은 확률로 고른다고 해요. 이때 맨 왼쪽(1번)에서 출발한 사람이 각 결과에 도착할 확률은 다음과 같아요.
| 가로줄 수 | 1번 도착 | 2번 도착 | 3번 도착 |
|---|---|---|---|
| 1개 | 1/2 (50%) | 1/2 (50%) | 0 (0%) |
| 2개 | 1/2 (50%) | 1/4 (25%) | 1/4 (25%) |
| 3개 | 3/8 (37.5%) | 3/8 (37.5%) | 2/8 (25%) |
| 4개 | 6/16 (37.5%) | 5/16 (31.25%) | 5/16 (31.25%) |
| 5개 | 11/32 (약 34.4%) | 11/32 (약 34.4%) | 10/32 (31.25%) |
| 6개 | 22/64 (약 34.4%) | 21/64 (약 32.8%) | 21/64 (약 32.8%) |
표를 보면 두 가지를 알 수 있어요. 첫째, 가로줄이 적을 때는 가장 먼 3번 결과에 도착할 확률이 뚜렷하게 낮아요. 가로줄이 하나뿐이면 아예 0이에요. 둘째, 가로줄이 늘어날수록 세 확률이 모두 1/3(약 33.3%)에 빠르게 가까워져요.
그런데 재미있는 사실이 하나 있어요. 이 방식으로는 가로줄을 아무리 많이 그려도 확률이 정확히 1/3이 되지는 않아요. 가로줄이 k개면 가능한 그리기 방법이 2를 k번 곱한 수만큼 있고, 각 확률은 ‘(해당하는 경우의 수) ÷ (2를 k번 곱한 수)’ 꼴인데, 2를 몇 번 곱해도 3으로 나누어떨어지지 않으니까요. 한없이 가까워질 뿐, 완벽하게 같아지지는 않아요.
사람이 그리면 생기는 문제
현실의 종이 사다리에는 계산보다 더 큰 문제가 있어요.
- 그리는 사람이 결과를 짐작할 수 있어요. 가로줄을 긋는 사람이 원하는 결과가 나오도록 길을 조정할 수 있어요.
- 사람이 긋는 가로줄은 무작위가 아니에요. 가운데에 몰리거나 규칙적인 패턴이 생기기 쉬워요.
- 사다리를 본 뒤 출발 위치를 고르면 눈썰미 좋은 사람이 길을 미리 따라가 볼 수 있어요.
그래서 종이로 할 때는 결과 칸을 접어서 가리고, 가로줄은 여러 사람이 번갈아 긋고, 출발 위치를 고른 뒤에 가로줄을 몇 개 더 추가하는 식으로 보완하곤 해요.
온라인 사다리는 어떻게 공정성을 지킬까?
복불복 놀이터의 사다리타기는 두 단계로 공정성을 지켜요.
- 가로줄을 무작위로 만들어요. 이웃한 세로줄 사이마다 여러 개의 가로줄을 브라우저의 암호학적 난수로 정한 높이에 배치해요. 같은 칸 안의 가로줄끼리, 또 이웃 칸의 가로줄과 너무 가깝게 붙지 않도록 간격 규칙도 지켜요. 그래서 갈 길이 애매한 지점이 생기지 않아요.
- 결과 칸을 섞어서 숨겨요. 시작 버튼을 누르는 순간 아래쪽 결과들의 순서를 피셔–예이츠 방식으로 무작위로 섞고 물음표로 가려요.
핵심은 두 번째 단계예요. 앞에서 본 것처럼 사다리 모양만으로는 완벽한 균등을 보장하기 어려워요. 하지만 사다리가 어떤 짝짓기를 만들든, 그 아래에 놓인 결과 순서가 모든 경우에 대해 같은 확률로 섞여 있다면 최종 결과도 모든 경우가 같은 확률이 돼요. 잘 섞인 카드 더미에서는 어떤 규칙으로 카드를 나눠 주든 각자가 받는 패의 확률이 똑같은 것과 같은 원리예요.
그래서 12명이 참가하면 479,001,600가지 짝짓기가 모두 정확히 같은 확률로 나올 수 있어요. 사다리가 모두 보이더라도 결과 칸이 가려져 있으니 길을 미리 따라가 봐도 소용이 없어요. 여기에 ‘사다리 숨기기’ 옵션을 켜면 지나간 길만 하나씩 드러나 보는 재미까지 더해져요. 난수가 어떻게 만들어지는지 더 궁금하다면 온라인 추첨기의 무작위는 믿을 수 있을까?를 읽어 보세요.
정리하면 — 사다리가 항상 1:1인 것은 가로줄이 ‘이웃끼리 자리 바꾸기’만 하기 때문이고, 사다리 모양만으로 완벽한 공정성을 얻기 어려운 것은 한 번에 한 칸씩만 움직일 수 있기 때문이에요. 결과 칸을 무작위로 섞어 두면 사다리 모양과 관계없이 모든 결과가 같은 확률이 돼요.
사다리 원리를 알면 더 재밌어지는 활용법
- 역할 배정에 딱이에요. 사다리는 1:1 짝짓기를 만드는 도구라서 ‘설거지, 장보기, 운전, 휴식’처럼 서로 다른 역할을 한 번에 나누는 데 가장 잘 어울려요.
- 순서 정하기에도 좋아요. 결과 칸에 1등부터 꼴등까지 적으면 순서가 한 번에 정해져요. 순서만 필요하다면 순서 정하기를 써도 편리해요.
- 한 명만 뽑을 때는 다른 도구가 빨라요. 당첨자 한 명만 필요하다면 돌림판나 제비뽑기가 더 간단해요.
마무리
사다리타기는 오래전부터 쓰여 온 소박한 놀이지만, 그 안에는 순열과 호환이라는 수학의 기본 개념이 고스란히 담겨 있어요. 가로줄 하나하나가 이웃끼리 자리를 바꾸는 작은 동작이고, 그 동작이 쌓여 누구와도 겹치지 않는 짝짓기를 만들어 내요. 다음에 사다리를 탈 때는 이름이 내려가는 길을 보며 ‘지금 두 사람이 자리를 바꾸는구나’ 하고 떠올려 보세요. 익숙한 놀이가 조금 다르게 보일 거예요.