루빅스 큐브와 수학

소개

루빅스 큐브(영어: Rubik's Cube)는 세계적으로 가장 널리 알려진 퍼즐이 아닐까 싶다. 80년대를 살았다면 누구나 어릴 때 한 번을 해보았을 것 같은데 요즘도 옛날만큼은 아니지만 많은 아이들이 재미있게 즐기고 있다. 간단한 역사를 찾아보면 아래와 같다.

작은 정육면체를 모아 만든 하나의 큰 정육면체이다. 각 면에 서로 다른 색을 칠하고 각 방향으로 돌려서 흩어진 각 면의 색깔을 같은 색깔로 맞추는 것이다. 1974년 헝가리의 루비크 에르뇌(Ernő Rubik)가 큐브를 발명했다. 그는 부다페스트에 있는 응용 예술 및 공예 아카데미의 인테리어 디자인 부서에서 일했다. 학생들이 3D 물체를 이해하는 데 도움을 주기 위해 큐브를 만들었다고 널리 알려져 있지만, 실제 목표는 전체 메커니즘이 무너지지 않고 부품을 독립적으로 움직이는 구조적 문제를 해결하는 것이었다. 그는 처음으로 새 큐브를 뒤섞은 다음 복원하려고 시도할 때까지 자신이 퍼즐을 만들었다는 사실을 깨닫지 못했다. 루비크 에르뇌는 1975년 1월 30일에 "마술 큐브: Magic Cube"( 헝가리어 : Bűvös kocka )에 대해 헝가리에서 특허를 신청했고 그해 말에 승인되었다. 마술 큐브의 첫 번째 테스트 배치는 1977년 말에 생산되어 부다페스트 장난감 상점에서 출시되었다.

루비크의 허락을 받아 사업가 티볼 라찌(Tibor Laczi)는 큐브를 대중화하기 위해 1979년 2월 독일 뉘른베르크 장난감 박람회에 가져갔습니다. 스티븐 타운(Seven Towns) 설립자 톰 크레머(Tom Kremer)가 이를 알아채고 1979년 9월에 Ideal Toys와 계약을 체결하여 '매직 큐브'를 전 세계에 출시했다. 'Ideal'은 적어도 상표명으로 인식할 수 있는 이름을 원했다. 그 배열은 1980년에 매직 큐브가 발명자의 이름을 따서 이름이 바뀌었기 때문에 루빅을 주목하게 했다.

이 퍼즐은 1980년 1월과 2월에 런던, 파리, 뉘른베르크, 뉴욕의 장난감 박람회에서 국제 데뷔를 했다. 국제적으로 데뷔한 후 서구의 장난감 가게 진열대를 향한 Cube의 발전은 서구의 안전 및 포장 사양에 따라 제조될 수 있도록 잠시 중단되었다. 더 가벼운 큐브가 생산되었고, 아이디얼은 이름을 바꾸기로 했다. " The Gordian Knot "과 "Inca Gold"가 고려되었지만 회사는 마침내 "Rubik 's Cube"로 결정했고 1980년 5월 헝가리에서 첫 번째 배치를 수출했다. https://en.wikipedia.org/wiki/Rubik%27s_Cube

루빅스 큐브와 관련된 수학을 정리해 두려고 한다. 

표기법

먼저 큐브의 면은 아래와 같이 부른다.

그림 1

조각은 아래와 같이 부르기로 하자. 가운데 있는 면 조각은 문자 하나, 모서리 조각은 문자 둘, 꼭짓점 조각은 문자 셋이 필요하다.

경우의 수

꼭짓점 조각 8개는 각각 3가지 위치를 가질 수 있으므로 경우의 수는 $8!\times 3^8$, 모서리 조각 12개는 각각 2가지 위치를 가질 수 있으므로 경우의 수는 $12!\times 2^{12}$이다. 따라서 전체 경우의 수는 아래와 같다.

$$8!\times3^8\times 12!\times2^{12}=519,024,039,293,878,272,000$$

하지만 이것은 회전해서 맞출 수 없을 때도 모두 포함한 것이다. 오로지 회전만을 이용하여 모든 면을 같은 색으로 맞출 수 있을 때는 $1/12$에 불과하다. 왜 그런가를 대수학에 있는 군의 정리로 설명할 수 있다.

$$\frac{8!\times3^8\times 12!\times2^{12}}{2\times 2\times 3}=43,252,003,272,489,856,000$$

여전히 엄청나게 큰 수다. 서로 다른 배열을 가진 큐브로 지구를 덮을 수 있다고 한다.

군 Group

군(群: Group)은 대수학(Algebra)을 배울 때 가장 먼저 만나는 구조이다.

정의

집합 $\mathcal{G}$와 이항연산 $*$이 아래를 만족하면 군이라고 한다. 

• 집합 $\mathcal{G}$가 연산 $*$에 대하여 닫혀있다. $$\forall h,g\in \mathcal{G}\Rightarrow h*g\in\mathcal{G}$$
• 연산 $*$는 결합법칙이 성립한다. $$\forall f, g, h\in \mathcal{G}\Rightarrow (f*g)*h=f*(g*h)$$
• 모든 원소에 대하여 연산 $*$에 대한 항등원을 가진다. $$\forall g \in \mathcal{G}\text{에 대하여 }e*g=g*e=g \text{를 만족하는 } \exists e\in\mathcal{G}$$
• 모든 원소는 연산 $*$에 대한 역원을 가진다. $$\forall g \in \mathcal{G}\text{에 대하여 }g*g^{-1}=g^{-1}*g=e \text{를 만족하는 } \exists g^{-1}\in\mathcal{G}$$

정리

간단한 몇 가지 정리는 아래와 같다.

• 연산에 $*$에 대한 항등원 $e$는 유일하다.
• $a*b=e\quad \Rightarrow \quad a=b^{-1}$
• $a*x=b*x\quad\Rightarrow\quad a=b$
• $ab$의 역원은 $b^{-1}a^{-1}$이다.
• $(a^{-1})^{-1}=a$

조심해야 할 것은 흔하게 알고 있는 교환법칙 $a*b=b*a$은 일반적으로 군에서 성립하지 않는다. 교환법칙이 성립하는 군은 아벨리안군(Abelian group)이라고 한다.

이제 루빅스 큐브를 맞추는 일을 수학적 구조로 파악해 보자. 퍼즐을 나타내는 원소를 나타내기 위해 여섯 면의 색이 모두 정렬된 상태에서 전혀 움직이지 않은 것을 $1$으로 하자. 연산 $*$은 큐브의 어느 한 면을 시계방향으로 $90^{\circ}$만큼 회전하는 것으로 하자. 시계방향으로 회전한 것은 그림 1을 참고하여 각각 $F,R,L,B,U,D$로 쓰고 시계 반대방향으로 회전한 것은 소문자로 나타내기로 하자. 자연스럽게 전혀 움직이지 않은 것이 항등원이므로 아래와 같이 대문자와 소문자는 서로 역원이다. 연산 $*$을 나타내는 기호는 곱셈처럼 따로 쓰지 않기로 하자.

$$Ff=fF=1,Rr=rR=1,\cdots,Dd=dD=1$$

이제 큐브가 섞인 상태를 집합의 원소로 나타낼 수 있게 되었다. 여기서 소문자로 표현하는 것은 루빅스 큐브의 해법을 나타내는 표기법과 쓰임이 다르다는 점에 유의하자. 

$$\mathcal {R}=\{1, F, R, L, U, D, B, \cdots, Fu, FUDR,\cdots \}$$

이 집합은 군을 이루고 있음을 쉽게 확인할 수 있다. $FR\not=RF$이므로 아벨군은 아니다.

$1$                                                                    FR                                                                                   RF

이제 퍼즐이 놓인 상태를 나타내는 원소를 찾으면 해법을 찾은 것이다.

$ABC$의 역원은 정리에 따라 $cba$가 된다. 

큐브 퍼즐이 이루는 군을 쉽게 이해하기 위해서 대칭군(symmetric group)을 공부할 필요가 있다.

큐브의 서로 다른 움직임은 순열이나 재배열로 보일 수 있다. 따라서 루빅스 큐브의 수학은 같은 큐빅의 배열은 순열로 이루어진 군의 원소로 나타낼 수 있다. 따라서 모든 움직임은 순열이다. 예를 들면 FFRR은 순열 (DF UF)(DR UR)(BR FR FL)(DBR UFR DFL)(ULF URB DRF)과 같다.

대칭군

순열을 쉽게 숫자로 나타내는 방법이 정리하자. 군론에서는 순열(permutation)을 치환으로 옮긴다. 

정의

집합 $X$에서 $X$ 자신 위로의 일대일 대응 $\sigma : X\rightarrow X$를 $X$ 위의 치환(permutation)이라고 한다. 또 집합 $X$ 위의 치환 전체의 집합을 $S(X)$로 적는다. 집합 $S(X)$는 두 치환의 합성사상 $\circ$에 대하여 군을 이룬다. 군 $(S(X),\circ)$를 $X$ 위의 대칭군(symmetric group)이라고 한다.

집합 $X=\{x_1 ,x_2, \cdots,x_n \}$일 때, 치환 $\sigma : X\rightarrow X$를 $$\sigma=\pmatrix{x_1&x_2&\cdots &x_n\\\sigma(x_1)&\sigma(x_2)&\cdots&\sigma(x_n)}$$으로 나타내면 편리하다. 특히 집합 $X_n =\{1,2,\cdots,n\}$ 위의 치환  $\sigma : X_n \rightarrow X_n$를 $$\sigma=\pmatrix{1&2&\cdots &n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)}$$으로 나타낼 때 2행은 $1,2,\cdots,n$의 순열이다. $$\sigma^{-1}=\pmatrix{\sigma(1)&\sigma(2)&\cdots&\sigma(n)\\1&2&\cdots &n}$$이다.

