문제 정사각형 조각 24개로 이뤄진 명화 퍼즐이 있다. 퍼즐의 각 조각을 상하좌우로 움직여 빈칸으로 옮길 수 있다. 그림처럼 두 조각의 위치를 바꿨을 때, 조각을 잘 움직여서 원래 모양으로 되돌릴 수 있을까?
-
-
-
불가능합니다.
간단하게 퍼즐을 3*3으로 바꾸어서 풀겠습니다.
그림을 숫자로 바꾼다면
4 2 3
1 5 6
7 8
가 됩니다. 여기서 우리가 1, 2, 3의 순서로 다시 바꾼다면
1 4 2 1 4 1 2 3
5 3 -> 5 3 2 -> 5 4 6
7 8 6 7 8 6 7 8
이 됩니다. 따라서 우리는 위 아래가 순서가 바뀔 시에 밑에 두 숫자가 순서가 바뀌게됨을 알아내었습니다.
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
5 4 6 -> 5 6 -> 5 6 8 -> 6 7 8 -> 4 5 6
7 8 7 4 8 7 4 5 4 8 7
우리는 여기서 알아낸것이 한가지 더 있습니다.
바로 퍼즐 중간의 좌우가 바뀌면 그 바로 밑의 좌우가 다음으로 바뀐다는 것입니다.
한번 더 해볼까요?
1 2 3 1 2 3 1 2 3
4 6 7 -> 8 7 -> 5 4 6
8 5 6 4 5 7 8
!!!!!!
우리는 이것을 보고 확신할 수 있습니다.
결국 이 퍼즐은 풀지 못한다는 것을요.
5*5퍼즐은 다르지 않겠느냐고 생각하는 분이 계실 수 있으나,
저렇게 상하가 바뀌거나 좌우가 바뀐 경우 필요한 블럭은 2*3이기 때문에,
5*5퍼즐도 별반 다르지 않습니다.
누구나 이해할 수있도록 쉽게 풀이 하였습니다.
더 좋은 풀이 이어나가시길 바랍니다.
-
안녕하세요. 주니어 폴리매스 멘토입니다!
3 X 3 퍼즐의 경우에 대해 자세하고 친절한 풀이를 남겨주셨네요!
사실 수학적으로 무언가를 증명하기 위해서는 조금 더 엄밀한 서술이 필요하겠으나,
그 서술에 도달하기 위해서 이렇게 이해하기 쉬운 풀이로 흐름을 파악하는 것도 중요하죠.
적어주신 것처럼 어느 두 조각의 위치를 바꾸기 위해선 다른 위치의 조각들도 불가피하게 변해야하는 것이 풀이의 중요한 포인트입니다.
위의 Kid Milli님께서 달아주신 것처럼 '불변량'이라는 개념과 퍼즐들의 순서를 생각하면 풀이에 다가갈 수 있을 것이라 생각합니다.
감사합니다!
좋아요0 -
이게 맞는지는 모르겠으나 한번 올려봅니다.
처음 퍼즐에 일치하지 않는 조각의 갯수를 i라 합시다.
예를 들면 처음의 퍼즐은 0이겠죠?
위하고 아래의 블럭이 바뀐 문제와 같은 상황은 i=2 입니다.
그러면 돌렸을때 i의 값이 2가 나오는 경우가 있는지를 알아보면 알수있을것입니다.
우리는 이러한 퍼즐을 맞출 때 하는 경우는 모두 조각을 일정한 직사각형에서 돌리는 것입니다.
1 2 3 1 2 3
4 5 6 4 6 8
7 8 7 5
이 상황을 보시면은 6,5,8 블럭이 반시계방향으로 한 칸 움직였음을 알 수 있습니다.
즉, 5,6,8,(공백) 의 사각형에서 회전하였다고 볼수 있습니다.
다른 방법도 결국 사각형을 그리며 회전한것입니다.
그럼 우리는 블럭을 다음과 같이 돌렸을 때 i=2인경우가 있는지를 찾아 내면 됩니다.
일정한 크기의 직사각형의 모양을 띄며 돌아가게 되면은,
원위치로 돌아올 만큼 많이 돌리지 않는 이상 위치가 잘못되게 됩니다.
즉, 그 직사각형(선)에 닿아 있는 블럭만큼 위치가 잘못됨을 알 수 있습니다.
그 직사각형의 가로줄을 a라 합시다.
그럼 위아래로 합쳐 2a이겠네요.
가로줄에 포함된 블럭을 제외하고
그 직사각형에 세로줄에 포함된 블럭의 갯수를 b라합시다.
그럼 양옆으로 합쳐 2b겠지요?
그러나 이렇게 돌릴 수 있는 경우에는 공백을 포함하므로,
2(a+b)-1 개의 블럭이 잘못되게 됩니다.
2(a+b) 는 짝수이므로 잘못되게 되는 블럭의 갯수는 홀수개입니다.
즉 i=2인 경우는 존재하지 않으므로,
저 퍼즐은 풀 수 없습니다.
좋아요0
-
-
이 문제는 불변성에 의해 풀 수 있습니다.
이 퍼즐에서 무질서 계수 Dp 라는 것을 정의하겠습니다. Dp 를 원래의 배열에서 변화되어 수의 순서가 바뀐 타일 쌍의 개수라고 정의 합시다
즉 각 퍼즐의 부분을
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 으로 보면 위의 배열은 Dp=0,
1 2 3 4 5 6 7 8 9 10 12 15 13 14 11 에서는 변화된 타일 쌍이 (12,11), (15,13), (15,14), (15,11), (13,11), (14,11)이므로 Dp=6이라고 정의 할 수 있습니다.
이때 우리는 Dp=0일때 아무리 타일을 변화해도 항상 짝수개의 배열이 바뀌므로 Dp=0 에서 항상 Dp=짝수로만 바뀔 수 있음을 알 수 있습니다.
6 2 3 4 5 1 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 위의 명작 퍼즐은 바뀐 타일 쌍이 (6,2), (6,3), (6,4), (6,1), (6,5) (2,1), (3,1), (4,1), (5,1) 이므로 Dp=9 (홀수) 이므로 불가능합니다.
-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 어떤 수 X에 대하여 그 뒤에 나오면서 X보다 작은 수의 개수를 f(x) 이라고 하자.이때, f(1)+f(2)+f(3)+...+f(15) = A라고 정의하자
완성된 퍼즐에서 A=0이다.
퍼즐조각이 좌우로 움직일때는 A값이 변하지 않는다.
퍼즐조각이 상하로 움지일때는 A값이 항상 짝수로 바뀐다는 것을 알수있다.
그러므로 어떤 퍼즐의 A값이 짝수이면 맟출수 있고 홀수이면 맟출수 없다.
그러나 본 명화퍼즐에서는 A값이 9이므로 맟출수 없는 퍼즐이 된다.
