3 x 2 슬라이딩 퍼즐
다음과 같은 슬라이딩 퍼즐을 푸는 것이 가능할까요 (x는 공간) ?:
1 3 2
4 5 x
나는 이것을 해결할 수 없었고 그것이 가능한지조차 모릅니다.
답변
해결책:
아니요, "해결 된"퍼즐에 부여한 위치에서 얻을 수 없습니다. $1,2,3,4,5$오른쪽 하단의 간격과 올바른 순서로 이것은 원래의 (유명한) " 14,15 퍼즐 " 과 같은 방식으로 증명 될 수 있습니다 .
여기 에서 찾은 증명과 유사한 몇 가지 기본 그룹 이론을 사용하여 보여줄 수 있습니다 .
퍼즐의 각 위치는 다음의 순열로 해석 될 수 있습니다. $\{1,2,3,4,5,6\}$, 빈 사각형은 다음과 같이 해석됩니다. $6$. 퍼즐의 각 움직임은 대칭 그룹의 전치로 해석 될 수 있습니다.$S_6$, 빈 사각형 바꾸기 $6$실제 타일 중 하나와 함께. 당신이 준 위치는 하나 개의 전위 떨어진 해결 위치에서,하지만 만에 도달 할 수 도 수$6$-스왑, 그 빈 사각형 이후 $6$같은 위치에 있어야하므로 상하 이동이 짝수이고 좌우 이동이 짝수 여야합니다. 그러나 짝수의 전치 조합은 교대 그룹에 있어야합니다.$A_6$따라서 이러한 조합으로는 단일 전치에 도달 할 수 없습니다.
목표가 첫 번째 행에 "1 2 3", 두 번째 행에 "4 5 x"를 얻는 것이라면 대답은 ' 아니오 '이며 불가능합니다.
이것은 Sam Loyd의 14-15 퍼즐의 작은 버전 입니다 . 하나의 빈 공간이있는 슬라이딩 퍼즐이있는 경우 패리티 ( 솔루션에 도달하는 데 필요한 스위치 수)를 기반으로 풀 수 있는지 확인할 수 있습니다 . 구체적으로 특별히:
- 먼저 빈 타일이 올바른 위치에 있도록 이동합니다.
- 이제 마법처럼 두 개의 타일을 선택하여 위치를 바꿀 수 있다고 상상해보십시오. 퍼즐을 풀려면 얼마나 많은 스왑이 필요합니까?
스왑 횟수가 짝수이면 원래 퍼즐을 풀 수 있습니다. 스왑 횟수가 홀수이면 원래 퍼즐을 풀 수 없습니다. (즉, 해결 된 퍼즐에서 시작하여 어떤 동작을 하더라도 항상 짝수 케이스에있을 것입니다. 타일을 밀어서 두 케이스 사이를 이동할 수있는 방법은 없습니다. 타일.)
귀하의 예에서는 퍼즐을 풀기 위해 정확히 하나의 스왑이 필요합니다. 따라서 슬라이딩으로 해결할 수 없습니다.