집합 $X_n =\{1,2,\cdots,n\}$ 위의 치환 전체의 집합 $S(X_n)$을 $S_n$으로 나타내고, 대칭군 $(S_n , \circ)$를 $n$차 대칭군이라고 한다.

$$|S_n|=n!$$

치환을 표현하는 방법은 여러 가지가 있는데 여기선 순환치환의 곱으로 나타내는 방법이 간편하다. 

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{pmatrix}=\begin{pmatrix}1 & 2 & 5 \end{pmatrix}\begin{pmatrix}3 & 4 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}1 & 2 & 5 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}5 & 1 & 2 \end{pmatrix}$$

캐노니컬 순환 표현(canonical cycle notation)은 (1)(234)과 같이 적는다. 이것은 1은 그대로 1이고 2, 3, 4는 차례로 순환함을 뜻한다. 2는 3으로 3은 4로 4는 2로 간다. (234) → (423).

치환의 조합은 아래와 같이 적는다.

1. 가장 작은 숫자를 찾아 치환을 시작한다. 이 예제는 1부터 시작한다.
2. 치환을 통해 객체의 움직임을 따라 첫 번째 주기를 마친다. 순환을 끝낼 때까지 작업을 수행한다. 예를 들어, (1 2 4)(3 5) * (6 1 2)(3 4)은 1부터 시작한다. 1은 첫 번째 치환에서 2로 이동하고 2는 두 번째 치환에서 6으로 이동하므로 1은 6으로 이동한다. 다음 6은 다시 1로 이동하므로 6과 1이 하나의 순환치환을 만든다.
3. 숫자를 모두 사용했다면 끝이다. 그렇지 않다면 1단계로 돌아가 사용하지 않은 가장 작은 숫자로 새 주기를 시작한다. 이러한 방식으로 계속하면 (1 6)(2 3 5 4)가 된다.

