루빅스 큐브의 불변성, 이동 회귀와 회전 제약에 관한 연구

개성고등학교

2608 김영현

초 록

루빅스 큐브는 정육면체가 3×3×3으로 쌓여 있는 모양으로, 절단된 부분을 통해 각각의 [eqn: 6]개 면이 돌아갈 수 있게 된 구조이다. 루빅스 큐브는 특정 상태에서 돌려서 절대로 맞출 수 없는 구조를 형성하는데, 이것을 적절한 불변량의 도입을 통해 증명한다. 같은 이동을 반복하면 원래 상태로 돌아오는 이유를 이동 회귀 수 개념을 이용하여 설명한다. 또한 큐브를 맞추는 알고리즘의 효율성에 직접적인 연관이 있는 제약에 관해서 설명한다. 특히 모서리 조각에 특별한 제약이 생기는 2-비대면 제약을, 이에 맞는 불변량인 [eqn: 2]-determinant를 도입하여 설명한다.

-  -

1. 소개

루빅스 큐브(Rubik's Cube)는 헝가리의 건축 교수인 에르뇌 루비크(Ernő Rubik)가 발명한 3D 퍼즐의 하나이다. 그림 1과 같이 생겼으며, 그림 2와 같이 각 면을 회전할 수 있는 구조이다.

그림 1 ThinkGeek (2014), “Rubik's Cube”, http://www.thinkgeek.com/product/69fe/. (2015-07-26)		그림 2 Wikipedia (2015), “Rubik's Cube”, http://en.wikipedia.org/wiki/Rubik%27s_Cube. (2015-07-26)

보통 큐브라고 부르는 것은 꼬임 퍼즐(Twisty Puzzle), 조합적 퍼즐(Combination Puzzle) 혹은 연속적 이동 퍼즐(Sequential Move Puzzle)이라고 부르는 것 중 루빅스 큐브의 구조, 이동 방식과 비슷한 3D 퍼즐을 의미한다. 꼬임 퍼즐에 조각 구성이 2×2×2, 4×4×4, 5×5×5인 정육면체 모양의 큐브가 포함된다. 이 부류에는 정사면체 모양의 피라밍크스(Pyraminx) 큐브, 정십이면체 모양의 메가밍크스(Megaminx) 큐브도 있으며, 15 퍼즐도 여기에 포함된다. (1) 여기에서는 루빅스 큐브, 즉 조각 구성이 3×3×3인 정육면체 큐브에 대해서만 다룰 것이므로, 큐브는 루빅스 큐브와 혼용한다.

2. 연구 내용

이 절에 나오는 다음 용어들은 논문의 전반에서 별도의 부연 설명 없이 사용된다.

회전(turn)은 큐브의 한 면을 잡고 돌리는 것으로, 그림 3과 같이 여섯 가지가 존재한다. 특정 회전을 순서대로 모은 것을 이동(move)이라 한다. 이동 [eqn: M], [eqn: N]의 최후 조각 위치가 같은 경우 같은 이동으로 보고, [eqn: M=N]으로 표시한다. 이동 [eqn: M], [eqn: N]을 순서대로 연속해서 적용한 것은 [eqn: MN]으로 표시한다. [eqn: M ^{1} =M], [eqn: M^{n} = M^{n-1}M] 등의 notation도 그대로 사용한다. 회전을 하나도 하지 않은 것도 편의상 이동이라고 부르며, 특히 항등이동(identity move)이라 하고 [eqn: I]로 표시한다. 어떤 이동 [eqn: M]에 대해 그 역이동(inverse move)은 [eqn: MN=I]이고 [eqn: u(N)=u(M)]인 이동 [eqn: N]이며 [eqn: M^{-1}]로 쓴다. 회전 [eqn: T]에 대해 [eqn: T ^{4} =I]이므로 회전에 대해서 [eqn: T^{-1}]라는 표현보다 [eqn: T^{3}]을 사용한다.

엄밀한 증명을 원한다면, 회전의 개수가 [eqn: 6]개이므로 [eqn: 6]면을 모두 네 번씩 돌려 보면 된다.

그림 3

이동 [eqn: M]의 회전수는 [eqn: M]의 회전의 개수이며 [eqn: u(M)]으로 표기한다. 이동 [eqn: M], [eqn: N]에 대해 [eqn: M=N]이라도 [eqn: u(M) != u(N)]일 수 있다. 이러한 번거로움을 해결하기 위해 이동 [eqn: M]에 대해 최소 회전수를 [eqn: LEFT { u(X)`|`X=M RIGHT }]의 최솟값으로 정의하고 [eqn: c(M)]으로 쓴다.

역이동의 정의가 well-defined임을 보장할 수 없으므로, 우선 이 문제부터 해결한다. 이것을 위해서는 역이동이 존재하고 유일함을 보이면 된다.

정리 1. 이동 [eqn: M], [eqn: N]에 대해 [eqn: MN=I]이면 [eqn: NM=I]이다.

증명. [eqn: M=I]이면 [eqn: N=MN=I]이기 때문에 자명하다.

[eqn: M neq I]인 경우를 보자. [eqn: N=I]라면 [eqn: M = MN = I]가 되어 모순이다. 따라서 [eqn: N neq I]이며, 자연수 [eqn: m=u(M)], [eqn: n=u(N)]과 회전 [eqn: T_1], [eqn: cdots], [eqn: T _{m}], [eqn: U_1], [eqn: cdots], [eqn: U _{n}]에 대해 [eqn: M=T _{1} CDOTS T _{m}], [eqn: N=U _{1} CDOTS U _{n}]으로 둘 수 있다. 여기서 [eqn: MN=T _{1} CDOTS T _{m} U _{1} CDOTS U _{n} =I]이므로

[eqn: (T _{m} ^{3} CDOTS T _{1} ^{3} )T _{1} CDOTS T _{m} U _{1} CDOTS U _{n} (T _{1} CDOTS T _{m} )=(T _{m} ^{3} CDOTS T _{1} ^{3} )(T _{1} CDOTS T _{m} )]

이 되는데, 위 식을 정리하면 [eqn: (U _{1} CDOTS U _{n})( T _{1} CDOTS T _{m}) =I]에서 [eqn: NM = I]를 곧바로 얻는다.

정리 2. 역이동은 존재하며 유일하다.

증명. (존재성) 회전수에 관한 수학적 귀납법을 사용한다. [eqn: u(M)=0]인 경우 [eqn: M=I]이므로 자기 자신을 역이동으로 갖는다. [eqn: u(M)=1]인 경우 앞에서 살펴본 것처럼 [eqn: M^{4} = M(M^{3})=I]이다. [eqn: u(M) LEQ k]인 경우, 모든 이동에 역이동이 존재한다고 하자. [eqn: u(M)=k+1]인 경우 이동 [eqn: M]은 항동이동이 아닌 이동 [eqn: M_1], [eqn: M_2]에 대해 [eqn: M = M_1 M_2]로 쓸 수 있으며, [eqn: u(M _{1} )leq k], [eqn: u(M_{2}) leq k]라서 역이동이 존재하므로 [eqn: M_1], [eqn: M_2]의 역이동을 순서대로 [eqn: N_1], [eqn: N_2]라고 할 수 있다. 이제

[eqn: M(N _{2} N _{1}) =M _{1} M _{2} N _{2} N _{1} =M _{1} {I}N _{1} =M _{1} N _{1} =I]

이므로 [eqn: M]은 [eqn: N_2 N_1]을 역이동으로 갖는다.

(유일성) 이동 [eqn: M]이 역이동으로 [eqn: N_1], [eqn: N_2]를 갖는다고 하자. 정리 1에서 [eqn: MN_{1} = I]이므로 [eqn: N_{1} M=I]이다. 따라서 [eqn: N_{1} = N_{1}(MN_{2}) = (N_{1} M)N_{2} = N_{2}]이다.

정리 2에 의해 각 이동에 역이동은 하나씩 존재하므로 역이동이 well-defined라는 것을 증명하였다. 또한 정리 1과 정리 2에 의해 역이동의 역이동은 자기 자신임을 알 수 있다.

루빅스 큐브를 [eqn: 3^{3} = 27]개의 작은 1×1×1 큐브로 인식할 수 있다. 그중 외부와 0개의 면을 접촉하고 있는 것을 중심부(core), 1개의 면을 접촉하고 있는 것을 가운데 조각(center), 2개의 면을 접촉하고 있는 것을 모서리 조각(edge), 3개의 면을 접촉하고 있는 것을 귀퉁이 조각(corner)이라 한다. 중심부를 제외한 위치는 그림 4와 같고, 루빅스 큐브에 중심부는 1개, 가운데 조각은 6개, 모서리 조각은 12개, 귀퉁이 조각은 8개가 있다. 모든 회전은 중심부와 가운데 조각을 이동시키지 않는다.

그림 4. 왼쪽부터 가운데 조각, 모서리 조각, 귀퉁이 조각의 위치이다.

큐브의 각 조각과 그 위치에 그림 5와 같이 번호를 붙인다. 이때 번호가 겹치는 것은 모서리 1번 조각, 귀퉁이 1번 조각, 모서리 1번 위치와 같이 구분해서 부른다. 모서리 조각 혹은 귀퉁이 조각의 위치 변환 상태(permutation status)를 각 조각의 위치에 각 조각의 번호를 대응시킨 함수로 정의한다. 정의역과 치역은 모서리 조각의 경우 [eqn: ℤ_{12}+1], 귀퉁이 조각의 경우 [eqn: ℤ_{8}+1]이 될 것이다.

[eqn: ℤ _{n} := LEFT { m:0 LEQ m<n,`m IN ℤ RIGHT }]로 정의하며, 정수 집합 [eqn: S]와 정수 [eqn: n]에 대해 [eqn: S+n]을 [eqn: left{ x+n : x in S right}]로 정의한다.

가운데 조각이 가진 면을 제외한 큐브의 각 조각의 면에 그림 6과 같이 번호를 붙인다. 각 조각에서 해당하는 방향 번호(orientation number)는 큐브가 맞춰진 상태에서 0번인 면이 현재 상태에서 가리키고 있는 번호이다. 모서리 조각 혹은 귀퉁이 조각의 방향 변환 상태(orientation status)를 각 조각의 번호에 각 조각의 방향 번호를 대응시킨 함수로 정의한다. 모서리 조각의 경우 정의역은 [eqn: ℤ_{12}+1], 치역은 [eqn: ℤ_{2}]이며, 귀퉁이 조각의 경우 정의역은 [eqn: ℤ_{8}+1], 치역은 [eqn: ℤ_{3}]이다. 이때 치역의 원소는 [eqn: ℤ/nℤ]의 representatives로 인식한다.

그림 5		그림 6

2.1 불변성

귀퉁이 조각의 생각할 수 있는 위치 변환 상태는 총 [eqn: 8!]가지이다. 그리고 각각의 회전은 귀퉁이 조각의 위치를 변화시키며 다른 위치 변환 상태로의 접근을 가능케 한다. 이를테면 회전 [eqn: U]는 위치 변환 상태 [eqn: f]를

[eqn: g(1)=f(4)], [eqn: g(2)=f(1)], [eqn: g(3)=f(2)], [eqn: g(4)=f(3)]

[eqn: g(c)=f(c)```````````` FORALLc` in `ℤ_{4}+5]

인 다른 위치 변환 상태 [eqn: g]로 만들어 주므로, 이 회전 [eqn: U]를 범함수로 생각하면, [eqn: U(f)=g]라는 표현이 가능해질 것이다.

범함수 [eqn: T]와 귀퉁이 조각의 위치 변환 상태 [eqn: f], [eqn: g]에 대해 [eqn: T(f)=g]이면 이 범함수의 귀퉁이 위치 부호(corner permutation signum)를 [eqn: rm sgn it f cdot rm sgn it g]로 정의하고 [eqn: rm sgnp_{it c} it T]로 쓴다. 회전 [eqn: 6]개에 대해서 직접 계산해 보면 범함수 [eqn: U], [eqn: D], [eqn: L], [eqn: R], [eqn: F], [eqn: B]의 귀퉁이 위치 부호는 모두 잘 정의되었음을 알 수 있으며 그 값은 모두 [eqn: -1]이다. 표 1을 참고하라. 귀퉁이 위치 부호를 이용해 다음 정리를 증명할 수 있다.

[eqn: c]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 5]	[eqn: 6]	[eqn: 7]	[eqn: 8]
[eqn: U]	[eqn: 4]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 5]	[eqn: 6]	[eqn: 7]	[eqn: 8]
[eqn: D]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 6]	[eqn: 7]	[eqn: 8]	[eqn: 5]
[eqn: L]	[eqn: 2]	[eqn: 6]	[eqn: 3]	[eqn: 4]	[eqn: 1]	[eqn: 5]	[eqn: 7]	[eqn: 8]
[eqn: R]	[eqn: 1]	[eqn: 2]	[eqn: 4]	[eqn: 8]	[eqn: 5]	[eqn: 6]	[eqn: 3]	[eqn: 7]
[eqn: F]	[eqn: 5]	[eqn: 2]	[eqn: 3]	[eqn: 1]	[eqn: 8]	[eqn: 6]	[eqn: 7]	[eqn: 4]
[eqn: B]	[eqn: 1]	[eqn: 3]	[eqn: 7]	[eqn: 4]	[eqn: 5]	[eqn: 2]	[eqn: 6]	[eqn: 8]
표 1. 범함수 [eqn: T]가 [eqn: T(f)=g], [eqn: g(c)=f(v)]일 때 [eqn: v]의 값을 나열하였다.

정리 3. 이동 [eqn: M], [eqn: N]에 대해 [eqn: M=N]라면 [eqn: u(M)+u(N)]은 짝수이다.

증명. 이동 [eqn: N]에 대해 [eqn: N^{-1}]이 존재하여 [eqn: MN^{-1}=I]이고,

[eqn: u(MN^{-1})=u(M)+u(N^{-1})=u(M)+u(N)]

이므로 이동 [eqn: M]에 대해 [eqn: M=I]이면 [eqn: u(M)]이 짝수임을 보이면 된다. 이때 [eqn: u(M)=0]이면 자명하므로 [eqn: u(M) neq 0]일 때만 증명한다.

임의의 회전 [eqn: T]에 대해 [eqn: rm sgnp _{it c rm} it T=-1]이다. 따라서 회전 [eqn: T_{1}], [eqn: T_{2}], [eqn: cdots], [eqn: T_{u(M)}]에 대해 [eqn: M=T_{1}T_{2}cdotsT_{u(M)}]으로 쓸 수 있고

[eqn: rm sgnp _{c} it M= rm sgnp _{it c rm} it LEFT ( T _{1} T _{2} CDOTS T _{u(M)} RIGHT ) = rm sgnp _{it c rm} it T _{1} rm sgnp _{it c rm} it T _{2} CDOTS rm sgnp _{it c rm} it T _{u(M)} =(-1) ^{u(M)}]

이다. 이제 [eqn: rm sgnp_{c} it M = rm sgnp_{c} it I = 1]에서 [eqn: u(M)]이 짝수이다.

따름정리 4. 이동 [eqn: M]에 대해 [eqn: LEFT { u(X)`|`X=M RIGHT }]은 [eqn: ℤ/2ℤ]의 원소의 부분집합이다.

따름정리 4는 홀수 번 돌려서 섞은 것은 홀수 번에, 짝수 번 돌려서 섞은 것은 짝수 번에 맞춰야 함을 의미한다.

범함수 [eqn: T]와 모서리 조각의 위치 변환 상태 [eqn: f], [eqn: g]에 대해 [eqn: T(f)=g]이면 이 범함수의 모서리 위치 부호(edge signum)를 [eqn: rm sgn it f cdot rm sgn it g]로 정의하고 [eqn: rm sgnp _{it e rm} it T]로 쓴다. 마찬가지로 회전 [eqn: 6]개에 대해서 직접 계산해 보면 범함수 [eqn: U], [eqn: D], [eqn: L], [eqn: R], [eqn: F], [eqn: B]의 모서리 위치 부호는 모두 잘 정의되었음을 알 수 있으며 그 값은 모두 [eqn: -1]이다. 표 2를 참고하라. 귀퉁이 위치 부호와 모서리 위치 부호를 이용해 다음 정리를 증명할 수 있다.

[eqn: c]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 5]	[eqn: 6]	[eqn: 7]	[eqn: 8]	[eqn: 9]	[eqn: 10]	[eqn: 11]	[eqn: 12]
[eqn: U]	[eqn: 4]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 5]	[eqn: 6]	[eqn: 7]	[eqn: 8]	[eqn: 9]	[eqn: 10]	[eqn: 11]	[eqn: 12]
[eqn: D]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 5]	[eqn: 6]	[eqn: 7]	[eqn: 8]	[eqn: 10]	[eqn: 11]	[eqn: 12]	[eqn: 9]
[eqn: L]	[eqn: 6]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 1]	[eqn: 9]	[eqn: 7]	[eqn: 8]	[eqn: 5]	[eqn: 10]	[eqn: 11]	[eqn: 12]
[eqn: R]	[eqn: 1]	[eqn: 2]	[eqn: 8]	[eqn: 4]	[eqn: 5]	[eqn: 6]	[eqn: 3]	[eqn: 11]	[eqn: 9]	[eqn: 10]	[eqn: 7]	[eqn: 12]
[eqn: F]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 5]	[eqn: 12]	[eqn: 6]	[eqn: 7]	[eqn: 4]	[eqn: 9]	[eqn: 10]	[eqn: 11]	[eqn: 8]
[eqn: B]	[eqn: 1]	[eqn: 7]	[eqn: 3]	[eqn: 4]	[eqn: 5]	[eqn: 2]	[eqn: 10]	[eqn: 8]	[eqn: 9]	[eqn: 6]	[eqn: 11]	[eqn: 12]
표 2. 범함수 [eqn: T]가 [eqn: T(f)=g], [eqn: g(c)=f(v)]일 때 [eqn: v]의 값을 나열하였다.

정리 5. 이동 [eqn: M]에 대해 [eqn: rm sgnp _{it c rm} it M CDOT rm sgnp _{it e rm} it M=1]이다.

증명. [eqn: M=I]이면 자명하므로 [eqn: M neq I]인 경우만 증명한다.

[eqn: M=T_{1}T_{2}cdots T_{u(M)]이라 할 수 있다. 임의의 회전 [eqn: T]에 대해 [eqn: rm sgnp_{it c}it T=-1]이고 [eqn: rm sgnp _{it e rm} it T] 역시 [eqn: -1]이므로

[eqn: rm sgnp _{it c rm} it M CDOT rm sgnp _{it e rm} it M&= rm sgnp _{it c rm} it LEFT ( T _{1} T _{2} CDOTS T _{u(M)} RIGHT ) rm sgnp _{it e rm} it LEFT ( T _{1} T _{2} CDOTS T _{u(M)} RIGHT )# &= rm sgnp _{it c rm} it T _{1} rm sgnp _{it c rm} it T _{2} CDOTS rm sgnp _{it c rm} it T _{u(M)} rm sgnp _{it e rm} it T _{1} rm sgnp _{it e rm} it T _{2} CDOTS rm sgnp _{it e rm} it T _{u(M)}# &=(-1) ^{2u(M)} =1]

이다.

위 정리에 의해 나머지 조각은 모두 제 위치에 있으면서 어느 두 모서리 조각만 바뀌거나 어느 두 귀퉁이 조각만 바뀐 것은 돌려서 맞출 수 없음을 알 수 있다. 상태의 모서리 위치 부호와 귀퉁이 위치 부호의 곱이 [eqn: -1]이기 때문이다.

방향 변환 상태에서도 마찬가지이다. 다만 각각의 회전은 방향뿐 아니라 위치까지 변화시킨다. 이를테면 회전 [eqn: R]은 귀퉁이 조각의 방향 변환 상태 [eqn: f]를

[eqn: g(1)=f(1)], [eqn: g(2)=f(2)], [eqn: g(3)=f(4)+2], [eqn: g(4)=f(8)+1],

[eqn: g(5)=f(5)], [eqn: g(6)=f(6)], [eqn: g(7)=f(3)+1], [eqn: g(8)=f(7)+2]

인 다른 귀퉁이 조각의 방향 변환 상태 [eqn: g]로 만들어 주는 범함수이다. 표 3을 참고하면, 모든 회전에 대해 [eqn: sum_{n=1}^{8}{g(n)}-sum_{n=1}^{8}{f(n)}]의 값이 항상 [eqn: 0]임을 알 수 있다. 따라서 다음 정리를 이끌어낼 수 있다.

방향 변환 상태의 모든 연산은 [eqn: ℤ/3ℤ]에서 이루어진다.

[eqn: c]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 5]	[eqn: 6]	[eqn: 7]	[eqn: 8]
[eqn: U]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]
[eqn: D]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]
[eqn: L]	[eqn: 1]	[eqn: 2]	[eqn: 0]	[eqn: 0]	[eqn: 2]	[eqn: 1]	[eqn: 0]	[eqn: 0]
[eqn: R]	[eqn: 0]	[eqn: 0]	[eqn: 2]	[eqn: 1]	[eqn: 0]	[eqn: 0]	[eqn: 1]	[eqn: 2]
[eqn: F]	[eqn: 2]	[eqn: 0]	[eqn: 0]	[eqn: 1]	[eqn: 1]	[eqn: 0]	[eqn: 0]	[eqn: 2]
[eqn: B]	[eqn: 0]	[eqn: 1]	[eqn: 2]	[eqn: 0]	[eqn: 0]	[eqn: 2]	[eqn: 1]	[eqn: 0]
표 3. 범함수 [eqn: T]가 [eqn: T(f)=g], [eqn: g(c)=f(v)+a]일 때 [eqn: a]의 값을 나열하였다. [eqn: v]의 값은 표 1에 있다.

정리 6. 이동 [eqn: M]의 상응하는 귀퉁이 조각의 방향 변환 상태 [eqn: f]에 대해 [eqn: sum_{n=1}^{8}f(n)=0]이다.

증명. [eqn: M=I]인 경우 [eqn: f(c)=0,````````FORALL c`in `ℤ_{8}+1]이므로 자명하다. [eqn: u(M)=k]인 경우 증명되었다고 하자. [eqn: u(M)=k+1]인 경우 회전 [eqn: T]와 이동 [eqn: N]에 대해 [eqn: M=NT]로 쓸 수 있다. [eqn: N]의 귀퉁이 조각의 방향 변환 상태를 [eqn: h]라고 하면 [eqn: sum_{n=1}^{8}f(n)-sum_{n=1}^{8}h(n)=0]이다. 따라서

[eqn: sum_{n=1}^{8}f(n) = sum_{n=1}^{8}h(n)+left(sum_{n=1}^{8}{f(n)}-sum_{n=1}^{8}{h(n) right)=0]

이다.

위 정리에 의해 나머지 조각이 모두 제자리에 있으면서 귀퉁이 조각 하나만 제자리에서 바뀌어 있는 것은 돌려서 맞출 수 없음을 알 수 있다. 상태의 귀퉁이 조각의 방향 변환 상태의 합이 [eqn: 0]이 아니기 때문이다.

모서리 조각의 방향 변환 상태에서도 마찬가지로, 모든 회전에 대해 [eqn: sum_{n=1}^{12}g(n)-sum_{n=1}^{12}f(n)]의 값이 항상 [eqn: 0]임을 알 수 있다. 표 4를 참고하라. 정리 6과 거의 비슷한 방식으로 다음 정리를 증명할 수 있다.

[eqn: c]	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 5]	[eqn: 6]	[eqn: 7]	[eqn: 8]	[eqn: 9]	[eqn: 10]	[eqn: 11]	[eqn: 12]
[eqn: U]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]
[eqn: D]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]
[eqn: L]	[eqn: 1]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 1]	[eqn: 1]	[eqn: 0]	[eqn: 0]	[eqn: 1]	[eqn: 0]	[eqn: 0]	[eqn: 0]
[eqn: R]	[eqn: 0]	[eqn: 0]	[eqn: 1]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 1]	[eqn: 1]	[eqn: 0]	[eqn: 0]	[eqn: 1]	[eqn: 0]
[eqn: F]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]
[eqn: B]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]	[eqn: 0]
표 4. 범함수 [eqn: T]가 [eqn: T(f)=g], [eqn: g(c)=f(v)+a]일 때 [eqn: a]의 값을 나열하였다. [eqn: v]의 값은 표 2에 있다.

정리 7. 이동 [eqn: M]의 상응하는 모서리 조각의 방향 변환 상태 [eqn: f]에 대해 [eqn: sum_{n=1}^{12}f(n)=0]이다.

증명. [eqn: M=I]인 경우 [eqn: f(c)=0,````````FORALL c`in `ℤ_{12}+1]이므로 자명하다. [eqn: u(M)=k]인 경우 증명되었다고 하자. [eqn: u(M)=k+1]인 경우 회전 [eqn: T]와 이동 [eqn: N]에 대해 [eqn: M=NT]로 쓸 수 있다. [eqn: N]의 모서리 조각의 방향 변환 상태를 [eqn: h]라고 하면 [eqn: sum_{n=1}^{12}f(n)-sum_{n=1}^{12}h(n)=0]이다. 따라서

[eqn: sum_{n=1}^{12}f(n) = sum_{n=1}^{12}h(n)+left(sum_{n=1}^{12}{f(n)}-sum_{n=1}^{12}{h(n) right)=0]

이다.

정리 5, 정리 6, 정리 7에 의해 큐브를 돌려서 생기는 상태의 경우의 수는 큐브를 “분해 후 재조립”했을 때 상태의 경우의 수 [eqn: 8! cdot 12! cdot 3^{8} cdot 2^{12}=519,024,039,293,878,272,000]에서, 각각 반, [eqn: 1 over 3], 반이 줄어들어 [eqn: 1 over 12] 이하가 됨을 알 수 있다. 이제 귀퉁이나 모서리의 오리엔테이션이나 퍼뮤테이션에서의 정리 3, 정리 5, 정리 6, 정리 7 이외의 invariant가 없음을 보인다. 이를 위해서는 다음의 정리로 충분하다.

정리 8. 다음 조건

[eqn: C_{2}]의 귀퉁이 방향 변환 상태 [eqn: f]에 대해 [eqn: f(3)=1], [eqn: f(4)=2]

[eqn: E _{2}]의 모서리 방향 변환 상태 [eqn: g]에 대해 [eqn: g(3)=1], [eqn: g(4)=1]

[eqn: X _{4}]는 [eqn: 3]번 모서리와 [eqn: 4]번 모서리, [eqn: 3]번 귀퉁이와 [eqn: 4]번 귀퉁이가 서로 바뀜

을 만족하는 이동 [eqn: C_{2}], [eqn: E_{2}], [eqn: X_{4}]가 존재한다. 단, 주어지지 않은 함수나 함숫값은 [eqn: I]와 그 함수나 값이 같다.

증명. [eqn: C _{2}=LUL^{3}ULU^{2}L^{3}R^{3}U^{3}RU^{3}R^{3}U^{2}R],

[eqn: E_{2}=UFUF^{2}D^{3}L^{3}U^{3}LUDF^{2}U^{2}F^{3}],

[eqn: X_{4}=RU^{2}R^{3}U^{3}RU^{2}L^{3}UR^{3}U^{3}L].

정리 8에 의해 [eqn: rm sgn_{it c} it S cdot rm sgn_{it e} it S = 1]이며 귀퉁이 조각과 모서리 조각의 위치 변환 상태를 순서대로 [eqn: f], [eqn: g]라 할 때 [eqn: sum_{n=1}^{8}f(n)=0], [eqn: sum_{n=1}^{8}g(n)=0]인 모든 상태 [eqn: S]에는 대응하는 이동이 존재한다. 따라서 큐브를 돌려서 생기는 상태의 경우의 수는

[eqn: {8!cdot12!cdot3^{8}cdot2^{12}}over{2cdot 3cdot 2}=43,252,003,274,489,856,000]

이 된다.

2.2 이동 회귀

이동 회귀(movement return)란, 맞춰진 상태에서 같은 이동을 반복해서 시행하면 다시 맞춰진 상태로 되돌아오는 현상을 뜻한다. 이 현상이 왜 일어나는지에 답하기 위해서 이동 회귀 수를 정의한다. 이동 [eqn: M]에 대해 이동 회귀 수(the number of movement return)는 [eqn: left{n:M^{n}=I,````n`in`ℕright}]의 최솟값이다. 모든 이동에 대해 이동 회귀 수가 well-defined임을 보이면, 이동 회귀가 설명될 것이다. 이 절에서도 회전과 이동을 범함수로 인식할 수 있다.

범함수 [eqn: M]이 귀퉁이 혹은 모서리 조각의 방향 변환 상태 [eqn: M(f)=g], [eqn: f(c)=g(v)]일 때 [eqn: c]들을 1행에, [eqn: v]들을 2행에 쓴 다음 표기

[eqn: M= {pmatrix{1&2&3&4&5&6&7&8#2&3&7&4&5&6&8&1}}= {pmatrix{1&2&3&7&8#2&3&7&8&1}}], [eqn: M= {pmatrix{1&2&3&4&5&6&7&8&9&10&11&12#2&3&7&1&5&6&11&4&9&10&8&12}}= {pmatrix{1&2&3&7&11&8&4#2&3&7&11&8&4&1}}]

예시는 [eqn: M=RU]이다.

를 행렬 닮은꼴(matrix-like form)이라고 부르며, column 등의 행렬 용어를 그대로 사용한다. 또 이를 치환(permutation)으로도 보아 signum 등의 용어도 사용한다. 행렬 닮은꼴로 조각 변화의 일부 혹은 전부를 나타낼 수 있으며, 일부만 나타낸 경우 나타내지 않은 조각은 변화하지 않는 것으로 간주한다.

[eqn: n]이 자연수일 때, 서로 다른 [eqn: n]개의 자연수 [eqn: i_1], [eqn: i_2], [eqn: cdots], [eqn: i_n]에 대해 다음 행렬 닮은꼴

[eqn: {pmatrix{i _{1}&i _{2}&i _{3}&CDOTS &i _{n-1}&i _{n}#i _{2}&i _{3}&i _{4}&CDOTS &i _{n}&i _{1}}}]

을 [eqn: bold n]-cycle, 혹은 [eqn: n]을 드러낼 필요가 없을 때 그냥 cycle이라고 부른다. [eqn: n]-cycle [eqn: L]은 [eqn: L ^{n} =I]를 만족하므로 [eqn: 1]-cycle은 [eqn: L=I]를 만족하는 것, 즉 항등 사상으로 본다. cycle을 이용하면 다음 정리를 증명할 수 있다.

정리 9. 유한개의 column을 가진 행렬 닮은꼴 [eqn: L]에 대해 [eqn: L^{n}=I]가 되는 자연수 [eqn: n]이 존재한다.

증명. [eqn: L]에 있는 1행의 첫 번째 원소를 [eqn: i_{1}]이라고 하자. 2행의 해당하는 위치에 있는 원소를 [eqn: i_{2}]라고 하고, [eqn: i_{2}]에 대해 같은 시행을 반복한다. 자연수 [eqn: k]에 대해 [eqn: i_{k}=i_{1}]이 되게 하는 [eqn: k]가 반드시 존재한다. 이 변화를 묶어 [eqn: L_{1}]이라고 하자. [eqn: L_{1}]에 없는 원소 중 가장 처음에 있는 원소를 골라 같은 시행을 반복하면 [eqn: L_{2}], [eqn: cdots], [eqn: L_{l}]이 만들어진다.

column이 유한개이므로.

이 작업을 cycle decomposition이라고 한다. 또 여기서 [eqn: L_1], [eqn: L_{2}], [eqn: cdots], [eqn: L_{l}]들을 disjoint cycle이라고 한다.

이들은 [eqn: L=L_{1} L_{2} cdots L_{l}]을 만족하며, 각각이 포함하는 원소가 모두 다르므로 순서를 바꿀 수 있다. 또한 [eqn: L_{k}]([eqn: k=1,2,cdots,l])들은 cycle임이 분명하므로 [eqn: c_k]-cycle이라고 하자. 이제

[eqn: L ^{c _{1} c _{2} CDOTS c _{l}} = LEFT ( L _{1} L _{2} CDOTS L _{l} RIGHT ) ^{c _{1} c _{2} CDOTS c _{l}} & =L _{1} ^{c _{1} c _{2} CDOTS c _{l}} L _{2} ^{c _{2} c _{1} c _{3} CDOTS c _{l}} CDOTS L _{l} ^{c _{l} c _{1} c _{2} CDOTS c _{l-1}}# & =I ^{ c _{2} CDOTS c _{l}} I ^{c _{1} c _{3} CDOTS c _{l}} CDOTS I ^{c _{1} c _{2} CDOTS c _{l-1}}=I]

이다. 따라서 [eqn: n=c_{1}c_{2}cdots c_{l}]로 두면 원하는 결과를 얻는다.

이동 [eqn: M]의 위치 변환 상태에 대해서만 주목해 보자. [eqn: M]의 위치 변환 상태에는 귀퉁이 조각과 모서리 조각이 있다. 이들을 각각 [eqn: M_{c}], [eqn: M_{e}]라고 두고 편의상 [eqn: M_{e}]의 원소에 모두 [eqn: 8]을 더해 [eqn: M_{c}]와 [eqn: M_{e}]의 원소 중 겹치는 것이 없도록 한다. 그렇다면 [eqn: M_{c}^k_{c}=I], [eqn: M_{e}^{k_{e}} = I]가 되는 [eqn: k_{c}]와 [eqn: k_{e}]가 존재한다. 그렇다면 정리 9의 증명과 비슷하게

[eqn: M^{k_{c} k_{e}} = M_{c}^{k_{c}k_{e}} M_{e}^{k_{e}k_{c}} = I^{k_{e}}I^{k_{c}} = I]

이므로, 같은 이동을 계속해서 반복하면 조각이 제 위치를 찾게 될 때가 있다. 다음 정리는 이동 회귀 수의 well-definedness를 보인다.

정리 10. 회전 [eqn: M]에 대해 [eqn: M^{n}=I]가 되게 하는 자연수 [eqn: n]이 존재한다.

증명. 정리 9와 이후의 논의에서 회전 [eqn: M]에 대해 [eqn: M^{c}]가 모든 조각이 제 위치를 찾도록 만들어 주는 자연수 [eqn: c]가 존재한다는 것을 알았다.

이제 귀퉁이 조각의 방향이 맞지 않은 경우, [eqn: 1+1+1=0], [eqn: 2+2+2=0]이므로 [eqn: M^{3c}]가 귀퉁이 조각의 방향과 위치, 모서리 조각의 위치를 맞게 한다. 여기에서 모서리 조각의 위치가 맞지 않는 경우 마찬가지로 [eqn: left(M^{3c}right)^{2}=M^{6c}]가 그것을 맞게 한다. 즉 [eqn: M^{6c}]는 귀퉁이 조각과 모서리 조각의 방향과 위치를 맞게 한다. 따라서 [eqn: n=6c]로 두면 원하는 결과를 얻는다.

[eqn: ℤ/3ℤ]에서의 연산이다.

이동 회귀 수는 모든 이동에 대해 well-defined이다. 이동 회귀 수가 가장 작은 이동은 무엇일까? 자연수의 최솟값은 [eqn: 1]이므로, 가장 작은 이동 회귀 수는 [eqn: 1]임을 알 수 있으며, 정의에서 [eqn: M=I]이면 된다는 것도 알 수 있다. 그렇다면 이동 회귀 수가 가장 큰 이동은 무엇일까? 정리 9와 정리 10의 증명에서 알 수 있듯이, 최소공배수가 이동 회귀 수와 관련이 있다. 어떤 방향 변환 상태가 주어질 때 이동 회귀 수를 그와 같은 위치 변환 상태에서 최대 [eqn: 6]배밖에 늘리지 못한다는 점을 감안하면, 위치 변환 상태의 이동 회귀 수의 최댓값을 찾아서 [eqn: 6]배 하면 그것이 상태 전체의 이동 회귀 수가 될 것이다.

이동 [eqn: M]의 위치 변환 상태에는 귀퉁이 조각과 모서리 조각의 위치 변환 상태가 있다. 이들을 순서대로 [eqn: M_{c}], [eqn: M_{e}]라고 하고 편의상 [eqn: M_{e}]의 모든 원소에 [eqn: 8]을 더하면 [eqn: 20]개의 column을 가진 행렬 닮은꼴을 만들 수 있다. 따라서 우리가 고려해야 할 행렬 닮은꼴은 [eqn: n=20]인 경우이며, cycle decomposition 결과 각 [eqn: a_{n}]-cycle이 나왔다면, [eqn: a_{n}]들의 최소공배수가 가장 큰 것을 찾는 것이 목적이다.

그러나 column이 [eqn: 20]개인 행렬 닮은꼴을 모두 고려해서는 안 된다. 정리 5를 만족하기 위해서 행렬 닮은꼴의 signum은 [eqn: 1]이어야 한다. 그런데 [eqn: 2k]-cycle들은 그 signum이 [eqn: -1]이므로, [eqn: 2k]-cycle이 짝수 개 나와야 한다. 또한 귀퉁이와 모서리는 서로 자리바꿈을 할 수 없으므로 cycle들이 반드시 [eqn: 8]과 [eqn: 12]로 분리되어야 한다. 종합하면 우리의 문제는 다음과 같다.

[eqn: 20=c_{1}+c_{2}+cdots + c_{n}]인 자연수 [eqn: c_{1}], [eqn: c_{2}], [eqn: cdots], [eqn: c_{n}]로 나눌 수 있다. 이렇게 만들어진 순서쌍 [eqn: (c_{1}, c_{2}, cdots, c_{n})] s. t. [eqn: (-1)^{n}=1], [eqn: exists k < n] s. t. [eqn: sum_{i=1}^{k}c_{i}=8]인 것들 중 [eqn: rm lcm it (c _{1} ,c _{2} , CDOTS ,c _{k} )]가 최대가 되는 [eqn: c_{1}], [eqn: c_{2}], [eqn: cdots], [eqn: c_{k}]는?

이 문제는 일반적인 경우 NP-complete로 알려져 있다. 하지만 [eqn: 20]은 작으므로 프로그래밍을 통해 모든 경우의 수를 조사해 보았다. (2) 그 결과 다음 다섯 가지

이것을 찾아내는 프로그램의 루틴이 약 [eqn: 2^{n}]번 돌아간다. 보통의 컴퓨터에서 초당 약 [eqn: 10^{8}]번의 루틴이 돌아가므로, [eqn: n=20]은 아주 작은 수라고 할 수 있다.

[eqn: (1+7)+(2+2+3+5)], [eqn: (1+2+5)+(2+3+7)], [eqn: (1+2+2+3)+(5+7)],

[eqn: (3+5)+(1+2+2+7)], [eqn: (2+6)+(5+7)]

가 [eqn: rm lcm it = 210]으로 가장 크게 됨을 알 수 있었다. 여기에 방향 변환 상태에서 늘릴 수 있는 [eqn: 6]배를 늘려 주면, 임의의 이동에 대해서 [eqn: M^{k}=I]인 [eqn: 210 cdot 6 = 1,260] 이하의 자연수 [eqn: k]가 존재한다고 할 수 있다.

실제로 이동 회귀 수가 [eqn: 1,260]인 이동을 찾는 것은 해당하는 다섯 가지의 경우가 되도록 조정하면 쉽게 찾을 수 있다. 하지만 돌리는 횟수가 적을수록 좋으므로, 이동 회귀 수가 [eqn: 1,260]인 이동 중 돌리는 횟수가 가장 적은 것을 찾아보자.

돌리는 횟수를 단순히 [eqn: c(M)]으로 정의하면, 같은 회전을 [eqn: 2]회 이상 연속으로 돌리는 경우가 문제가 된다. 실제로 큐브를 돌릴 때 편의만 따지자면 [eqn: R^{2}]나 [eqn: R^{3}]는 [eqn: R]과 사실상 같다. 그런데 [eqn: c(R)=1], [eqn: c(R^{2})=2], [eqn: c(R^{3})=3]이고, 이동 회귀수가 [eqn: 6]인 [eqn: M=RUR^{3}U^{3}]는 [eqn: c(M)=8]이 된다. 따라서 단순히 [eqn: c(M)]을 지표로 삼는 것은 문제가 된다.

이동 [eqn: M]이 회전 [eqn: T_{1}], [eqn: T_{2}], [eqn: cdots], [eqn: T_{u(M)}]에 대해 [eqn: M=T_{1}T_{2}cdotsT_{u(M)]일 때, 실제 회전수를 [eqn: u_{r}(M)]이라 쓰고

[eqn: u_{r}(M):= u(M)-{sum_{k=2}^{u(M)}delta_{T_{k-1}T_{k}}]

으로 정의한다. 마찬가지로 실제 최소 회전수를 [eqn: left{u_{r}(X) : X=M right}]의 최솟값으로 정의하고 [eqn: c_{r}(M)]으로 쓴다. 임의의 회전 [eqn: T]에 대해 [eqn: u(T)=1]인 점에 주목하여 실제 회전을 [eqn: u_{r}(M)=1]인 이동 [eqn: M]으로 정의한다. 실제 회전은 회전 [eqn: T]에 대해 [eqn: T^{k}]([eqn: k=1,2,3])들이며 총 [eqn: 18]개다.

[eqn: delta]는 Kronecker delta이다.

[eqn: a>b]인 경우 [eqn: sum_{n=a}^{b}f(n):=0]으로 정의한다.

이동 회귀 수가 [eqn: 1,260]인 이동 [eqn: M] 중 [eqn: c_{r}(M)]이 가장 작은 이동은 프로그래밍으로 찾아본 결과 총 [eqn: 400]개다. (3) (4) breadth-first search를 통해 모든 이동을 조사했으며, 실행 시간이 오래 걸리므로 실행 결과까지 첨부하였다. [eqn: c_{r}(M)]은 제시된 것과 일치하지 않을 수 있으나 [eqn: u_{r}(M)]은 제시된 것과 일치한다. [eqn: u_{r}(M)=5]인 경우는 이동 회귀 수가 [eqn: 1,260]이면서 [eqn: u_{r}(M)<5]인 이동 [eqn: M]이 없었으므로 [eqn: c_{r}(M)=5]라고 생각해도 좋을 것이다. [eqn: u_{r}(M)=5]인 것은 cycle decomposition 결과 모두 [eqn: (3+5)+(1+2+2+7)] 꼴이다. [eqn: u_{r}(M)]이 두 번째로 작은 이동은 [eqn: u_{r}(M)=6]에 있었으며, 총 [eqn: 2,336]개다. [eqn: u_{r}(M)=6]인 것도 모두 [eqn: (3+5)+(1+2+2+7)] 꼴이다.

2.3 회전 제약

제약(restriction)은 큐브의 특정 회전 혹은 이동만을 가능케 하는 것을 의미한다. 이중 회전 제약(turn restriction)은 큐브의 특정 회전만을 가능케 하는 것을 의미하며, 회전 제약에서는 회전이 가능해지면 회전으로 이루어진 이동에는 제약이 없다. 루빅스 큐브에는 제약이 없지만, 적절한 회전 제약은 큐브를 맞추는 알고리즘의 각 단계를 구성하는 데 도움을 준다. 큐브의 회전은 [eqn: 6]가지이므로, [eqn: 6]가지의 회전에 모두 회전 제약을 할 수 있다.

회전 제약은 두 가지로 나뉜다. 완전 회전 제약(complete turn restriction)은 이동의 특정 회전을 아예 포함하지 않게 하는 것이고, 불완전 회전 제약(incomplete turn restriction)은 특정 회전 [eqn: T]에 대해 [eqn: T^{2}]만을 이동에 허용하는 것이다. 이를 통해 제약을 두 가지로 분류할 수 있는데, 어떤 제약의 어떤 회전도 완전 회전 제약이거나 제약이 되어 있지 않은 경우 이를 완전 제약(complete restriction)이라 하고, 그렇지 않은 경우 불완전 제약(incomplete restriction)이라 한다. (5) 완전 제약과 불완전 제약의 [eqn: 55]가지가 모두 나와 있다.

큐브에서 불완전 제약의 수는 총 [eqn: 47]가지이다. 이 경우는 그 수가 많고 본질적으로 비슷한 회전이 제약되는 완전 제약과 비슷한 성질을 지니므로, 이 절에서는 완전 제약에 집중한다.

2.3.1 완전 제약

큐브의 완전 제약에는 총 [eqn: 8]가지가 있다. 이름은 포함되는 면의 개수와 그 면의 위치 관계를 이용해 붙여졌다. 그림 7은 왼쪽 위부터 순서대로 1면, 2-비대면(2-nonfacing), 2-대면(2-facing), 3-비대면(3-nonfacing), 3-대면(3-facing), 4-홑대면(4-monofacing), 4-쌍대면(4-bifacing), 5면의 [eqn: 8]개 완전 회전 제약에서, 제약되지 않는 면의 관계를 표시해 놓은 것이다. 각 제약의 특징을 통해 이동으로 접근 가능한 상태의 개수를 찾아내는 것이 목표이다.

그림 7. 제약되는 면을 굵은 선으로 표시하였다.

1면 제약의 경우 가능한 모든 이동은 [eqn: I], [eqn: T], [eqn: T^{2}], [eqn: T^{3}]의 [eqn: 4]가지이다. 2-대면 제약의 경우 가능한 모든 이동은 [eqn: T_{1}^{k}T_{2}^{l}]([eqn: k=0,1,2,3], [eqn: l=0,1,2,3])으로 나타낼 수 있으며 총 [eqn: 16]가지이다. 이 두 제약은 두 개 이상의 회전이 걸치는 조각이 없는 회전 제약이다.

3-비대면 제약과 4-홑대면 제약은 그 성질이 서로 비슷하다. 편의상 3-비대면 제약의 회전이 가능한 면을 [eqn: U], [eqn: R], [eqn: F]라 하고 4-홑대면 제약은 여기에 [eqn: L]이 추가되었다고 하자.

정리 11. 정리 8의 [eqn: C_{2}], [eqn: E_{2}], [eqn: X_{4}]는 3-비대면 제약에서 존재한다.

증명. [eqn: C_{2}=RFR^{3}UR^{2}U^{3}F^{3}R^{2}FR^{3}URU^{3}R^{2}F^{3}],

[eqn: E_{2}=RFRUR^{3}F^{3}R^{3}FU^{3}F^{2}U^{2}FU^{3}F^{3}U^{3}F],

[eqn: X_{4}=RU^{2}F^{3}R^{3}FU^{3}F^{3}RFU^{3}R^{3}U^{3}].

정리 11에 의해 3-비대면 제약과 4-홑대면 제약에서 이동이 가능한 조각은 정리 5, 정리 6, 정리 7을 지키면서 마음대로 원하는 위치에 놓을 수 있음을 알 수 있다. 따라서 3-비대면 제약에서 가능한 경우의 수는 [eqn: {7! cdot 9! cdot 3^{7} cdot 2^{9}} over {2 cdot 3 cdot 2} = 170,659,735,142,400]가지이며, 4-홑대면 제약에서 가능한 경우의 수는 [eqn: {8! cdot 11! cdot 3^{8} cdot 2^{11}} over {2 cdot 3 cdot 2} = 1,802,166,803,103,744,000]가지이다.

3-대면 제약과 4-쌍대면 제약도 그 성질이 서로 비슷하다. 편의상 3-대면 제약의 회전이 가능한 면을 [eqn: U], [eqn: F], [eqn: B]라 하고 4-쌍대면 제약은 여기에 [eqn: D]가 추가되었다고 하자.

정리 12. 정리 8의 [eqn: C_{2}], [eqn: X_{4}]는 3-대면 제약에서 존재하나 [eqn: E_{2}]는 3-대면 제약, 4-쌍대면 제약 모두에서 존재하지 않는다.

증명. [eqn: C_{2}], [eqn: X_{4}]는 정리 8에 나타나 있다. 임의의 회전 [eqn: T]에 대해 범함수 [eqn: T]는 모서리 조각의 위치 변환 함수 [eqn: f] s. t. [eqn: f(x)=0````FORALL x `in` ℤ_{8}+1]를 [eqn: f]로 보내므로, 모서리는 항상 한 가지 방향으로밖에 있을 수 없다.

정리 11에 의해 3-대면 제약과 4-쌍대면 제약에서 이동이 가능한 귀퉁이 조각은 정리 5, 정리 7을 지키면서 원하는 위치에 놓을 수 있지만, 모서리 조각은 정리 5를 지키면서 원하는 위치에 지정된 방향으로 놓아야 함을 알 수 있다. 따라서 3-대면 제약에서 가능한 경우의 수는 [eqn: {8! CDOT 10! CDOT 3 ^{8}} over {2 CDOT 3} =159,993,501,696,000]가지이며, 4-쌍대면 제약에서 가능한 경우의 수는 [eqn: {8! CDOT 12! CDOT 3 ^{8}} over {2 CDOT 3} =21,119,142,223,872,000]가지이다.

3-대면 제약과 4-쌍대면 제약에서 모서리 조각은 반드시 정해진 방향대로 들어가므로, 정리 6에서 그 경우의 수가 반이 되지 않는다.

5면 제약은 다음 정리에 의해 제약이 없는 경우와 같은 [eqn: 43,252,003,274,489,856,000]가지임을 알 수 있다.

정리 13. [eqn: U], [eqn: D], [eqn: L], [eqn: R], [eqn: F]만으로 이동 [eqn: B]를 만들 수 있다.

증명. [eqn: B=RLU ^{2} D ^{2} R ^{3} L ^{3} FRLU ^{2} D ^{2} R ^{3} L ^{3}].

2-비대면 제약은 귀퉁이 조각에 걸린 제약이 까다롭다. 이를 분석하기 위해서 조각과 관련된 일부를 재정의한다. 그림 8은 모서리 조각의 방향 변환 상태, 그림 9는 귀퉁이 조각의 위치 변환 상태와 관련된 번호이다. 그림 8과 같이 재정의하면 [eqn: R] 혹은 [eqn: U] 시 한 조각의 같은 면이 같은 숫자를 가리키게 되므로 모서리 조각은 항상 한 방향으로 유지된다.

그림 8		그림 9

정리 14. 2-비대면 제약에서 모서리 조각의 이동이 자유로우며, 다음 조건

이전에 이런 증명이 필요 없었던 이유는 각각의 회전이 그 회전만의 영향을 받는 귀퉁이 조각이나 모서리 조각을 가졌기 때문이며, 귀퉁이 조각에 대해 그렇지 않았던 3-대면 제약에서는 정리 8의 [eqn: X_{4}]가 있었기 때문에 귀퉁이 조각이 자유로웠다.

모서리 조각의 위치 변환 상태 [eqn: f], [eqn: g]에 대해 [eqn: E_{3}(f)=g]일 때,

[eqn: f(1)=g(2)], [eqn: f(2)=g(3)], [eqn: f(3)=g(1)]

을 만족하는 이동 [eqn: E_{3}]와 정리 8의 [eqn: C_{2}]가 존재한다. 단, 주어지지 않은 조각이나 함수는 [eqn: I]와 그 상태가 같다.

증명. 첫 번째 것은 [eqn: x,y,z`in`left{1,2,3,4,7,8,11right}]인 서로 다른 [eqn: x], [eqn: y], [eqn: z]에 대해 다음 조건

모서리 조각의 위치 변환 상태 [eqn: f], [eqn: g]에 대해 [eqn: M(f)=g]일 때,

[eqn: g(1)=x], [eqn: g(2)=y], [eqn: g(3)=z]

을 만족하는 이동 [eqn: M]이 존재함을 보이면 된다. 표 5의 이동을 참고하면, 그 방법이 존재함을 알 수 있다. 반드시 [eqn: x], [eqn: y], [eqn: z] 순으로 시행해야 이동이 만들어진다.

[eqn: ME_{3}M^{-1}]가 임의의 세 모서리 조각의 3-cycle이기 때문이다. 이동 [eqn: M_{1}]과 [eqn: M_{2}]에 대해 [eqn: M_{1}M_{2}M_{1}^{-1}] 꼴의 이동을 conjugation이라고 하고, 이때 [eqn: M_{1}]을 set-up move라고 한다.

위치	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 7]	[eqn: 8]	[eqn: 11]
[eqn: x]	[eqn: I]	[eqn: U^{3}]	[eqn: U^{2}]	[eqn: U]	[eqn: R^{3}U^{2}]	[eqn: RU^{2}]	[eqn: R^{2}U^{2}]
[eqn: y]		[eqn: I]	[eqn: R^{3}URU^{3}]	[eqn: (U^{2}R^{2})^{3}]	[eqn: UR^{3}U^{3}]	[eqn: URU^{3}]	[eqn: UR^{2}U^{3}]
[eqn: z]			[eqn: I]	[eqn: U^{3}R^{3}UR]	[eqn: R^{3}]	[eqn: R]	[eqn: R^{2}]
표 5. [eqn: x], [eqn: y], [eqn: z]가 될 조각이 위치 [eqn: c]에 있을 때 이동을 시행하면 제자리를 찾는다.

이제 [eqn: E_{3}=R^{3}UR^{3}U^{3}R^{3}U^{3}R^{3}URUR^{2}], [eqn: C_{2}=U^{2}RUR^{3}URU^{2}R^{3}U^{2}R^{3}U^{3}RU^{3}R^{3}U^{2}R]이므로 정리가 증명된다.

이상의 사실을 종합하면 2-비대면 제약에서는 귀퉁이 조각의 방향은 자유로우며, 모서리 조각의 위치는 자유롭고 방향은 반드시 한 방향으로 정해져 있다는 것을 알았다. 귀퉁이 조각의 위치에 대해 알아보기 위해서 새로운 용어를 정의한다.

이제 귀퉁이 조각의 위치 변환 상태는 정의역과 치역이 [eqn: ℤ_{6} + 1]이다. 회전 [eqn: T]와 귀퉁이 조각의 위치 변환 상태 [eqn: f]에 대해 귀퉁이 조각의 위치 변환 상태 [eqn: g]가 존재하여 [eqn: T(f)=g]일 때

[eqn: 3- sum _{n=1} ^{6}{`sum_{j=4}^{6} LEFT (delta_{f(n)j}` delta _{f(n)g(n)} RIGHT )}]

을 [eqn: T]의 component라고 하고, [eqn: rm comp it `(f,T)] 혹은 [eqn: I]로부터 귀퉁이 조각의 위치 변환 상태 [eqn: f]를 생성하는 이동 [eqn: M]에 대해 [eqn: rm comp it `(M, T)]로 쓴다. 자연수 [eqn: n `in `ℤ_{3}+1], 이동 [eqn: M]과 회전 [eqn: T_{1}], [eqn: T_{2}], [eqn: cdots], [eqn: T_{u(M)}]에 대해 [eqn: M = T_{1}T_{2}cdotsT_{u(M)}]일 때

[eqn: sum_{k=1}^{u(M)}delta_{rm comp it `(T_{1}cdotsT_{k-1}, T_{k})n]

를 이동 [eqn: M]의 [eqn: bold n it]-count라고 하고, [eqn: n]-count [eqn: c_{n}]에 대해 [eqn: exp (c_{n} pi i)]를 [eqn: bold n]-value라고 하며, [eqn: n=2]인 경우 특히 [eqn: bold 2]-determinant라고 한다. 또 이동 [eqn: M]에 대해 [eqn: M]이 [eqn: I]로부터 생성한 귀퉁이 조각의 위치 변환 상태를 [eqn: f]라 할 때 다음 diagram

여기서 [eqn: i=sqrt{-1}]이다.

[eqn: p_{1}p_{2}p_{3}p_{4}p_{5}p_{6}] s. t. [eqn: p_{n}= cases{□ ````& delta_{f(n)1}+delta_{f(n)2}+delta_{f(n)3}=1# ■& rm else it }]

을 status diagram이라 한다. [eqn: I]의 status diagram은 □□□■■■이고, [eqn: U^{2}RU]의 경우에는 ■□■□■□이다. 여기서 status diagram의 [eqn: bold i it]번([eqn: i=1,2,3,4,5,6])을 [eqn: p_{i}]로 정의한다.

이동 [eqn: M]과 회전 [eqn: T`in`left{ R, U right}]에 대해 [eqn: rm comp it `(M,T)=2]일 때, [eqn: M]과 [eqn: MT^{2}]의 status diagram이 같으면 [eqn: M]은 [eqn: T]에 대해 떨어진 상태라고 하고, 다르면 붙은 상태라고 한다. 또 status diagram이 □□□■■■인 이동을 모은 집합을 [eqn: I_{6}]라 이름 붙이자. 우리는 [eqn: I_{6}] 집합의 성질을 주목해서 볼 것이다.

정리 15. [eqn: M`in`I_{6}]의 [eqn: n]-value [eqn: v_{n}]에 대해 [eqn: v_{1}v_{3}=1]이다.

증명. [eqn: n]-count [eqn: c _{n}]을 생각하자. 홀수 번 위치의 조각이 회전되면 반드시 짝수 번 위치의 조각으로, 짝수 번 위치의 조각이 회전되면 반드시 홀수 번 위치로 들어가게 되므로, 이동 [eqn: M]의 총 귀퉁이 회전 횟수 [eqn: c_{1}+2c_{2}+3c_{3}]는 짝수이다. [eqn: 2(c_{2}+c_{3})]가 짝수이므로 [eqn: c_{1}+c_{3}]가 짝수가 된다. 따라서

[eqn: v_{1}v_{3}=exp(c_{1}pi i)exp(c_{3}pi i) = exp left((c_{1}+c_{3})pi i right)=1]

이다.

정리 16. [eqn: M `in `I_{6}]의 [eqn: 2]-determinant는 [eqn: 1]이다.

증명. 이동 [eqn: M]에 대해 [eqn: rm comp it `(M, U)=2]이고 [eqn: rm comp it` (M, R)neq 2]라고 하자. 그러면 [eqn: M]의 status diagram의 [eqn: 3]번과 [eqn: 4]번은 서로 같고, [eqn: 5]번과 [eqn: 6]번 중 하나만이 ■이다. 즉 [eqn: M]은 [eqn: U]에 대해 붙은 상태가 되고, [eqn: rm comp it `(M U, R)=2]이다. 따라서 [eqn: M U^{2}]와 [eqn: M UR]의 경우 모두 [eqn: 2]-determinant가 [eqn: M]과 같을 것이다. 이 문단의 증명에서 [eqn: U]를 [eqn: R]로, [eqn: 5]와 [eqn: 6]을 [eqn: 1]과 [eqn: 2]로 바꾸어 읽으면 비슷한 상황에서 [eqn: MR^{2}]과 [eqn: MRU]의 경우 모두 [eqn: 2]-determinant가 [eqn: M]과 같음을 알 수 있다.

이동 [eqn: M]이 [eqn: rm comp it `(M,U)=rm comp it `(M,R)=2]이고, [eqn: M]이 [eqn: U]나 [eqn: R] 모두에 대해 떨어진 상태라고 하자. 회전 [eqn: T]를 취하면 [eqn: rm comp it] 값은 [eqn: 2]로 유지된다. 다음 회전을 [eqn: T]로 취하면 역시 [eqn: M]과 [eqn: MT^{2}]는 [eqn: 2]-determinant가 같다. [eqn: MT]가 해당 회전의 co-회전에 대해 붙은 상태가 되므로, 다음 회전을 [eqn: T]의 co-회전 [eqn: T`']로 취하면 [eqn: rm comp it `(MTT`', T) neq 2]이면서, 역시 [eqn: M]과 [eqn: MTT`']의 [eqn: 2]-determinant가 같게 된다.

[eqn: U]이면 [eqn: R], [eqn: R]이면 [eqn: U].

이상의 경우에서 [eqn: rm comp it `(M, U)=2]이거나 [eqn: rm comp it `(M, R)=2]인 경우 [eqn: 2]-determinant를 바꾸는 회전은 항상 쌍으로 일어난다는 것을 알았다. 따라서 [eqn: rm comp it `(M, U)=3 neq 2]이면서 [eqn: rm comp it `(M, U)=1 neq 2]인 [eqn: M`in`I_{6}]의 경우, 그 [eqn: 2]-determinant 값은 [eqn: I]와 같은 [eqn: 1]이 된다.

정리 15와 정리 16에서, [eqn: M`in`I_{6}]인 이동 [eqn: M]의 [eqn: n]-value를 [eqn: v_{n}]이라 하면 [eqn: v_{1}v_{2}v_{3}=1]이다. 따라서 [eqn: n]-count [eqn: c_{n}]의 합이 짝수이다. 이동 [eqn: M]에 관련 없이 [eqn: T]의 component는 [eqn: ℤ_{3}+1]에 있으므로, 이 말은 [eqn: M]의 회전의 개수가 짝수라는 말이며, 따라서 [eqn: rm sgnp_{it c}it M=1]이다. 이 말은 2-비대면 제약에 정리 8의 [eqn: X_{4}]는 존재할 수 없다는 말이 된다. 마찬가지로 생각하면 2-비대면 제약에서는 [eqn: 3]개의 조각이 결정되면 나머지 조각의 위치는 자동으로 결정된다. 따라서 귀퉁이 조각의 위치만을 고려할 때 2-비대면 제약에서의 경우의 수는 [eqn: 6cdot5cdot 4=120] 이하이다.

2-비대면 제약에 [eqn: X_{4}]가 존재한다고 가정하자. set-up move로 [eqn: U^{2}]를 잡으면 [eqn: 1], [eqn: 2]번 코너 조각이 바뀐 이동이 나온다. 이는 [eqn: 4], [eqn: 5], [eqn: 6]번 조각이 제자리에 있으면서 귀퉁이 위치 부호가 [eqn: -1]이므로, 2-비대면 제약에서는 존재할 수 없는 이동이다. 따라서 [eqn: X_{4}]가 존재한다는 가정이 틀렸다.

정리 17. 2-비대면 제약에서 귀퉁이 조각의 위치의 가짓수는 [eqn: 120]이다.

증명. 임의의 세 조각을 [eqn: 4], [eqn: 5], [eqn: 6]번 위치에 결정할 수 있음을 보이면, 경우의 수가 [eqn: 120] 이상이 되어, 정리 16 이후의 논의를 합치면 원하는 결론이 나온다. 표 5와 비슷한 방식으로 표 7을 적용하면 세 조각을 마음대로 놓을 수 있게 된다.

위치	[eqn: 1]	[eqn: 2]	[eqn: 3]	[eqn: 4]	[eqn: 5]	[eqn: 6]
[eqn: 6]번 위치	[eqn: UR]	[eqn: U^{2}R]	[eqn: R]	[eqn: R^{2}]	[eqn: R^{3}]	[eqn: I]
[eqn: 5]번 위치	[eqn: RU^{3}R^{3}]	[eqn: RU^{2}R^{3}]	[eqn: U^{3}RU^{2}R^{3}]	[eqn: URU^{3}R^{3}]	[eqn: I]
[eqn: 4]번 위치	[eqn: U^{3}]	[eqn: U^{2}]	[eqn: U]	[eqn: I]
표 7. 각 위치의 조각을 해당 위치로 옮기기 위해 이동을 시행한다.

정리 16 이후의 논의와 정리 17에 의해 [eqn: I_{6}]의 원소의 개수는 [eqn: 6]개이므로 그 이름을 그렇게 붙였다. 이동 [eqn: M]이 [eqn: M=I]인 경우 [eqn: 2]-determinant는 항상 [eqn: 1]이지만, [eqn: 1]-value나 [eqn: 3]-value는 [eqn: 1] 또는 [eqn: -1]이다. 예를 들어, [eqn: left(RU^{3}R^{3}U^{3}right)^{5}]는 [eqn: I]와 다르게 [eqn: 1]-value와 [eqn: 3]-value가 [eqn: -1]이지만, 정리 16에 의해 [eqn: 2]-determinant는 [eqn: 1]임을 알 수 있다. 따라서 [eqn: 2]-value는 이동에만 의존한다는 특성 때문에 [eqn: 2]-determinant로 부를 수 있다. 총 [eqn: pmatrix{6#3}=20]개 중 [eqn: 2]-determinant가 [eqn: -1]인 것이 [eqn: 6]개이므로 [eqn: 120]개 중 [eqn: 120cdot {6 over 20}=36]개는 [eqn: 2]-determinant가 [eqn: -1]임을 알 수 있다.

이 논증이 가능한 이유는 status diagram이 [eqn: 2]-determinant를 결정하는 모든 정보를 담고 있기 때문이다. 정리 16이 그것을 증명한다.

2-비대면 제약에서의 모든 논의를 종합하자면, 귀퉁이 조각의 위치가 총 [eqn: 120]가지이고, 방향에는 제한이 없으며, 모서리 조각의 위치는 signum이 [eqn: 1]이 되게 놓으면 제한이 없고 방향은 정해진 방향에 따라 놓아야 한다. 따라서 2-비대면 제약에서 가능한 경우의 수는 [eqn: {120 CDOT 7! CDOT 3 ^{6} } over {2 CDOT 3} =73,483,200]가지이다.

2.3.2 불완전 제약

불완전 제약의 경우, 다음 정리로 비슷한 완전 제약을 통해 그 성질을 유추할 수 있다.

정리 18. 마주 보는 두 면에 불완전 제약을 하면 모서리 조각의 방향이 고정된다. 또 마주 보는 두 면을 제외한 네 면에 불완전 제약을 하면 귀퉁이 조각의 방향이 고정된다.

증명. 표 4에서 [eqn: L], [eqn: R]을 제약한 것, 표 3에서 [eqn: L], [eqn: R], [eqn: F], [eqn: B]를 제약한 것을 확인하면 충분하다.

3. 참고 문헌 및 첨부 자료

(1) Wikipedia (2015), “Combination Puzzle”, http://en.wikipedia.org/wiki/Combination_puzzle. (2015-06-23)

(2) 자료, “나누고 확인하기”, http://site.thekipa.com/2015/divide_and_check.cpp. (2015-09-24)

(3) 자료, “이동 회귀 수가 [eqn: 1,260]인 이동 찾기”, http://site.thekipa.com/2015/find_1260_move .cpp. (2015-09-24)

(4) 자료, “최대 이동 회귀 수 실행 결과”, http://site.thekipa.com/2015/find_1260_out put.txt. (2015-09-24)

(5) Lehrstuhl D für Mathematik (1992), “Re: subgroups”, http://www.math.rwth-aachen.de/ ~Martin.Schoenert/Cube-Lovers/michael_reid__Re__subgroups.html. (2015-08-21)