본문으로 이동

사다리타기

위키백과, 우리 모두의 백과사전.

사다리타기의 예

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

수학

[편집]

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

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

게임

[편집]

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

각주

[편집]
  1. 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.

외부 링크

[편집]
  • https://web.archive.org/web/20091023070628/http://geocities.com/Athens/Acropolis/7247/amidakuji.html
  • Ladders: A Research Paper by David Senft (PDF)
  • Man-Kit Ho, Hoi-Kwan Lau, Ting-Fai Man, Shek Yeung (2012). "Ghost Leg", Hang Lung Mathematics Awards Collection of Winning Papers, 2004. International Press. ISBN 978-1-57146-254-1.