치환 $P$가 다양한 길이의 여러 순환치환으로 구성되었을 때 $P$를 $n$번 적용하면 시작 상태가 되면 해당 치환의 차수는 $n$이다. 치환 $P$가 다양한 길이의 여러 순환치환으로 구성되으면 순환 단계의 수가 두 체인을 시작 상태로 되돌리기 때문에 차수는 순환치환 길이의 최소 공배수이다.

다음은 몇 가지 예이다.

• (1 2 3)(2 3 1) = (1 3 2) 차수 3
• (2 3)(4 5 6)(3 4 5) = (2 4 3)(5 6) 차수 6
• (1 2) 차수 2

보기 대칭군 $S_3=\{1,\;\;(1\;2\;3),\;\;(1\;3\;2),\;\;(1\;2),\;\;(1\;3),\;\;(2\;3)\}$

 $S_3$의 곱셈표

$\circ$	$1$	$(12)$ $\tau$	$(23)$ $\tau\circ\sigma$	$(123)$  $\sigma$	$(132)$  $\sigma^2$	$(13)$ $\sigma\circ\tau$
$1$	$1$	$(12)$	$(23)$	$(123)$	$(132)$	$(13)$
$(12)$ $\tau$	$(12)$	$1$	$(123)$	$(23)$	$(13)$	$(132)$
$(23)$ $\tau\circ\sigma$	$(23)$	$(132)$	$1$	$(13)$	$(12)$	$(123)$
$(123)$ $\sigma$	$(123)$	$(13)$	$(12)$	$(132)$	$1$	$(23)$
$(132)$ $\sigma^2$	$(132)$	$(23)$	$(13)$	$1$	$(123)$	$(12)$
$(13)$ $\sigma\circ\tau$	$(13)$	$(123)$	$(132)$	$(12)$	$(23)$	$1$

