사다리 타기 게임

공정한 사다리 타기 게임의 원리

본 게임은 역설계를 통해 공정성을 구현합니다.

치환 (Permutation)

자연수 \( n \)에 대하여 집합 \( \{1, 2, \dots, n\} \)에서 자기 자신으로 가는 전단사 사상을 \( n \)-치환이라고 하며, 다음과 같이 나타냅니다.

\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & \dots & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \dots & \sigma(n) \end{pmatrix} \]

호환 (Transposition)

인접한 두 원소 \( i, i+1 \)만 서로 바꾸고, 나머지 원소는 고정하는 것을 인접 호환(adjacent transposition)이라고 하며, 기호로 \( s_i = (i \quad i+1) \)과 같이 나타냅니다. 호환을 두 번 실행하면 항등치환(\(e\))이 됩니다.

\[ s_i^2 = s_i \circ s_i = e \]

치환의 분해

모든 치환은 호환들의 곱으로 나타낼 수 있습니다. 이 정리는 치환되는 원소의 개수 \( n \)에 대한 수학적 귀납법을 통해 증명할 수 있습니다.

\[ \sigma = s_{i_1} \circ s_{i_2} \circ \dots \circ s_{i_k} \]

이 정리는 아무리 복잡한 치환이라도 인접한 원소들끼리의 위치 바꿈을 반복하여 만들어낼 수 있음을 의미합니다.

사다리 타기와 치환의 연결

사다리 타기는 치환과 완벽하게 대응합니다.

세로줄과 치환: \(n\)개의 세로줄은 집합 \(\{1, 2, \dots, n\}\)을 나타내며, 사다리 타기의 결과는 이 집합의 치환 \(\sigma\)가 됩니다.
가로줄과 호환: 인접한 두 세로줄을 잇는 가로줄 하나는 인접한 두 원소만 바꾸는 호환(\(s_i = (i \quad i+1)\))을 의미합니다.
사다리 경로: 전체 사다리 경로는 목표 치환을 여러 개의 호환들의 곱으로 분해하여 시각화한 것입니다.

이 게임은 "모든 치환은 인접 호환들의 곱으로 나타낼 수 있다"라는 정리를 이용합니다. 따라서 어떤 복잡한 결과라도 적절한 위치에 가로줄을 배치하면 반드시 사다리로 구현할 수 있습니다.

역설계

본 게임은 목표를 먼저 정하고 과정을 생성하는 역설계 방식을 사용합니다. 이는 크게 세 단계로 나뉩니다.

목표 치환 생성: 집합에 대하여 무작위 치환 \(\sigma\)를 먼저 결정합니다.
호환의 곱으로 분해: 결정된 치환을 만들기 위한 호환의 곱을 계산합니다.
항등원 삽입: 결과에 영향을 주지 않는 항등원 쌍을 중간에 삽입하여 표면적 복잡도를 높입니다.

컴퓨터 공학적 관점: 정렬을 거꾸로 되감기

버블 정렬(bubble sort)의 시간 복잡도는 \(O(n^2)\)입니다. 이는 정렬되지 않은 데이터를 완벽하게 정렬하는 데 최대 \(O(n^2)\)번의 위치 바꿈이 필요하다는 뜻입니다. 정렬하는 데 \(O(n^2)\)번이 필요하다면, 사다리의 가로줄을 이용해서 완벽하게 섞는 데도 \(O(n^2)\)개의 가로줄이 필요합니다. 본 게임은 이 원리를 역으로 이용합니다.

목표 결정: Fisher-Yates shuffle 알고리즘을 통해 편향되지 않은 무작위 결과를 먼저 뽑습니다.
역정렬: 정렬된 상태에서 시작하여, 정해진 목표 결과가 나올 때까지 가로줄을 배치합니다. 이때 정렬 알고리즘의 단계를 거꾸로 추적하여 필수적인 가로줄 리스트를 만듭니다.
복잡도 보완: 최소한의 줄만으로는 경로가 눈에 보일 수 있으므로, 결과에 영향을 주지 않는 '가로줄 쌍'을 추가하여 시각적인 즐거움을 더합니다.

이러한 구현 방식은 모든 결과의 확률적 균등성을 보장함과 동시에, 사다리 타기 특유의 직관적으로 예측 불가능한 재미를 동시에 제공합니다.