1. 전 세계에서 인기 있는 장난감
1974 년 봄 부다페스트 응용예술학원 건축학 교수 E. Rubik 은 재미있는 생각을 가지고 있다. 그는 학생들이 공간 기하학의 다양한 회전을 직관적으로 이해할 수 있도록 교육 도구를 디자인하고 싶어한다. 그는 각 면이 자유롭게 회전할 수 있는 작은 사각형으로 구성된 3×3×3 입방체를 만들기로 했다. 이러한 입방체는 다양한 공간 회전을 쉽게 시연할 수 있습니다.
이 아이디어는 좋지만 실제로 까다로운 문제에 직면 해 있습니다. 이러한 큐브의 모든 면을 자유롭게 회전시키는 방법은 무엇입니까? 루비크는 자석이나 고무줄로 작은 정사각형을 연결하는 것과 같은 많은 생각을 시도했지만 모두 실패했다. 그해 여름의 어느 날 오후, 그는 다뉴브 강변에서 바람을 쐬고 있었고, 무심코 강가의 조약돌 위에 눈빛이 떨어졌다. 갑자기 새로운 생각이 그의 머릿속을 스쳐 지나갔다. 조약돌 표면과 비슷한 원형 표면으로 입방체의 내부 구조를 처리한다. 이 새로운 아이디어는 성공적이었고, Rubik 은 곧 자신의 디자인을 완성하고 헝가리 특허청에 특허를 신청했다. 이 디자인은 모두가 잘 아는 큐브, 큐브라고도 함) [주 1].
6 년 후 헝가리 사업가 겸 아마추어 수학자가 이끄는 루빅 큐브 (rubik's Rubik's Cube) 가 서유럽과 미국 시장에 진출해 놀라운 속도로 전 세계를 휩쓸고 있는 패션 장난감이 됐다. 이후 25 년 동안 큐브 판매량이 3 억을 돌파했다. 루빅스 큐브의 플레이어 중에는 이를 배우는 아이도 있고 다국적 기업의 사장도 있다. 루빅이 생각했던 것처럼 우주 기하학의 교육 도구가 되지는 않았지만 역사상 가장 잘 팔리는 장난감이 되었다.
베스트셀러 큐브의 마법은 놀라운 색상 조합의 수에 있다. 큐브 공장 출하 시, 각 면에는 한 가지 색이 있는데, 모두 여섯 가지 색이 있다. 하지만 이 색깔들이 헝클어진 후 형성할 수 있는 조합수는 4325 억 개에 이른다. 만약 우리가 이 조합들을 각각 큐브를 만든다면, 지구에서 250 광년 떨어진 먼 별까지 큐브를 함께 배열할 수 있다. 다른 말로 하자면, 만약 우리가 이런 큐브의 한쪽 끝에 등불을 놓는다면, 250 년이 걸려야 빛이 다른 쪽 끝을 비출 수 있다. 부지런한 게이머가 모든 조합을 시도해 보고 싶다면, 먹거나 마시지 않아도 654 억 38+0500 억년이 걸린다. (대조적으로 우리 우주는 아직 654 억 38+0400 억세 미만이다.) 이런 조합수치에 비해 평일에 광고주들이 많이 사용하는' 천억',' 수억',' 수십억' 과 같은 허세, 고객을 홀랑거리는 형용사는 모두 얻기 어려운 겸손이 되었다. BIGBANG 에서 루빅스 큐브를 시작하더라도 색이 헝클어진 큐브를 복원할 희망이 거의 없다고 자신 있게 말할 수 있다. (윌리엄 셰익스피어, 윈스턴, 자신감명언)
큐브와 "신수"
큐브의 플레이어가 많아서 서로 경쟁하는 것은 자연스러운 일이다. 198 1 부터 큐브 애호가들은 세계 차원의 큐브 대회를 개최하여 자신의 세계기록을 창조하기 시작했다. 이 기록은 끊임없이 새로워진다. 이 글이 집필될 즈음에는 큐브의 가장 빠른 기록이 복원됐다. 우리가 이 글의 서두에서 언급한 바와 같이 이미 놀라운 7.08 초에 이르렀다. 물론, 개별 복구의 기록은 우연성이 있다. 이런 우연성을 줄이기 위해 2003 년부터 큐브 대회 우승은 여러 차례 회수한 평균 점수에 의해 결정된다. 현재 이 평균 성적의 세계기록은 1 1.28 초입니다. 이러한 기록의 출현에 따르면 큐브에는 천문학적인 색상 조합이 있지만 요령만 익히면 어떤 조합이라도 복원하는 데 필요한 회전 횟수가 많지 않다는 것을 알 수 있다.
그렇다면 어떤 색상 조합이 복원될 수 있도록 몇 번 이상 회전해야 합니까? [주 4]? 이 문제는 많은 사람들의 흥미를 불러일으켰는데, 특히 수학자들은 더욱 그렇다. 어떤 조합을 회복하는 데 필요한 최소 회전수는 수학자들이' 신수' 라고 놀렸고, 큐브라는 장난감계의 총아는 이' 신수' 로 학계를 단번에 침범했다.
"신수" 를 연구하려면 당연히 큐브의 복원 방법을 먼저 연구해야 한다. 큐브를 가지고 노는 과정에서 사람들은 주어진 색상 조합을 복원하는 것이 쉽다는 것을 이미 알고 있었다. 이는 수많은 플레이어의 우수한 기록에 의해 증명되었다. 큐브 플레이어가 사용하는 복원 방법은 인간의 뇌는 쉽게 파악할 수 있지만 최소한의 회전 횟수는 없기 때문에' 신수' 를 찾는 데 도움이 되지 않는다. 회전 횟수가 가장 적은 방법을 찾는 것은 수학 문제이다. 물론 이 문제는 수학자들에게는 어렵지 않다. 일찍이 90 년대 중반에는 실용적인 알고리즘이 있어 평균 15 분 정도면 지정된 색상 조합을 복원하는 최소 회전 횟수를 찾을 수 있었다. 이론적으로, 만약 누군가가 각 색상 조합에 대해 이런 최소 회전 수를 찾을 수 있다면, 최대 회전 수는 의심할 여지 없이' 신수' 이다. 하지만 유감스럽게도, 4325 억이라는 거대한 숫자는 사람들이' 신수' 를 엿보는 걸림돌이 되었다. 위에서 언급한 알고리즘을 채택하면 1 억 대의 기계 계산을 동시에 사용하더라도 1000 여만 년이 걸려야 완성할 수 있다.
무력이 통하지 않는 것 같아서 수학자들은 그들의 본업인 수학에 종사했다. 수학적 관점에서 볼 때 큐브의 색상 조합은 변화무쌍하지만 실제로는 일련의 기본 연산 (즉, 회전) 으로 인해 발생하며, 이러한 연산에는 몇 가지 매우 간단한 특징이 있습니다. 예를 들어, 모든 연산에는 반대 연산이 있습니다 (예: 시계 방향 회전과 반대 연산은 시계 반대 방향 회전임). 이런 연산에 대해 수학자들의 무기고에 매우 효과적인 도구가 있다. 이 도구는 군론이라고 불리며 큐브가 나타난 140 여 년 전에 나타났다. 독일의 수학자 D 힐버트는 군론을 배우는 열쇠가 좋은 예를 선택하는 것이라고 말했다. 큐브가 나온 이래로 수학자들은 큐브를 통해 군론에 관한 책 몇 권을 썼다. 따라서 큐브는 공간 기하학의 교육 도구가 되지는 않았지만, 어느 정도는 군론을 배우는' 좋은 본보기' 로 사용될 수 있다.
큐브 연구에 대해 군론은 큐브의 대칭성을 최대한 활용할 수 있다는 중요한 장점을 가지고 있다. 우리가 4325 억이라는 거대한 숫자를 언급했을 때, 큐브로서 큐브의 대칭성을 고려하지 않았다는 누락이 있었습니다. 그 결과, 4325 억 가지의 색상 조합은 사실 대부분 똑같지만, 다른 각도에서 (예를 들어, 서로 다른 얼굴을 위로 향하게 하는 것) 볼 뿐이다. 따라서 4325 억이라는 무서운 숫자는 실제로 "돼지 고기 주입" 입니다. 그럼, 이' 돼지고기' 중 몇% 의' 물' 은? 말을 해서 모두를 겁주다: 거의 99% 를 차지한다! 즉, 수학자는 대칭을 통해서만 큐브의 색상 조합을 두 단계 줄일 수 있습니다 [주 5].
그러나 두 개의 수량을 줄이는 것만으로는' 신수' 를 찾기에 충분하지 않다. 이는 앞서 언급한 1000 만년을 10 만년으로 줄인 것이기 때문이다. 수학 문제를 해결하기 위해 10 만년은 분명히 너무 길기 때문에, 우리는 누군가가 1 억대의 컴퓨터를 사용하여 신의 수를 계산할 것이라고 기대하지 않는다. 수학자는 비록 총명하지만, 다른 방면에서 반드시 부자가 되는 것은 아니다. 아마도 그들이 정말로 사용할 수 있는 것은 그들의 책상 위에 있는 기계일 것이다. 그래서' 신수' 를 찾기 위해서는 더 교묘한 사고를 찾아야 한다. 다행히도, 군론 도구의 힘은 입방체의 대칭과 같은 명백한 것을 분석하는 데 사용되지 않았다. 그것의 도움으로, 새로운 생각이 곧 나타났다.
3. "하나님의 수" 찾기
1992 년 독일 수학자 H. Kochiemba 는 큐브 복원 방법을 찾는 새로운 아이디어를 제시했다. 그는 큐브의 몇 가지 기본 회전 패턴이 자신의 시리즈를 형성할 수 있다는 것을 발견했다. 이 회전을 통해 거의 200 억 가지의 색상 조합을 형성할 수 있다 [주 6]. 이 200 억 가지의 조합을 이용하여 코현바는 큐브 복원을 두 단계로 분해했다. 첫 번째 단계는 임의의 색상 조합을 200 억 가지 조합 중 하나로, 두 번째 단계는 200 억 가지의 조합을 복원한다. 큐브의 복원을 왕양해에서 고정 목적지로 향하는 작은 배에 비유한다면, 코현팔에서 제안한 200 억 가지의 색상 조합은 마치 그 고정 지점보다 200 억 배 큰 특수한 수역과 같다. (알버트 아인슈타인, Northern Exposure (미국 TV 드라마), 스포츠명언) 그가 제안한 두 단계는 배가 먼저 그 특수한 수역을 향해 항해하게 한 다음 그곳에서 그 고정 목적지를 향해 나아가게 하는 것과 같다. (윌리엄 셰익스피어, 햄릿, 희망명언) 왕양해에서 거대한 특수수역을 찾는 것이 그 작은 목적지를 직접 찾는 것보다 훨씬 쉽다는 것이 코선바의 새로운 아이디어의 장점이다.
그럼에도 불구하고 코차바의 방법으로 신의 수를 추정하는 것은 쉬운 일이 아니다. 특히 빠른 계산을 위해 컴퓨터 메모리에 200 억 가지의 색상 조합 ('특수수역' 의 지도) 을 복구하는 최소 회전 수를 저장하는 것이 가장 좋다. 약 300 메가바이트의 메모리가 필요하다. 300 조 원은 오늘날 큰 숫자는 아니지만, 코현바가 새로운 사상을 내놓은 해에 일반 기계의 메모리는 10 분의 1 도 안 된다. 그래서 3 년이 지나서야 Kochenba 의 방법으로 첫 번째 추정 결과를 제시한 사람이 있었다. 그의 이름은 M. Reid 입니다. 미국 중플로리다 대학의 수학자입니다. 1995 에서 Reid 는 계산을 통해 큐브의 모든 색상 조합이 최대 12 회 회전을 거쳐 코크렌바이르나의 200 억 가지 조합 중 하나가 될 수 있다는 사실을 발견했습니다. 최대 18 회 회전 후 200 억 개 조합 중 어느 것도 복구할 수 있습니다. 이는 큐브의 모든 색상 조합이 최대 회전 12+ 18=30 회 회전하면 복구된다는 것을 의미합니다.
앞서 언급한 결과를 얻은 리드는 곧 그의 계산을 개선하여 결과를 30 개에서 29 개로 줄였는데, 이는' 신수' 가 29 개를 넘지 않는다는 것을 보여준다. 이후 컴퓨터 기술이 발달하면서 수학자들은 Reid 의 결과를 더욱 보완했지만 진전은 빠르지 않았다. 1 1 년 후인 2006 년까지 오스트리아 요하네스 케플러 대학 기호계산연구소의 박사 실부 라두가 이 결과를 27 로 밀었다. 이듬해인 2007 년 미국 동북대학의 컴퓨터 과학자 D. Kunkle 과 G. Cooperman 은 이 결과를 26 으로 밀었다. 그들의 작업은 병렬 컴퓨팅 시스템을 사용하여 700 만 메가바이트의 메모리를 사용하며 8000 시간의 컴퓨팅 시간 (거의 1 년 24 시간 연속 컴퓨팅에 해당) 을 소비했습니다.
이 계산은 "신의 수" 가 26 을 초과하지 않을 것임을 보여준다. 그러나 이러한 모든 계산의 가장 큰 장점은 코산댐의' 특수수역' 을 이용하는 것도 가장 치명적인 약점이다. 그들이 제시한 수리 방법은 반드시 그 특수한 수역을 통과해야 하기 때문이다. 하지만 사실, 많은 색상 조합에 대한 최적의 복구 방법은 그 특별한 수역을 전혀 통과하지 않습니다. 예를 들어, 목적지에 가깝지만 특별한 수역에 있지 않은 배는 대륙 대만성의 직항기 전세기처럼 목적지로 가기 전에 일부러 그 특별한 수역을 우회할 필요가 없는 것이 분명하다. 따라서 코선바의 생각으로 얻은 복원 방법이 반드시 최선은 아니며,' 신수' 에 대한 추정도 과대평가될 가능성이 높다.
하지만 코신바의 특수한 수역을 도입하지 않으면 계산량이 너무 크면 어떻게 합니까? 수학자들은 그 특수수역의' 면적' 을 확대하는 절충안을 취하기로 했다. 특수수역이 커질수록 최적의 재활용 경로가 지나갈 가능성이 높아지기 때문이다 (물론 계산량도 그에 따라 증가한다). 2008 년 15 년을 연구한 컴퓨터 전문가 Rokic 은 Koshanba 의 특수수역을 수천 배로 확대하는 교묘한 방법을 사용하여 몇 달 동안 신의 수에 대해 네 차례의 맹렬한 공격을 개시하여 예상치를 25 에서 22 로 낮췄다. 이 글이 집필될 때까지 이것은 세계 최고의 결과이다. Rokic 의 계산은 영화 특수효과 제작사인 Sony Pictures Imageworks 의 지원을 받아' 스파이더맨' 등 유명 영화에 특효를 제작했고, Rokic 에게 50 년 동안 쉬지 않고 계산되는 컴퓨터 자원을 제공했다.
그래서 지금 우리는' 신수' 가 22 를 넘지 않아야 한다는 것을 알고 있다. 그러나 Rokic 의 특수 수역은 크지만 색상 조합은 여전히 많다. 가장 좋은 회복 방법은 그 특별한 수역을 통과하지 않는 것이다. 그래서' 신수' 는 22 보다 작을 가능성이 높다. 그럼 얼마예요? 비록 사람들이 정확히 알 수는 없지만, 여러 가지 조짐은 20 일 가능성이 매우 높다는 것을 보여준다. 이는 사람들이 지난 몇 년 동안의 모든 노력에서 어떤 색상 조합도 20 회 이상 뒤집혀야 복원할 수 있기 때문이다. Rokic 이 직접 계산한 약 4 조 가지의 색상 조합을 포함한다. (알버트 아인슈타인, Northern Exposure (미국 TV 드라마), 예술명언) 이것은' 신수' 가 20 을 넘지 않을 가능성이 높다는 것을 보여준다. 한편, 수만 가지의 색상 조합을 찾았고, 20 회전을 거쳐야 복원할 수 있다는 것을 보면' 신수' 가 20 보다 작을 수 없다는 것을 알 수 있다. 이 두 가지 측면을 결합하여 수학자들은 일반적으로' 신수' 의 진실값이 20 이라고 생각한다. 물론,' 신' 은 미묘할 수도 있고, 우리 중 누구도 그것이 어딘가에서 우리를 놀라게 할지 장담할 수 없다. 우리가 믿을 수 있는 유일한 이유는 이 게임과 수학이 얽힌 신비한' 신수' 가 세상에 나온 날로부터 그리 멀지 않다는 것이다.
주다주석을 달다
1 .. 루비크 자신이 큐브를 명명했고, 큐브는 미국 장난감 회사인 Ideal Toys 가 명명했다. 서방 국가에서는 큐브라는 이름이 더 인기가 있고, 중국에서는 큐브라는 이름이 더 인기가 있다. 또 독자에게 상기시켜야 할 것은 큐브가 여러 가지가 있다는 점이다. 이 글에서 소개한 3×3×3 큐브는 가장 흔한 것 중 하나일 뿐이다.
2. 구체적인 계산은 다음과 같습니다. 큐브를 구성하는 작은 입방체에는 8 개의 정점이 있고, 그 사이에는 8 개가 있습니다! 종 교체 각 정점에는 3 가지 색상이 있으며 방향은 37 가지 조합으로 구성됩니다 (구조적 제한으로 인해 큐브에는 7 개의 정점만 독립적인 방향을 가질 수 있음). 마찬가지로 큐브에는 12 개의 가장자리가 있는 큐브, 중간에 12 가 있습니다! /2 가지 배열 (2 로 나눈 이유는 큐브의 정점이 확정되면 절반의 가장자리 배열만 가능하기 때문입니다.) 이들 면은 각각 2 1 1 의 조합으로 두 가지 색상을 가지고 있습니다 (구조적 제한으로 인해 큐브는 1 1 면만 독립적인 방향을 가질 수 있음). 그래서 루빅스 큐브의 총 색상 조합은 8 입니다! ×37× 12! × 211/2 = 4325200327489856000, 약 4325 억. 또한, 큐브가 해체되는 것을 허락한다면, 앞서 언급한 구조적 제한은 더 이상 존재하지 않을 것이며, 그 색상 조합의 수는 최대 5 190 억이 될 것입니다. 그러나 조합 수가 늘었다고 해서 복구가 더 어렵다는 뜻은 아니다. 사실 큐브 구조의 조합 수에 대한 제한은 큐브가 복원하기 어려운 주요 원인이다. 예를 들어, 26 개의 영문자는 인접한 글자의 교환에서 약 400 억 가지의 조합으로 큐브 색상의 조합보다 훨씬 많지만, 인접한 글자의 교환을 통해 무작위로 배열된 26 개의 영문자를 A 에서 Z 로 되돌려 초기 배열로 되돌리는 것은 매우 간단하다.
3. 정확히 말하면, 다섯 번의 시도 중 세 번의 득점의 평균을 취한다.
4. 이 문제를 의미 있게 하기 위해서, 당연히 먼저 회전이 무엇인지 정의해야 한다. 큐브의 수학 연구에서 회전은 큐브의 모든 면 (9 개의 작은 사각형 포함) 을 시계 방향이나 시계 반대 방향으로 90 도 또는180 도 회전하는 것을 의미합니다. 얼굴마다 세 가지 회전이 있습니다. (생각해 보세요, 왜 네 가지가 아닌가요? ) 을 참조하십시오. 큐브에는 6 면이 있기 때문에 18 가지 기본 회전 모드가 있습니다.
5. 정확히 18 가지 기본 회전 모드가 있습니다. 결과 색상 조합 * * * 은 8 입니다! ×8! ×4! /2 (약 6543.8+095 억).