$(1\;2\;3)^2 =(1\;3\;2)=(1\;2\;3)^{-1},(1\;3\;2)^2 =(1\;2\;3)=(1\;3\;2)^{-1}$

$(1\;2)^{-1}=(1\;2)\quad(1\;3)^{-1}=(1\;3)\quad (2\;3)^{-1}=(2\;3)$

$\sigma=(1\;2\;3), \quad \tau=(1\;2)$에 대하여

$\sigma \circ \tau=(1\;2\;3) \circ (1\;2)=(1\;3),\quad\tau\circ\sigma=(1\;2) \circ (1\;2\;3)=(2\;3)$이므로

$\sigma \circ \tau \not=\tau\circ\sigma$이다. 따라서 아벨군이 아니다.

치환의 표준분해

대칭군 $S_n$에서 두 순환치환 $\displaystyle{\sigma=\pmatrix{i_1&i_2&\cdots&i_r},\;\;\tau=\pmatrix{j_1&j_2&\cdots&j_s}}$에 공통문자가 없는 경우에 $\sigma \circ \tau =\tau\circ\sigma$이다.

치환 $$\sigma=\pmatrix{1&2&3&4&5&6\\4&6&2&1&5&3}\in S_6$$에 대하여

$$1\rightarrow4\rightarrow1;\quad 2\rightarrow 6\rightarrow 3 \rightarrow 2;\quad5\rightarrow5$$

이므로, $\sigma$에 의해 세 부분집합 $\{1,4\},\{2,6,3\},\{5\}$로 분할되고 또 $\sigma$는 각 부분집합에 순환치환 $(1\;4),\;\;(2\;6\;3),\;\;(5)$를 유도한다. 이런 의미에서 $\sigma$를

$$(1\;4)\circ(2\;6\;3),\quad (1\;4)\circ(2\;6\;3)\circ(5),\quad (5)\circ(1\;4)\circ(2\;6\;3)$$

과 같이 나타낸다.

일반적으로, $n\geq2$일 때 임의의 치환 $\sigma \in S_n$는 다음과 같이 공통문자가 들어 있지 않은 순환치환의 곱으로 나타내어진다.

$$\sigma=\pmatrix{i_1&i_2&\cdots&i_r}\circ\pmatrix{j_1&j_2&\cdots&j_s}\circ\cdots\circ\pmatrix{l_1&l_2&\cdots&l_t}$$

$$1\leq r \leq s \leq\cdots \leq t,\quad r+s+\cdots+t=n$$

이러한 분해를 치환 $\sigma$의 표준분해(standard decomposition)라 하고, $\sigma$를 $\{r,s,\cdots,t\}$형 치환이라고 한다. 

홀짝성(parity)

 $n\geq2$일 때, 대칭군 $S_n$에 대하여 다음이 성립한다.

1) $\forall \sigma \in S_n$는 유한 개 순환치환의 곱으로 나타내어진다.

