반추이적 주사위(nontransitive dice)

      Comments Off on 반추이적 주사위(nontransitive dice)

$1$부터 $6$까지의 숫자가 각 면에 적혀있는 일반적인 정육면체 모양 주사위 두 개 $A$와 $B$가 주어졌다고 하자. 이제 주사위 $A$가 주사위 $B$를 이길 확률, 질 확률, 비길 확률 (즉, 주사위 $A$와 $B$를 던졌을 때, $A$의 눈이 $B$의 눈보다 클 확률, 작을 확률, 같을 확률)을 각각 $P(A > B)$, $P(A < B)$, $P(A = B)$로 정의하면 간단한 계산을 통해

\[ P(A > B) = P(A < B) = \frac{15}{36}, \quad P(A = B) = \frac{6}{36} \]

임을 알 수 있다. 즉, 두 주사위 $A$와 $B$에 대하여, 한 주사위가 다른 주사위를 이길 확률은 각각 $\frac{15}{36}$으로 동일하다. 이와 같이 두 주사위 $A$와 $B$에 대하여 $P(A > B) = P(A < B)$가 성립하는 경우 기호로 $A \simeq B$로 나타내기로 하자.

$ $

이번에는 모든 면에 $6$이 적혀 있는 정육면체 모양 주사위 $A$와 모든 면에 $1$이 적혀 있는 정육면체 모양 주사위 $B$를 생각해 보자. 그러면 주사위 $A$가 항상 주사위 $B$를 이기게 된다. (즉, $P(A > B) = 1 > 0 = P(A < B)$가 성립한다.) 이와 같이 두 주사위 $A$와 $B$에 대하여 $P(A > B) > P(A < B)$가 성립하는 경우 기호로 $A \succeq B$로 나타내기로 하자.

$ $

반추이적 주사위(nontransitive dice)

각 면에 양의 정수가 적혀 있는 $n \geq 3$개의 정육면체 모양 주사위의 집합 $\{A_1,\, A_2,\, \ldots,\, A_n\}$이 주어졌다고 하자. 각각의 주사위에 대하여 다음과 같은 관계

\[ A_1 \succeq A_2 \succeq A_3 \succeq \cdots \succeq A_n \succeq A_1 \]

이 성립할 때, 주사위의 집합 $\{A_1,\, A_2,\, \ldots,\, A_n\}$은 반추이적(nontransitive)이라 한다. "가위-바위-보 게임"은 반추이적 성질을 가지는 가장 간단하면서 유명한 게임이다.

$ $

$n=3$인 경우, 다음과 같은 예가 있다.

