사다리타기
'사다리타기' 또는 고스트 레그(Ghost Leg,유령다리, 일본 Amidakuji)는 제비뽑기의 일종으로 게임으로 사용되기도 한다. 사람 수만큼 세로줄을 긋고 한쪽 편에는 이름을 쓰고 반대건을 쓴 뒤, 세로줄 사이에 가로줄을 겹치지 않게 무작위로 그은 다음, 사람 이름에서부터 한쪽 방향으로 타고 가면서 교점을 만날 때마다 90도로 꺾는 것이다.
수학 편집
n개의 세로줄로 된 사다리타기가 있다고 했을 때, 사다리타기의 가로줄 선분 하나는 두 인접한 원소 사이의 치환으로 볼 수 있으며 전체는 그 치환의 곱이므로 역시 n개의 원소에 대한 치환이다.
또한, 임의의 사다리타기의 끝에 하나의 가로줄을 무작위로 더하는 것은, 그 사다리타기에 해당하는 치환으로부터 다른 치환으로 전체 상태를 바꾸는 마르코프 체인에 해당한다.[1]
게임 편집
사다리타기 게임(game 또는 Ghost Leg)은 제비뽑기를 하는 사람 수만큼 세로줄을 긋고 그 사이사이에 가로줄을 그어 사다리 모양을 만든 다음, 위에서 아래로 세로선을 타고 내려가다가 가로선(교점)을 만나면 꺾어 내려가면서 최종적으로 도달하게 된 결과에 따라 차례 따위를 정하는 게임이다. 시작점과 결과값에서 일대일 대응하는 원리의 프레임워크에 기반한 이 게임은 컴퓨터게임등으로도 구현될수 있으며 중간 영역에 가로줄을 생성하는 것은 암호화작업이라고 볼 수 있다. 따라서 이 부분을 블랙마킹(Black Marking)등으로 가리는것을 제거하는 것과 같은 공개작업은 복호화 작업을 가능하게 한다.
참고 문헌 편집
- ↑ Les Lange and James W. Miller, "A Random Ladder Game: Permutations, Eigenvalues, and Convergence of Markov Chains", The College Mathematics Journal, Vol. 23, No. 5, (1992), pp. 373-385.
- (데이타제네틱스- Amidakuji)https://datagenetics.com/blog/may42014/index.html