2) $r$항 순환치환  $\pmatrix{i_1&i_2&\cdots&i_r}$는 $r-1$개 호환의 곱으로 나타내어진다.

$$\pmatrix{i_1&i_2&\cdots&i_r}=\pmatrix{i_1&i_r}\circ\cdots\circ\pmatrix{i_1&i_3}\circ\pmatrix{i_1&i_2}$$

3) $\forall \sigma \in S_n$는 유한 개 호환의 곱으로 나타내어진다.
호환: 길이가 2인 순환치환

치환 $\sigma\in S_n$의 표준분해가

$$\sigma=\pmatrix{i_1&i_2&\cdots&i_r}\circ\pmatrix{j_1&j_2&\cdots&j_s}\circ\cdots\circ\pmatrix{l_1&l_2&\cdots&l_t}$$

일 때

$$N(\sigma)=(r-1)+(s-1)+\cdots+(t-1)$$

이라고 하면, $N(\sigma)$는 $\sigma$에 의해 결정되는 정수이고 $\sigma$는 $N(\sigma)$개 호환의 곱으로 나타내어진다. 일반적으로 $\sigma$를 표준분해하는 방법은 여러 가지가 있으나, 이때 나타나는 호환의 개수가 짝수인지 홀수인지는 항상 일정하다.

$$(a\;\;b)\circ \pmatrix{a&c_1&\cdots&c_n&b&d_1&\cdots&d_n}=\pmatrix{a&c_1&\cdots&c_n}\circ\pmatrix{b&d_1&\cdots&d_n}$$

$$(a\;\;b)\circ\pmatrix{a&c_1&\cdots&c_n}\circ\pmatrix{b&d_1&\cdots&d_n}=\pmatrix{a&c_1&\cdots&c_n&b&d_1&\cdots&d_n}$$

따라서, $\sigma$의 표준분해에서 $a,b$가 동일한 순환치환 안에 들어 있으면 $N((a\;\;b)\circ\sigma)=N(\sigma)-1$이고 $a,b$가 서로 다른 순환치환 안에 들어 있으면 $N((a\;\;b)\circ\sigma)=N(\sigma)+1$이다. 즉, $N((a\;\;b)\circ\sigma)=N(\sigma)\pm1$이다. 이제 치환 $\sigma$가 $\sigma=(a_1\;\;b_1)\circ(a_2\;\;b_2)\circ\cdots\circ(a_m\;\;b_m)$과 같이 $m$개의 호환의 곱으로 분해되어 있다고 하자. 이때, $(a_i\;\;b_i)^2 =1$이므로

$$(a_1\;\;b_1)\circ(a_2\;\;b_2)\circ\cdots\circ(a_m\;\;b_m)\circ\sigma=1$$

이므로 위의 결과에 의하여

$$N(\sigma)\pm1 \pm 1\cdots \pm 1=N(1)=0\quad\quad(\pm 1은 \;\;m개)$$

이 등식에 있는 $m$개의 $\pm1$ 중에서 $+1$이 $m_1$개, $-1$이 $m_2$개 있으면 $N(\sigma)=m_1 -m_2,\;\;m=m_1 +m_2$이므로 $N(\sigma)=m-2m_2$이다. 따라서, $N(\sigma)$가 짝수이면 $m$도 짝수이고 $N(\sigma)$가 홀수이면 $m$도 홀수이다. 그러므로, $\sigma$를 호환의 곱으로 분해할 때 나타나는 호환의 개수 $m$이 짝수인지 홀수인지는 분해하는 방법에 관계없이 일정하다.

치환 $\sigma\in S_n$가 짝수개의 호환의 곱으로 나타내어질 때 $\sigma$를 짝수-치환(even permutation), 홀수개의 호환의 곱으로 나타내어질 때는 홀수-치환(odd permutation)이라고 한다.

정리 

$n\geq2$일 때, 대칭군 $(S_n,\circ)$에서 짝수-치환 전체의 집합을 $A_n$으로 나타내면, 집합 $A_n$은 합성 연산 $\circ$에 관하여 군을 이루고 또한 $\displaystyle{|A_n|=\frac{|S_n|}{2}=\frac{n!}{2}}$이다.

