루빅스 큐브를 스크램블하는 것이 얼마나 어렵습니까?

루빅스 큐브는 40 년 동안 세계에서 가장 좋아하는 퍼즐 중 하나였습니다. 수많은 책에서 설명했듯이이를 해결하기 위해 여러 가지 다른 방법이 고안되었습니다. 전문가”speedcubers”는 몇 초 만에 해결할 수 있습니다.

놀라운 손재주와 같은 업적 외에도 Rubik’S Cube 와 관련된 많은 매혹적인 수학적 질문이 있습니다. 큐브의 이동은 6 개의면 중 하나를 90 도,180 도 또는 270 도 회전시키는 것으로 구성됩니다. 엄청난 43,252,003,274,489,856,000 가능한 상태를 적용하여 얻을 수 있습의 순서로 이동하여 해결된 상태입니다.

이러한 복잡성에도 불구하고 2010 년에 Rubik’s Cube 는 초기 상태에 관계없이 항상 20 이동 이하로 해결할 수 있음을 보여주었습니다. 이 숫자는”하나님의 숫자”,으로 알려진 모든 솔루션을 사용하여 인간은 일반적으로 사용하는 훨씬 더 많은 움직임이 최적의 값입니다.

해결 된 상태의 루빅스 큐브. 마이크 곤잘레스(TheCoffee)

하지만 무엇에 대해 반대 q:얼마나 많은 이동하는 데 필요한 출격 해결하나? 언뜻보기에 이것은 하나님의 수를 계산하는 것보다 훨씬 쉬운 질문처럼 들립니다. 결국,큐브를 해결하는 것과는 달리,하나를 스크램블링하는 것은 전혀 기술을 취하지 않습니다.

비슷한 질문이 카드 셔플에 대해 성공적으로 답변되었습니다. 유명한 예는 수학자 Dave Bayer 와 Perci Diaconis 의”riffle shuffle”에 대한 1990 년 연구입니다. 카드 갑판은 순서가 무작위 인 경우”혼합”으로 정의되며 가능한 각 순서가 나타날 확률이 동일합니다. Bayer 와 Diaconis 는 7 개의 riffle shuffles 가 표준 카드 놀이 갑판을 대략 혼합하기에 필요하고 충분하다는 것을 보여주었습니다.

지난 해,수학자 출판 비슷한 연구의 15 퍼즐로 구성되어 4×4 광장을 가득한 15 슬라이딩 타일과 하나의 빈 공간이다.

큐브가 스크램블된다는 것은 무엇을 의미합니까?

루빅스 큐브를 스크램블하려고하는 전형적인 사람은 반복적으로 임의의 움직임을 수행합니다. 그 결과 임의의 상태 시퀀스는 수학자가 마르코프 체인이라고 부르는 특별한 경우입니다. 키 숙박 시설은 주어진 현재 국가의 가능성 다음 상태가 될 것입에 의존하지 않는 이전의 어떠한다.

의 이론을 적용 마르코프 체인 큐브 스크램블링,그것이 다음과 같이 수의 임의의 움직임이 증가되는 확률에서 어떤 특정의 가능한 상태가 가까이 가까이 1/43,252,003,274,489,856,000. 수학자들은 가능한 각 상태가 동일한 확률로 발생하므로이를”균일 한 확률 분포”라고 부릅니다.

후 주어진 숫자의 임의 이동,큐브의 상태를 임의 될 것이다,그러나 그것의 확률분포를 정확하게 uniform;몇몇 국가 될 것이다 발생할 가능성이 높습니다.

d(t)는 t 랜덤 이동 후의 확률 분포가 균일 확률 분포와 얼마나 다른지를 설명하게한다. 무작위 이동(t)의 수가 증가함에 따라 d(t)의 값은 감소합니다. 스크램블되는 큐브는 d(t)가 작은 것에 해당합니다.

마르코프 사슬 몬테카를로

마르코프 사슬 이론에서 d(t)의 이러한 감소를”혼합”이라고합니다. 카드 셔플 링 및 퍼즐 스크램블링 외에도 마르코프 체인 믹싱 이론은 매우 심각한 실용적인 응용 분야를 가지고 있습니다. 현대 과학 및 공학에서 가장 중요한 계산 도구 중 하나는 몬테카를로 방법입니다. 이 방법은 이름이 지정된 후 유명한 카지노와 마찬가지로 근본적으로 기회에 의존합니다. 본질적으로 여러 무작위 추측을 사용하여 어려운 수학 문제를 대략 해결하려고 시도합니다.

실제로 마르코프 사슬은 종종 이러한 무작위 상태를 생성하는 데 사용됩니다. 을 이해하의 정확도 이러한 마르코프 체인 Monte Carlo 방법,주요 작업을 추정하는 것이 얼마나 신속하게 d(t)감소 t 증가합니다.

포켓 큐브

포켓 큐브에서 뒤섞이는 상태입니다. 마이크 곤잘레스(TheCoffee)

공부한 뒤섞 문제 표준에 대한 3x3x3 매직 큐브는 현재 매혹적인 미해결 도전입니다. 그러나 pocket cube 라고 불리는 더 작은 2x2x2 버전으로 관심을 돌리면 꽤 관리하기 쉬워집니다.

이 큐브에서는 가장자리와 가운데 조각이 없으며 모서리 조각 만 남습니다. 포켓 큐브에는 3,674,160 개의 가능한 상태 만 있으며 신의 수는 11 개에 불과합니다.

아래 그래프에서 포켓 큐브에 대해 d(t)를 플롯합니다. 11 이동 후 d(t)는 여전히 0.695 에서 매우 큽니다. 0.25 이하의 d(t)값을 산출하는 t 의 첫 번째 값(종종 마르코프 사슬 이론에서”혼합 시간”이라고 함)은 19 입니다. 25 이동 후 d(t)는 0.092;50 이동 후 0.0012; 그리고 100 이동 후에는 0.00000017 입니다.

거리의 큐브 포켓 유통에서 균일한 후 t 이동합니다. 에릭 Zhou

이렇게 많은 움직임을 사용해야 하을 완벽하게 출격 주머니나? 대답은 d(t)가 얼마나 작은지에 달려 있습니다. 그러나 하나님의 이동 횟수가 부족하다는 것은 확실히 사실입니다. 맨손으로,하나는 19 개 미만의 이동을 사용하지 않아야합니다. D(t)를 계산하는 코드를 포함한 자세한 내용은 여기에서 확인할 수 있습니다.물론 큐브를 스크램블하면 남은 것은 다시 해결하는 것입니다.

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 항목은 *(으)로 표시합니다