\[ \left\{ \begin{aligned} A_1 &= \{2,\, 2,\, 4,\, 4,\, 9,\, 9\} \\[5px] A_2 &= \{1,\, 1,\, 6,\, 6,\, 8,\, 8\} \\[5px] A_3 &= \{3,\, 3,\, 5,\, 5,\, 7,\, 7\} \end{aligned} \right. , \qquad \left\{ \begin{aligned} B_1 &= \{2,\, 2,\, 6,\, 6,\, 7,\, 7\} \\[5px] B_2 &= \{1,\, 1,\, 5,\, 5,\, 9,\, 9\} \\[5px] B_3 &= \{3,\, 3,\, 4,\, 4,\, 8,\, 8\} \end{aligned} \right. \]

각각의 경우에 대하여 경우의 수를 생각해 보면

\[ \begin{align*} & P(A_1 > A_2) = P(A_2 > A_3) = P(A_3 > A_1) = \frac{5}{9}, \\[5px] & P(B_1 > B_2) = P(B_2 > B_3) = P(B_3 > B_1) = \frac{5}{9} \end{align*} \]

가 되어 $A_1 \succeq A_2 \succeq A_3 \succeq A_1$, $B_1 \succeq B_2 \succeq B_3 \succeq B_1$이 성립한다. 즉 두 주사위 집합 모두 반추이적임을 알 수 있다.

$ $

하지만 두 주사위 집합 $\{A_1,\, A_2,\, A_3\}$, $\{B_1,\, B_2,\, B_3\}$은 다음과 같은 흥미로운 차이점을 갖는다. 이를 알아보기 위하여, 각 집합의 세 주사위가 동시에 던지는 경우를 생각해 보자. 먼저 주사위 집합 $\{A_1,\, A_2,\, A_3\}$의 세 주사위를 동시에 던질 때, 각 주사위가 다른 두 주사위를 동시에 이길 확률을 계산하면 각각

\[ \begin{align*} P(A_1 > A_2 \cap A_1 > A_3) &= \frac{10}{27}, \\[5px] P(A_2 > A_1 \cap A_2 > A_3) &= \frac{6}{27}, \\[5px] P(A_3 > A_1 \cap A_3 > A_2) &= \frac{10}{27} \end{align*} \]

가 되어 $A_2$가 게임에서 가장 불리함을 알 수 있다. 반면 주사위 집합 $\{B_1,\, B_2,\, B_3\}$에 대하여도 같은 계산을 해 보면

\[ \begin{align*} P(B_1 > B_2 \cap B_1 > B_3) &= \frac{8}{27}, \\[5px] P(B_2 > B_1 \cap B_2 > B_3) &= \frac{11}{27}, \\[5px] P(B_3 > B_1 \cap B_3 > B_2) &= \frac{8}{27} \end{align*} \]

이 되어 이번에는 반대로 $B_2$가 가장 유리한 주사위가 된다. 따라서 두 주사위 집합은 모두 반추이적이기는 하지만 서로 동형은 아님을 알 수 있다.

$ $

마이윈 주사위(Miwin dice)

1975년 물리학자 마이클 윈켈만(Michael Winkelmann)은 다음과 같은 형태의 반추이적 주사위를 제안하였다.

\[ \left\{ \begin{aligned} M_1 &= \{1,\, 2,\, \phantom{3,\;} \phantom{4,\;} 5,\, 6,\, 7,\, \phantom{8,\;} 9\} \\[5px] M_2 &= \{1,\, \phantom{2,\;} 3,\, 4,\, 5,\, \phantom{6,\;} \phantom{7,\;} 8,\, 9\} \\[5px] M_3 &= \{\phantom{1,\;} 2,\, 3,\, 4,\, \phantom{5,\;} 6,\, 7,\, 8 \phantom{9,\;}\} \end{aligned} \right. , \qquad \left\{ \begin{aligned} N_1 &= \{1,\, \phantom{2,\;} 3,\, \phantom{4,\;} 5,\, 6,\, 7,\, 8 \phantom{9,\;}\} \\[5px] N_2 &= \{1,\, 2,\, \phantom{3,\;} 4,\, \phantom{5,\;} 6,\, \phantom{7,\;} 8,\, 9\} \\[5px] N_3 &= \{\phantom{1,\;} 2,\, 3,\, 4,\, 5,\, \phantom{6,\;} 7,\, \phantom{8,\;} 9\} \end{aligned} \right. \]

위 주사위 역시 한 주사위가 다른 주사위를 이길 확률을 각각 계산해 보면

\[ \begin{align*} & P(M_1 > M_2) = P(M_2 > M_3) = P(M_3 > M_1) = \frac{17}{36}, \\[5px] & P(N_1 > N_2) = P(N_2 > N_3) = P(N_3 > N_1) = \frac{17}{36} \end{align*} \]

이 되어 반추이적 성질 $M_1 \succeq M_2 \succeq M_3 \succeq M_1$, $N_1 \succeq N_2 \succeq N_3 \succeq N_1$을 가짐을 확인해 볼 수 있다. 이 주사위를 마이윈 주사위(Miwin dice)라 부른다.(1)

$ $

마이윈 주사위 집합 $\{M_1,\, M_2,\, M_3\}$ 또는 $\{N_1,\, N_2,\, N_3\}$에 적힌 주사위들의 눈을 살펴보면 $1$부터 $9$ 까지의 숫자가 정확히 두 번씩 사용되었음을 알 수 있다. 이 사실을 이용하여 $0 \sim 80$의 숫자 중 하나를 뽑는 시행이 균등분포(uniform distribution)을 갖도록 설계할 수 있다. 다음과 같은 시행을 살펴보자.

  1. 첫번째 마이윈 주사위 집합 $\{M_1,\, M_2,\, M_3\}$에서 하나의 주사위를 무작위로 선택하여 던진다. 이 때 나온 주사위의 눈을 $a$라 하자.
  2. 두번째 마이윈 주사위 집합 $\{N_1,\, N_2,\, N_3\}$에서 하나의 주사위를 무작위로 선택하여 던진다. 이 때 나온 주사위의 눈을 $b$라 하자.
  3. $N := 9a - b$의 값을 계산한다. 이 때, $N$은 $0$부터 $80$ 사이의 정수 값을 갖는다.

위 시행에서 계산한 $N$의 값의 분포는 균등분포를 갖는다. 실제로 임의의 정수 $0 \leq k \leq 80$에 대하여, $P(N = k) = \frac{1}{81}$임을 간단히 확인할 수 있다.

$ $

오스카의 주사위(Oscar dice)

독일의 퍼즐 제작자 오스카 반 데벤터(Oskar van Deventer)(2)는 다음과 같이 7개의 반추이적 주사위를 제안하였다.

\[ \left\{ \begin{aligned} O_1 &= \{2,\, 2,\, 14,\, 14,\, 17,\, 17\} \\[5px] O_2 &= \{7,\, 7,\, 10,\, 10,\, 16,\, 16\} \\[5px] O_3 &= \{5,\, 5,\, 13,\, 13,\, 15,\, 15\} \\[5px] O_4 &= \{3,\, 3,\, 9,\, 9,\, 21,\, 21\} \\[5px] O_5 &= \{1,\, 1,\, 12,\, 12,\, 20,\, 20\} \\[5px] O_6 &= \{6,\, 6,\, 8,\, 8,\, 19,\, 19\} \\[5px] O_7 &= \{4,\, 4,\, 11,\, 11,\, 18,\, 18\} \end{aligned} \right. \]

실제로 확률 계산을 통해 $O_1$은 $\{O_2,\, O_3,\, O_5\}$를 이기고, $O_2$는 $\{O_3,\, O_4,\, O_6\}$를 이기고, $O_3$는 $\{O_4,\, O_5,\, O_7\}$을 이기고, $O_4$는 $\{O_5,\, O_6,\, O_1\}$을 이기고, $O_5$는 $\{O_6,\, O_7,\, O_2\}$를 이기고, $O_6$는 $\{O_7,\, O_1,\, O_3\}$를 이기고, 마지막으로 $O_7$은 $\{O_1,\, O_2,\, O_4\}$를 이김을 확인할 수 있다. 이를 방향그래프(digraph)로 나타내면 다음과 같다. 여기서 $A \to B$는 $A$가 $B$를 이김을 뜻한다.

또한 오스카 주사위 집합 $\{O_1,\, \ldots,\, O_7\}$에서 임의로 두개의 주사위를 고르면, 이 주사위들을 모두 이기는 오스카 주사위가 유일하게 존재한다. 예를 들어 $\{O_3,\, O_7\}$은 모두 이기는 주사위는 $O_6$임을 알 수 있다.

$ $

  1. 이 주사위를 제안한 마이클 윈켈만(Michael Winkelmann)의 이름과 성의 앞자를 따서 마이윈(Miwin)이라는 이름을 붙혔을 것으로 추측된다.
  2. 유튜브 채널: https://www.youtube.com/user/OskarPuzzle