$S_3=\{1,\;\;(1\;2\;3),\;\;(1\;3\;2),\;\;(1\;2),\;\;(1\;3),\;\;(2\;3)\}$에서 $$(1\;2\;3)=(1\;2)\circ(2\;3),\quad(1\;3\;2)=(2\;3)\circ(1\;2)$$이다. 

따라서 짝수-치환은 $1, (1\;2\;3),(1\;3\;2)$로 $|A_3|=3!/2=3$이다.

모든 큐브의 움직임을 치환으로 적을 수 있다.

예를 들면 FFRR은 (DF UF)(DR UR)(BR FR FL)(DBR UFR DFL)(ULF URB DRF)이다.

정리: 큐브의 움직임을 나타내는 치환은 항상 짝수-치환이다.

증명(면을 회전한 횟수 n에 대한 귀납법):

1) 움직이지 않은 큐브에서 n = 0 이면 움직이는 조각이 없다. 0은 짝수입니다.

2) n 번 움직인 후 치환을 $P(n)$이라고 하자.

P(n) → P(n + 1)을 나타내기 위해 P(n)을 짝수-치환이라고 가정하자.

일련의 움직임은 한 면의 회전으로 만들어진다. 한 면을 회전하는 움직임은 F = (FL FU FR FD)(FUL FUR FDR FDL) = (FL FU)(FL FR)(FL FD)(FUL FUR)(FUL FDR)(FUL FDL)이다. 이 치환에서 길이 4인 순환은 3개의 호환으로 쓸 수 있다. 총 6개의 호환이므로 면을 회전하는 치환은 짝수-치환이다. 이 사실은 모든 면의 회전에 적용된다. 

n번 움직인 큐브가 짝수-치환 P(n)을 가진다면 n + 1번 이동한 큐브는 한 면의 회전이 더해지기 때문에 P(n+1)도 짝수-치환이다. $\blacksquare$

루빅스 큐브의 모든 치환은 짝수-치환이므로 한 쌍의 조각만 바꾸는 치환은 없다. 즉, 조각 2개를 서로 바꾼다면 이에 따라 다른 조각도 바꿔야 한다. 우리가 바꾸려는 2개를 포함하여 3조각을 순환하는 3주기를 사용하여 이 문제를 해결할 것이다. 큐브 이동의 주기 구조에 대해 이야기할 때 다음 표기법이 도움이 된다.

• φ-corner는 꼭짓점 조각의 순환 구조를 설명한다. 
• φ-edge는 변 조각의 순환 구조를 설명한다.

꼭짓점 조각의 방향을 바르게 정렬하는 데 먼저 집중하고 변 조각은 신경 쓰지 않아도 될 때가 온다. 이때, 우리는 φ-corner만 처리하고 변 조각에 발생하는 모든 것을 무시한다. 그것은 둘을 분리하는 것이 도움이 된다. 또한 φ-corner의 모든 주기는 φ-edge에도 포함된 조각을 포함할 수 없다. 조각은 변 조각이면서 꼭짓점 조각일 수 없기 때문이다. 큐브의 중심이 고정되어 있기 때문에 φ-center는 생각할 필요가 없다.

부분군(Subgroup)과 잉여류

주어진 $G$의 부분집합 $H$가 이항연산 $*$에 대하여 군이 되면 $H$는 군 $G$의 부분군(subgroup)이라고 부른다.

복잡한 군의 구조를 살펴보려면 더 간단한 부분군을 연구해야 한다.

큐브의 움직임으로 만들어진 군을 $\mathcal{R}$이라고 하자. $S ⊆ \mathcal{R}$인 부분집합이면 $S$에 의해 생성된 부분군 $H$는 $S$의 모든 원소를 포함하는 $\mathcal{R}$의 가장 작은 부분군이다. 예를 들어 $\{F\}$는 앞면을 회전하여 얻을 수 있는 모든 가능한 다른 큐브 순열로 구성된 $\mathcal{R}$의 부분군인 $\{F, F^2, F^3 F^4\}$을 생성한다. $\{F, B, U, L, R, D\}$에 의해 생성된 군은 전체 군인 $\mathcal{R}$이다. 아래에 $\mathcal{R}$의 부분군 생성자의 몇 가지 보기가 있다.

