루빅스 큐브의 상태 수를 세어 보자

루빅스 큐브(Rubik's Cube)는 에르뇌 루빅이 1974년에 발명한 정육면체 형태의 물리 퍼즐이다. 형태를 놓고 보면 3×3×3으로 나누어진 정육면체이며, 한가운데 숨어서 아무것도 하지 않는 조각을 제외하면 26개의 조각으로 이루어져 있다. 각 면에 하나의 색이 대응되어 있어서 하나의 면이 하나의 색으로 색칠되어 있다. 한 면을 골라 그 면과 닿아 있는 9개의 조각을 잡고 90°씩 돌릴 수 있게 되어 있다. 몇 번만 돌리다 보면 처음 상태를 알아볼 수 없을 정도로 섞이게 되며, 퍼즐의 목표는 그렇게 섞인 큐브를 원래대로 되돌리는 것이다.

그렇다면 생기는 궁금증이 있다. 이 큐브를 이리저리 돌려서 만들 수 있는 총 상태의 수는 몇 개일까? 사실 간단하게 구글링을 하면 답이 바로 나오긴 하는데, 왜 그런 경우의 수가 나오는지 정확하고 엄밀하게 설명하는 자료는 놀라울 정도로 찾아보기 힘들다! 그래서 여기서 최대한 엄밀한 과정을 통해 루빅스 큐브의 상태 수를 계산해 보고자 한다. 때문에, 글이 꽤나 길어질 수밖에 없음을 미리 알린다. 그게 이 사이트에서 가장 긴 글이 될 줄은 필자도 몰랐다.

이 글은 독자가 순열의 홀짝성(parity of permutation)에 대해 알고 있다는 가정 하에 쓰여져 있다. 해당 개념에 대해 알고 있지 않다면 이 글을 먼저 읽고 오자.

일단 규칙부터!

계산하기 전에, 정확히 무엇을 구하고 있는 것인지 정리하고 가자.

• 3×3×3 큐브를 돌려서 나올 수 있는 경우의 수를 셀 거다.
• 큐브 전체를 회전시켜서 같은 경우는 똑같이 센다. 즉, 다른 각도에서 본 같은 상태를 여러 번씩 세지 않는다.
• 한 면을 골라 그 면을 90°의 배수만큼 회전하는 것만 허용한다. 특히 코너 트위스팅은 허용하지 않는다. 조각을 다시 색칠하거나 조각을 뽑는 것도 당연히 허용하지 않는다.
  • 다시 말해, 허용되는 것은 다음밖에 없다. R, R', R2, U, U', U2, F, F', F2, L, L', L2, D, D', D2, B, B', B2.
  • 다만, R2는 R을 두 번 하는 것으로, R'은 R을 세 번 하는 것으로 생각할 수 있기 때문에 R, U, F, L, D, B만 허용된다고 보아도 충분하다.

용어

설명이 간결해지기 위해서는 몇 가지 용어를 정의해야 한다.

• 센터 조각(center piece): 각 면의 중심에 있는 조각. 1개의 색으로 이루어져 있으며 총 6개가 있다.
• 엣지 조각(edge piece): 각 면의 중점에 위치한 조각. 2개의 색으로 이루어져 있으며 총 12개가 있다.
• 코너 조각(corner piece): 각 꼭짓점에 위치한 조각. 3개의 색으로 이루어져 있으며 총 8개가 있다.
• \(n\)-순열: 집합 \(\{1, 2, \cdots, n\}\) 상에서의 순열
• 이 글에서는 순열을 표기하기 위해 cycle notation을 사용한다.
• \(c\)-사이클: \(c\)개의 원소가 순환적으로 위치를 바꾸는 순열, 즉 cycle notation 상으로 \((a_1 \ a_2 \ \cdots \ a_n ) \) 꼴의 순열
• 전치: 2-사이클, 즉 \((a \ b)\) 꼴의 순열

단순하게 세기

루빅스 큐브의 아주 유용한 성질이 있는데, 바로 센터 조각은 절대 위치가 변하지 않는다는 것이다. 물론 큐브 자체를 돌려 버리면 위치가 바뀌긴 하겠다만, 어차피 우리는 큐브 전체의 회전을 무시하고 있기 때문에 센터 조각들의 위치를 고정하는 것은 경우의 수를 세는 데 큰 도움이 된다.

그러면 이제 위치가 고정된 센터 조각을 제외한 나머지 조각들을 배치하는 경우의 수를 세어 보자. 엣지 조각이 코너 조각에 가거나 코너 조각이 엣지 조각에 가지는 않으므로 다음과 같이 간단하게 계산할 수 있다.

• 엣지 조각 12개를 배열하는 경우의 수: \(12! = 479,001,600\)
• 코너 조각 8개를 배열하는 경우의 수: \(8! = 40,320\)
• 엣지와 코너 조각들의 위치를 결정하는 경우의 수: \(12! \times 8! = 19,313,344,512,000\)

단 이게 끝이 아니다. 조각 하나의 위치가 결정되어도 그 조각이 큐브에 들어가는 방법이 유일하게 결정되지 않는데, 조각을 어떤 방향으로 넣는지 결정해 주어야 하기 때문이다. 엣지 조각 하나를 특정 위치에 넣는 방법은 2가지, 코너 조각 하나를 특정 위치에 넣는 방법은 3가지가 있으므로,

• 엣지 조각 12개의 방향을 결정하는 경우의 수: \(2^{12} = 4,096\)
• 코너 조각 8개의 방향을 결정하는 경우의 수: \(3^8 = 6,561\)
• 엣지와 코너 조각들의 방향을 결정하는 경우의 수: \(2^{12} \times 3^8 = 26,873,856\)

따라서, 조각들의 위치와 방향을 결정하는 경우의 수는 \(12! \times 8! \times 2^{12} \times 3^8 = 519,024,039,293,878,272,000\)이다.

여기서 끝났다면 참 좋았겠지만, 그렇게 쉬웠다면 이 글이 써질 이유가 없을 것이다.

왜 안돼요?

방금 센 것은 엣지와 코너 조각의 위치와 방향을 아무렇게나 결정하는 방법의 수다. 그렇게 아무렇게나 만든 상태를 실제로 큐브의 회전만으로 만들 수 있다는 보장은 없다.

간단한(?) 반례 하나로, 주변에 큐브가 있다면 그 큐브를 들고 코너 조각 하나의 방향을 바꾸려고 시도해 보자. 다른 조각들의 위치와 방향은 그대로여야 한다. 코너 트위스팅을 사용하지 않고서는 불가능하다는 것을 알 수 있다.

따라서 우리가 구하고 있는 실제 경우의 수는 위에서 구한 수보다 작다.

조각의 위치

엣지 조각 12개에 1부터 12까지의 번호를 아무 순서대로나 붙이고, 마찬가지로 코너 조각 8개에도 1부터 8까지의 번호를 아무 순서대로나 붙이자. 이제 조각의 위치는 두 개의 순열로 표현할 수 있다. 엣지 조각의 위치를 표현하는 12-순열 \(E\)와 코너 조각의 위치를 표현하는 8-순열 \(C\)의 순서쌍 \((E,C)\)는 큐브의 조각 위치 상태와 일대일 대응된다.

한 면을 돌릴 때마다 조각 위치에 어떤 일이 일어나는지 관찰해 보자. 엣지 조각 4개가 길의 4의 사이클을 이루며 위치가 변하고, 코너 조각 4개에도 같은 일이 일어난다. 즉, \(E\)와 \(C\) 각각에 4-사이클이 합성된다.

이때, 4-사이클 \( (a_1 \ a_2 \ a_3 \ a_4 ) \)는 다음과 같이 홀순열임을 알 수 있다.

\( (a_1 \ a_2 \ a_3 \ a_4 ) = (a_1 \ a_4) \circ (a_1 \ a_3) \circ (a_1 \ a_2)\)

그러므로, 한 회전을 할 때마다 \(E\)와 \(C\) 각각의 홀짝성이 바뀐다. \(E\)와 \(C\)는 시작 상태에서 모두 짝순열이므로(모든 조각이 제자리에 있기 때문에 둘 다 \(\text{id}\)이다), \(E\)와 \(C\)의 홀짝성은 항상 같다.

12와 8는 모두 1보다 크기 때문에, 12-순열과 8-순열 중 각각 정확히 절반씩이 짝순열, 절반씩이 홀순열이다. 따라서 \(12! \times 8!\)개의 \((E, C)\) 순서쌍 중 절반만이 실제로 가능하다는 것을 알 수 있다!

그렇다면 홀짝성이 같은 순열의 순서쌍으로 이루어진 \((12!\times 8!)/2\)개의 순서쌍은 모두 실제로 가능할까? 이를 위해서는 다음을 증명하면 충분하다.

• 임의의 엣지 조각 두 개와 코너 조각 두 개를 고르면, 선택된 엣지 조각 두 개의 위치와 코너 조각 두 개의 위치를 바꾸면서 나머지 조각들의 위치는 건드리지 않는 방법이 존재한다.

만약 위의 사실을 증명할 수 있다면, 우리는 다음과 같이 원하는 순서쌍 \((E, C)\)를 만들 수 있다.

1. \(E\)와 \(C\)를 각각 전치들의 합성으로 분해한다. 둘의 홀짝성이 같으므로, 각각의 분해는 길이가 같거나 차이가 짝수이다.
2. 만약 둘의 길이가 다르다면, 짧은 쪽에 \((1 \ 2)\)를 반복해서 덧붙여서 길이를 같게 만든다. 붙여야 하는 개수는 짝수 개이고 \((1 \ 2) \)를 짝수 번 합성하면 항등원이 되므로, 이렇게 덧붙여도 \(E\)와 \(C\)는 변하지 않는다.
3. 그 결과를 \(E = E_k \circ \cdots \circ E_2 \circ E_1\), \(C = C_k \circ \cdots \circ C_2 \circ C_1\)이라 하자.
4. 위에서 존재성을 증명한 방법을 이용해서, \(E_1\)과 \(C_1\)을 동시 실행한다. 그 다음에 \(E_2\)와 \(C_2\)를 동시 실행한다. 이를 \(E_k\)와 \(C_k\)를 동시 실행할 때까지 반복한다. 완성!

이제 위의 사실을 증명해 보자. 다음과 같은 방법을 쓰면 된다.

1. 바꾸고 싶은 엣지 조각들을 적당한 회전을 통해 윗면의 오른쪽과 왼쪽에서 마주보게 만든다.
2. 바꾸고 싶은 첫 번째 코너 조각을 적당한 회전을 통해 윗면의 오른쪽 앞 꼭짓점으로 옮긴다. 이때 엣지 조각들의 위치를 건드리지 않게 주의한다. R이나 L을 해야 할 때마다 U R U', U L U'를 대신 실행하면 된다.
3. 바꾸고 싶은 두 번째 코너 조각을 적당한 회전을 통해 윗면의 오른쪽 뒤 꼭짓점으로 옮긴다. 이때 맞추어 놓은 세 조각들의 위치를 건드리지 않게 주의한다. R 대신 U R U', L 대신 U'LU, F 대신 U2 F U2를 실행하자. 단, 이미 그 조각이 윗면의 왼쪽 앞 구석에 있는 경우에는 그렇게 간단하게 옮기기 어렵다. 이때는 L D L'을 통해 그 조각을 다른 곳으로 빼낸 뒤 시작하자.
4. R U R' U' R' F R2 U' R' U' R U R' F'를 실행한다. ^[출처]
5. 3단계에서 한 회전들을 거꾸로 해서 되돌린다.
6. 2단계에서 한 회전들을 거꾸로 해서 되돌린다.
7. 1단계에서 한 회전들을 거꾸로 해서 되돌린다.

4단계에서 윗면의 오른쪽과 왼쪽 엣지 조각의 위치 및 오른쪽 앞과 뒤 코너 조각의 위치가 바뀌는 것을 확인할 수 있다. 이 상태에서 5, 6, 7단계를 시행하면 1, 2, 3단계가 다른 조각들에게는 모두 없던 일이 됨과 동시에, 4단계에서 바뀐 조각들이 서로의 위치로 이동하게 된다.

이로서, \(E\)와 \(C\)의 홀짝성이 같기만 하다면 순서쌍 \((E, C)\)는 항상 실제로 가능하다는 사실이 증명되었다! 따라서 큐브의 조각들의 위치를 결정하는 방법의 수는 다음과 같다.

\(\dfrac{12!\times 8!}{2} = 9,656,672,256,000 \)

엣지 조각의 방향

지금부터는 일단 조각들의 위치는 결정되었다고 생각하고, 이제부터 우리가 할 수 있는 건 조각의 위치를 바꾸지 않으면서 방향만 바꾸는 것뿐이라고 생각하도록 하자. 이래야 조각의 방향을 결정하는 것이 조각의 위치를 결정하는 것에 간섭하지 않음을 확실히 할 수 있다.

엣지 조각의 방향을 잘 정의하기 위해 다음과 같은 상황을 상상하자.

• 모든 엣지 조각은 두 개의 면으로 이루어져 있다. 이 면 중 하나에 0을 쓰고, 다른 하나에는 1을 쓴다.
• 큐브를 감싸고 있는 가상의 '투명 큐브 껍질'이 있다고 생각해 보자. 이 껍질은 큐브를 감싸기만 하고, 우리가 회전을 시킴에 따라 같이 돌아가지 않는 고정된 껍질이다.
• (큐브가 맞추어져 있는) 처음 상태에서, 연필을 들고 그 투명 껍질에 숫자를 쓴다고 상상하자. 이미 엣지 조각에 쓰여 있는 숫자와 겹쳐 보이도록 숫자를 쓴다.

이렇게 하고 나면, 우리가 큐브를 돌림에 따라 다음과 같은 일이 일어날 것이다.

• 엣지 조각은 항상 엣지 조각의 위치로만 이동한다. 따라서, 열심히 돌리고 난 뒤 한 엣지 조각에 주목하면 그 엣지 조각에는 0과 1이 써 있고, 그 엣지 조각 바로 위에 있는 껍질 부분에도 0과 1이 써 있다.
• 이때 조각과 껍질에 써 있는 숫자가 일치할 수도 있고, 일치하지 않을 수도 (즉, 0 위치에 1이 써 있고 1 위치에 0이 써 있을 수도) 있다.
• 껍질과 일치하는 숫자가 써 있는 조각을 '방향이 맞는' 엣지 조각이라고 부르자. 일치하지 않는 숫자가 써 있는 조각은 '방향이 맞지 않는' 엣지 조각이라고 부르자.

자, 이제 회전을 한 번 시키면 방향이 맞지 않는 엣지 조각의 수에는 어떤 변화가 생길까? 편의를 위해 윗면을 시계 방향으로 회전시키고 있다고 생각하자(즉, U를 하고 있다). 다른 회전의 경우도 그냥 다른 방향에서 보면 똑같다. 돌아가고 있는 윗면을 바로 위에서 관찰하면,

• 엣지 조각 4개가 한 면씩 보인다. 각 조각에는 0 또는 1이 써 있다. (즉, 실제로는 조각 하나에 숫자가 두 개 써 있지만 다른 하나는 옆면에 있기 때문에 보이지 않는다)
• 껍질의 윗면이 보인다. 그 윗면에도 숫자 4개가 써 있으며, 그 4개 역시 각각 0 또는 1이다. 조각에 써 있는 숫자 하나가 껍질에 써 있는 숫자 하나씩과 겹쳐 보인다.
• 이때 우리는 다음을 알 수 있다. 만약 어떤 엣지 조각에 써 있는 숫자 두 개 중 보이는 것을 \(a\)라 하고 해당 위치에 있는 껍질의 숫자를 \(b\)라고 할 때, \(a=b\)라면 그 엣지 조각은 방향이 맞는 조각이다. 반대로 \(a \neq b\)라면 그 조각은 방향이 맞지 않는 조각이다.
• 여기서 \(a\)와 \(b\)는 각각 0 또는 1이라는 사실에 주목하면, \(a=b\)와 "\(a+b=0\) 또는 \(a+b=2\)"가 필요충분조건이고, \(a \neq b\)와 \(a+b=1\)이 필요충분조건이다.
• 다시 말해 특정 조각이 방향이 맞지 않는다는 것은 \(a+b\)가 홀수인 것과 필요충분조건이다!

위에서 정의한 \(a\)와 \(b\)에 대해, \(a+b\)의 값이 매우 중요함을 알 수 있다. 그 \(a+b\)의 값을 우리가 주목 중인 4개의 조각에 대해 모두 더한 값을 \(S\)라 하자. 조금만 생각해 보면, \(S\)는 그냥 현재 보이는 모든 8개의 수의 합과 같다.

\(a+b\)의 값이 홀수인 것과 그 조각의 방향이 맞지 않는 것이 필요충분조건이므로, \(S\)의 홀짝성은 우리가 보고 있는 4개의 조각 중 방향이 맞지 않는 것의 개수의 홀짝성과 같다. 그런데 \(S\)는 현재 보이는 8개의 수의 합이고, 그 수들은 큐브를 돌릴 때 위치만 바뀌지 수가 사라지거나 새로 생기거나 값이 바뀌지 않으므로, \(S\)의 값은 회전을 해도 변하지 않는다!

따라서 우리는 다음 결론을 얻는다. 방향이 맞지 않는 조각의 개수의 홀짝성은 절대 변하지 않는다. 또한, 처음에 방향이 맞지 않는 조각 개수는 0개로 짝수이므로, 방향이 맞지 않는 조각 개수는 항상 짝수라는 것을 알 수 있다.

그러므로 엣지 조각의 방향을 결정하는 \(2^{12}\)개의 방법 중 실제로 가능한 것은 그 중 절반뿐이다. 11개의 조각의 방향을 결정하고 나면 나머지 하나의 방향은 방향이 맞지 않는 조각 개수의 홀짝성 때문에 자동 결정되기 때문이다.

물론, 위에서 조각들의 위치를 가지고 했던 것과 마찬가지로 방향이 맞지 않는 조각의 홀짝성만 맞는다면 모든 방향 조합이 실제로 가능한지를 증명해야 한다. 이를 위해서는 다음을 증명하면 충분하다.

• 임의의 두 엣지 조각에 대해, 그 두 조각을 각각 뒤집고, 그들의 위치 및 나머지 조각들의 위치나 방향은 건드리지 않는 방법이 존재한다.

만약 위 사실을 증명했다면, 우리는 다음 과정을 통해 임의의 원하는 엣지 조각 방향 조합을 얻을 수 있다(물론 홀짝성이 맞는다면).

1. 아무 엣지 조각 \(e\)를 고른다.
2. 나머지 11개의 엣지 조각 각각에 대해 다음을 실행한다. 만약 해당 조각의 방향이 이미 우리가 원하는 대로라면 넘어간다. 만약 그렇지 않다면, 위 사실로부터 존재성을 알 수 있는 방법을 통해 해당 조각과 \(e\)의 방향을 동시에 바꾼다.
3. 그러고 나면, 홀짝성 조건 때문에 \(e\)의 방향은 자동으로 우리가 원하는 것과 같아야 한다. 한 번에 짝수 개의 엣지 조각이 방향이 바뀌니까.

이제 위 사실을 증명해 보자. 아이디어는 위에서 조각 위치에 대해 했던 것과 비슷하다. 다음 방법을 통해 원하는 두 개의 엣지 조각 방향을 뒤집을 수 있다.

1. 적당한 회전을 통해 뒤집고 싶은 두 개의 엣지를 윗면의 오른쪽과 앞쪽 모서리에 배치한다.
2. F U2 F2 D' U' L' U L D F2 U' F' U를 실행한다. ^[출처]
3. 1단계에서 했던 회전을 모두 거꾸로 한다.

2단계에서 윗면의 오른쪽과 앞쪽 엣지 조각의 방향이 뒤집힌다. 3단계를 통해 나머지 조각들에게 1단계를 없던 일로 만듦과 동시에 그 두 개의 엣지들도 방향만 뒤집힌 채 제자리로 돌아간다.

따라서 방향이 맞지 않는 조각이 짝수 개이기만 하다면 임의의 엣지 조각 방향 조합은 실제로 가능하다. 즉, 조각들의 위치가 정해져 있는 상태에서 엣지 조각의 방향을 정하는 경우의 수는 다음과 같다.

\(\dfrac{2^{12}}{2} = 2,048\)

코너 조각의 방향

엣지 조각의 방향을 정하는 경우의 수를 계산하기 위해서 상상의 큐브 껍질까지 동원하며 꽤 어려운 과정을 거쳤지만, 여기까지 이해하는 데 성공했다면 코너 조각의 방향 파트는 엣지 조각과 크게 다르지 않다.

마찬가지로, 코너 조각의 방향이 조각의 위치 및 엣지 조각의 방향과 간섭하는 것을 막기 위해 지금부터는 일단 조각들의 위치 및 엣지 조각들의 방향은 결정되었다고 생각하고, 이제부터 우리가 할 수 있는 건 이들을 바꾸지 않으면서 코너 조각의 방향만 바꾸는 것뿐이라고 생각하도록 하자.

엣지 조각과 거의 동일한 테크닉을 사용할 것이다. 단, 엣지 조각은 가능한 방향이 2개뿐이었지만 코너 조각은 3개여서, 약간의 디테일이 추가된다.

• 모든 코너 조각에는 3개의 면이 있다. 이 3개의 면 중 아무거나 골라서 0을 쓰고, 그로부터 시계 방향으로 돌아가면서 남은 두 개의 면에 1과 2를 쓴다.
• 마찬가지로 큐브를 감싸고 있지만 절대 움직이지는 않는 가상의 투명 큐브 껍질을 생각하고, 방금 쓴 수들 모두와 일치하도록 껍질에 숫자를 새긴다.

이 상태에서 큐브를 열심히 돌리고 나면,

• 코너 조각은 코너 조각의 위치로만 이동한다. 따라서 모든 코너 조각에는 여전히 3개의 수가 써 있고, 그 수들은 껍질의 수들과 여전히 겹쳐 있다.
• 조각에 써 있는 수와 껍질에 써 있는 수를 비교한다. 다음 세 가지의 경우가 있다.
  • 완전히 일치하는 경우. 이 경우 그 조각의 "방향값"을 0으로 정의한다.
  • 조각의 0이 껍질의 1 위치에 있는 경우. 껍질과 조각 모두 시계 방향으로 0, 1, 2가 써 있기 때문에, 이 경우 조각의 1은 껍질의 2와, 조각의 2는 껍질의 0과 겹쳐 있을 수밖에 없다. 즉, 이 경우는 완전히 일치하는 상태에서 일종의 '코너 트위스트'를 시계 방향으로 한 번 한 상태와 같다. 이 경우 그 조각의 "방향값"을 1로 정의한다.
  • 조각의 0이 껍질의 2 위치에 있는 경우. 마찬가지로 이 경우는 완전히 일치하는 상태에서 '코너 트위스트'를 반시계 방향으로 한 번 한 상태와 같다. 이 경우 그 조각의 "방향값"을 2로 정의한다.

여기서 회전을 한 번 시키면 모든 코너 조각들의 방향값의 합에 어떤 변화가 생길까? 엣지 조각의 방향에 대한 설명을 잘 이해했고, 눈치가 빠른 독자라면 "3으로 나눈 나머지가 변하지 않는다!"라고 외칠 수 있을 것이다. 그래도, 너무 성급해지지 말고 차근차근 증명하자.

마찬가지로 편의상 U를 실행하고 있다고 가정하고 위에서부터 윗면을 내려다보면,

• 코너 조각 4개가 보이고, 그 4개에는 각각 하나의 숫자가 써 있다(나머지는 옆면에 있어서 보이지 않는다).
• 껍질의 윗면이 보이고, 4개의 숫자가 보인다.
• 한 조각에 대해 그 조각에 써 있는 숫자를 \(a\), 그 숫자와 겹쳐서 보이는 껍질의 숫자를 \(b\)라 하자. \(a=b\)라면, 방향값은 0이다. \(a=b-1\) 또는 \(a=2, b=0\)라면, 방향값은 1이다. \(a=b+1\) 또는 \(a=0, b=2\)라면, 방향값은 2이다.
• 즉, 방향값과 \(b-a\)를 3으로 나눈 나머지는 같다.

이제 4개의 코너 조각에 대해 \(b-a\)의 값을 각각 더한 값을, 음, 이번엔 \(T\)라고 하자. 그렇다면 \(T\)는 현재 보이는 껍질의 숫자의 합에서 조각의 숫자의 합을 뺀 값과 같다. 중요한 건, \(T\) 역시 회전을 해도 변하지 않는다는 거다.

방향값과 \(b-a\)는 3으로 나눈 나머지가 같다고 했으므로, 우리는 모든 조각의 방향값의 합을 3으로 나눈 나머지는 변하지 않는다라는 결론을 얻는다. 처음 상태에서 모든 방향값은 0이기 때문에, 방향값의 합은 항상 3의 배수를 유지한다.

따라서, 코너 조각의 방향을 결정하는 \(3^8\)개의 방법 중 실제로 가능한 것은 그 중 3분의 1뿐이다. 7개의 방향을 결정하고 나면 나머지 하나의 방향은 방향값의 합이 3의 배수가 되어야 한다는 조건 때문에 자동 결정되기 때문이다.

이제 무엇을 해야 하는지는 보이지 않는가? 그렇다, 방향값의 합이 3의 배수기만 하면 모든 방향 조합이 가능함을 증명해야 한다. 그러기 위해서는 다음을 증명하면 충분하다.

• 임의의 두 코너 조각 \(c_1\)과 \(c_2\)에 대해, \(c_1\)을 시계 방향으로, \(c_2\)를 반시계 방향으로 돌리고, \(c_1\)과 \(c_2\)의 위치 및 나머지 조각의 위치와 방향은 건드리지 않는 방법이 존재한다.

만약 위 사실을 증명할 수 있다면, 우리는 다음 방법을 통해 방향값의 합이 3의 배수인 모든 방향 조합을 만들 수 있다.

1. 아무 코너 조각 \(c\)를 고른다.
2. 나머지 7개의 코너 조각 각각에 대해, 다음을 실행한다. 만약 그 조각의 방향이 이미 우리가 원하는 것과 같다면, 넘어간다. 만약 그 조각을 시계 방향으로 돌려야 한다면, 위의 사실로부터 존재성이 확인된 방법을 통해 그 조각을 시계 방향으로 돌리고 \(c\)를 반시계 방향으로 돌린다. 만약 그 조각을 반시계 방향으로 돌려야 한다면, 그 조각을 반시계 방향으로 돌리고 \(c\)를 시계 방향으로 돌린다.
3. 그러고 나면 \(c\)의 방향은 방향값의 합이 3의 배수라는 조건 때문에 자동으로 우리가 원하는 것과 같아야 한다.

위 사실을 증명하기 위해 우리는 다음 방법을 사용할 수 있다.

1. 적당한 회전을 통해 \(c_1\)을 윗면의 오른쪽 앞 구석으로, \(c_2\)를 윗면의 왼쪽 앞 구석으로 옮긴다.
2. R' D R F D F' U' F D' F' R' D' R U를 실행한다. ^[출처]
3. 1단계에서 했던 회전을 모두 거꾸로 한다.

2단계에서 해당 두 위치의 코너 조각이 각각 시계와 반시계 방향으로 회전하며, 3단계를 통해 1단계를 다른 모든 조각들에게 없던 일로 만들어 주고, \(c_1\)과 \(c_2\)도 제자리로 돌아간다.

따라서, 방향값의 합이 3의 배수이기만 하다면 임의의 코너 조각 방향 조합을 만드는 것이 가능하다! 즉, 모든 조각의 위치와 엣지 조각의 방향이 결정되었을 때 코너 조각의 방향을 결정하는 경우의 수는 다음과 같다.

\(\dfrac{3^8}{3} = 2,187\)

드디어 결론!

위에서 열심히 증명한 결과에 따라, 우리는 마침내 큐브의 가능한 상태 개수를 계산할 수 있다.

\(\dfrac{12!\times 8!}{2} \times \dfrac{2^{12}}{2} \times \dfrac{3^8}{3} = 43,252,003,274,489,856,000 \approx 4.325 \times 10^{19}\)

처음에 단순하게 계산한 결과에서 위치를 결정할 때 순열의 홀짝성 제약으로 절반이 되고, 엣지 조각의 방향을 결정할 때 홀짝성 제약으로 절반이 되고, 코너 조각의 방향을 결정할 때 3의 배수 제약으로 3분의 1이 되어 총 12분의 1이 실제로 가능한 상태의 수가 되었다.