사다리타기

사다리타기의 예.

'사다리타기' 또는 고스트 레그(Ghost Leg,유령다리, 일본 Amidakuji)는 제비뽑기의 일종으로 게임으로 사용되기도 한다. 사람 수만큼 세로줄을 긋고 한쪽 편에는 이름을 쓰고 반대건을 쓴 뒤, 세로줄 사이에 가로줄을 겹치지 않게 무작위로 그은 다음, 사람 이름에서부터 한쪽 방향으로 타고 가면서 교점을 만날 때마다 90도로 꺾는 것이다.

수학

n개의 세로줄로 된 사다리타기가 있다고 했을 때, 사다리타기의 가로줄 선분 하나는 두 인접한 원소 사이의 치환으로 볼 수 있으며 전체는 그 치환의 곱이므로 역시 n개의 원소에 대한 치환이다.

또한, 임의의 사다리타기의 끝에 하나의 가로줄을 무작위로 더하는 것은, 그 사다리타기에 해당하는 치환으로부터 다른 치환으로 전체 상태를 바꾸는 마르코프 체인에 해당한다.

게임

사다리타기 게임(game 또는 Ghost Leg)은 제비뽑기를 하는 사람 수만큼 세로줄을 긋고 그 사이사이에 가로줄을 그어 사다리 모양을 만든 다음, 위에서 아래로 세로선을 타고 내려가다가 가로선(교점)을 만나면 꺾어 내려가면서 최종적으로 도달하게 된 결과에 따라 차례 따위를 정하는 게임이다. 시작점과 결과값에서 일대일 대응하는 원리의 프레임워크에 기반한 이 게임은 컴퓨터게임등으로도 구현될수 있으며 중간 영역에 가로줄을 생성하는 것은 암호화작업이라고 볼 수 있다. 따라서 이 부분을 블랙마킹(Black Marking)등으로 가리는것을 제거하는 것과 같은 공개작업은 복호화 작업을 가능하게 한다.

참고 문헌

• (데이타제네틱스- Amidakuji)https://datagenetics.com/blog/may42014/index.html