• 어떤 한 면을 회전 $\{ F\}$
• 어떤 마주 보는 두 면을 회전 $\{ LR\}$
• 두 면을 회전 $\{RF\}$

항등원이 $e$인 군 $\mathcal{G}$의 원소 $g$가 $g^m=e$를 만족하는 $m$을 원소 $g$의 차수(order)라고 하자. 이 차수는 $g$가 생성하는 부분군의 원소의 개수가 된다. 

항등원인 처음으로 돌아가려면 특정 이동을 몇 번이나 반복해야 하는지에 따라 큐브 움직임을 설명하기 위해 차수의 개념을 사용할 수 있다.

예를 들어 이동 F는 면을 4번 회전하면 원래 상태로 돌아가므로 차수가 4인 부분군을 생성한다. 이동 FF는 두 번 반복하면 원래 상태로 돌아가므로 차수가 2인 부분군을 생성한다. 마찬가지로 일련의 이동은 특정 유한 순서를 갖는 하위 그룹의 생성자를 만든다. 정육면체는 배열의 한정된 수만 달성할 수 있고 움직일 때마다 패싯이 뒤섞이기 때문에 결국에는 적어도 일부 배열이 반복되기 시작한다. 따라서 우리는 큐브가 해결된 상태에서 시작하는 경우 한 동작을 반복해서 적용하면 결국 특정 수의 동작 후에 다시 해결된 상태로 되돌아감을 증명할 수 있다.

정리: 큐브가 6면이 모두 정렬된 상태에서 시작해 한 번의 움직임 $P$를 연속적으로 수행하면 결국 큐브는 다시 잘 정렬된 처음 상태로 돌아간다.

증명: 임의의 큐브 움직임을 $P$라고 하자.

 $P$가 적용되는 $m$번에서 $k<m$인 $k$일 때 배열이 되풀이되고 $m$은 같은 배열이 나타나는 가장 빠른 수라고 하자.

따라서 $P^k = P^m$이다.

따라서 $k=0$이어야 한다는 것을 보여주면 큐브가 풀린 상태인 $P^0$으로 다시 순환한다는 것을 증명한 것이다.

$k = 0$이면 $P^0 = 1 = P$이므로 증명이 끝난다.

이제 $k=0$이어야 한다는 것을 귀류법으로 증명하자.

만약 $k > 0$이면 $P^k$와 $P^m$ 모두에 $P^{−1}$을 적용하면 두 배치 $P^k$와 $P^m$이 동일하기 때문에 같은 결과를 얻는다.

그러면 $$P^kP^{-1}= P^mP^{-1} \rightarrow P^{k-1} = P^{m-1}.$$

그러나 이것은 모순이다. $m$이 같은 배열이 반복되는 첫 번째 수이기 때문에 $k=0$이다. 따라 모든 움직임은 결국 다른 배열을 반복하기 전에 먼저 초기 상태로 다시 돌아간다.$\blacksquare$

주어진 부분군 $H$와 $a\in G$에 대하여 아래와 같은 왼쪽과 오른쪽 잉여류를 정의할 수 있다.

$$aH=\{ah|h\in H\}\quad Ha=\{ha|h\in H\}$$

$a$는 역수가 있으므로 $\phi(h)=ah$로 주어진 사상 $\phi: H\rightarrow aH$은 전단사(bijection)이다. $G$의 모든 원소는 $H$의 왼쪽 잉여류 가운데 어느 하나에 속한다.

라그랑제 정리

${H}$의 왼쪽 잉여류의 개수는 ${G}$ 안에서 ${H}$의 지수(index)라고 하고 $[{G}:{H}]$로 적는다.

아래와 같은 라그랑제 정리가 성립한다. 이때 $|G|$와 $|H|$는 두 유한군 $\mathcal{G,H}$의 차수(order) 또는 위수로 두 집합  $G,H$의 원소의 개수이다.

$$ [G:H]={|G| \over |H|}$$

케일리 그래프(Cayley Graphs)

군과 부분군의 구조를 살펴보는 유용한 방법으로 케일리-그래프가 있다. 다음은 군 $\mathcal{G}$의 케일리-그래프를 설명한다.

• 각 원소 $g\in \mathcal{G}$는 꼭짓점
• 각 부분군의 생성자인 $s\in S$는 색 $C_s$로 약속 
• $g\in \mathcal{G}$,  $s\in S$와 짝이되는 $g$와 $gs$는 색 $C_s$인 화살표로 연결

보기. F로 생성되는 부분군

보기. $\phi=FF$와 $\rho=RR$로 생성되는 부분군 ($\phi^2=\rho^2=1$)

U에 대한 그래프를 그리려고 하면 어떻게 될까? 아니면 RRBB? 그들 각각 위에 표시된 것과 같은 케일리-그래프를 가진다. 두 군이 동일한 케일리-그래프를 가지면 본질적으로 동일한 구조를 가지며 동형(isomorphic)이라고 한다. 동형인 두 군은 큐브에서 동일한 순서와 동일한 효과를 가진다. 예를 들어 FFRR을 수행하는 것은 이제 L면이 앞에 오도록 큐브를 회전한 다음 RRBB를 수행하는 것과 같은 효과가 있다.

매크로

먼저 큐브 군 $\mathcal{R}$의 원소의 일부 속성을 정의하고 이러한 속성과 위에서 배운 내용을 사용하여 큐브를 해결할 수 있도록 특정하게 조각을 재배치하는 데 도움이 되는 조각 이동의 일부 매크로 또는 조합을 개발한다.

교환자(commutator)

루빅스 큐브를 움직이는 작업은 분명히 가환적이지 않다.

예를 들어 처음에 밝혔듯이 앞면(F)을 회전한 다음 오른쪽 면(R)을 회전하여 FR을 이동한다. 이는 오른쪽 면을 회전한 다음 앞면 또는 RF를 회전하는 것과 분명히 다르다. 연산이 서로 교환가능함을 설명하는 유용한 도구 중 하나는 $ [P.M]$으로 표시되는 교환자 $PMP^{ −1}M^{−1}$이다. 여기서 $P$와 $M$은 큐브의 두 움직임이다. $P$와 $M$이 가환적이면 $P$가 $P ^{−1}$을 상쇄하고 $M$도 마찬가지기 때문에 교환자는 항등원이 된다. 

두 연산은 같은 연산이거나 L과 R처럼 움직임이 서로 다른 조각 세트에 영향을 미치지 않을 때, 즉 $supp(P) ∩ supp(M) = ∅$일 때 교환적이다. (예 UDud=1, LRlr=1)

교환자가 항등식이 아닐 때 교환자를 적용하여 바뀐 큐브 조각의 수에 의해 "상대적 교환성"을 측정할 수 있다.  두 연산으로 움직이는 조각들의 교집합을 보면 이 척도에 대한 통찰을 얻을 수 있다.

1. $ FrfR$으로 $F$와 $r$이 겹치는 부분에 있는 모서리 조각들이 바뀌고 나머지는 제자리로 돌아간다.

$FrfR=a$

2. $ FrfR=a$라고 할 때 $aDa^{-1}d$를 실행하면 아래와 같이 단 세 조각만 바뀐 것을 볼 수 있다.

$FrfRDrFRf=aDa^{-1}d$

유용한 쌍의 이동에는 공통적으로 변경된 큐브 조각의 수가 적으며 교환자와 관련된 매크로가 계속해서 나타나는 것을 볼 수 있다. 

증명은 하지 않지만 교환자에 관한 쓸모 있는 정리는 다음과 같다.

$supp(g)∩supp(h)$이 한 조각이면 $[g, h]$ 차수 3인 순환이다. 다음은 매크로를 만드는데 쓸모 있는 교환자를 위한 방법이다.

• FUDLLUUDDRU은 윗면에서 정확히 하나의 변 조각을 뒤집는다.
• rDRFDf 면에 있는 조각 하나를 바꾼다.
• FF 슬라이스에서 변 조각을 바꾼다.
• rDR 세 꼭짓점 조각을 순환한다.

 

 

 

 

https://en.wikipedia.org/wiki/Rubik%27s_Cube_group

Rubik's Cube group - Wikipedia