본문바로가기
[KAIST 과학영재교육연구원] k5. 명화 퍼즐 맞추기
수학동아 2018.12.02 15:38

 

문제 정사각형 조각 24개로 이뤄진 명화 퍼즐이 있다. 퍼즐의 각 조각을 상하좌우로 움직여 빈칸으로 옮길 수 있다. 그림처럼 두 조각의 위치를 바꿨을 때, 조각을 잘 움직여서 원래 모양으로 되돌릴 수 있을까? 

 

      

 

 

  •  
    Benedict Lv.5 2018.12.02 22:40

    불가능하다고 알려져 있지 않나요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      주니어멘토 Lv.1 2018.12.02 23:48

      안녕하세요! 주니어폴리매스 멘토입니다.

      문제가 올라오자마자 관심을 갖고 봐주셔서 감사합니다!

      당장 정답을 드릴 수는 없지만, 가능하다면 방법을, 불가능하다면 불가능한 이유를 증명하면 됩니다!
      (실제로 대부분의 수학 문제를 이런 식으로 접근하기도 하죠 :D)

      감사합니다!

      좋아요0
  •  
    21세기오일러 Lv.11 2018.12.03 15:58

    이런경우 바뀐 횟수가 홀수인 경우 안되지 않나요?

    그런데. 증명은 어떻게 하죠?

    댓글 작성하기 좋아요0 댓글수0
  •  
    냐뇨기 Lv.1 2018.12.05 22:05

    불가능 할것 같습니다?

    댓글 작성하기 좋아요0 댓글수0
  •  
    아인수타인 Lv.12 2018.12.06 15:48

    예전에 수학동아에 '보드게임 페스타'에 증명이 나왔던 거 같은데요...

    댓글 작성하기 좋아요0 댓글수1
  •  
    구머 Lv.5 2018.12.07 23:49

    불변값을 잘 뒤져봅시다~

    댓글 작성하기 좋아요1 댓글수1
    •  
      Benedict Lv.5 2018.12.12 23:31

      구머님 바쁘신지 폴리매스 잘 안 하시는 것 같습니다?

      좋아요0
  •  
    codename Lv.1 2019.01.04 22:18

    불가능합니다.

    간단하게 퍼즐을 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퍼즐도 별반 다르지 않습니다.

    누구나 이해할 수있도록 쉽게 풀이 하였습니다.

    더 좋은 풀이 이어나가시길 바랍니다.

    댓글 작성하기 좋아요1 댓글수2
    •  
      주니어멘토 Lv.1 2019.01.04 23:15

      안녕하세요. 주니어 폴리매스 멘토입니다!

      3 X 3 퍼즐의 경우에 대해 자세하고 친절한 풀이를 남겨주셨네요!

      사실 수학적으로 무언가를 증명하기 위해서는 조금 더 엄밀한 서술이 필요하겠으나,

      그 서술에 도달하기 위해서 이렇게 이해하기 쉬운 풀이로 흐름을 파악하는 것도 중요하죠.

      적어주신 것처럼 어느 두 조각의 위치를 바꾸기 위해선 다른 위치의 조각들도 불가피하게 변해야하는 것이 풀이의 중요한 포인트입니다.

      위의 Kid Milli님께서 달아주신 것처럼 '불변량'이라는 개념과 퍼즐들의 순서를 생각하면 풀이에 다가갈 수 있을 것이라 생각합니다.

      감사합니다!

      좋아요0
    •  
      codename Lv.1 2019.01.07 21:16

      이게 맞는지는 모르겠으나 한번 올려봅니다.

      처음 퍼즐에 일치하지 않는 조각의 갯수를 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
  •  
    me Lv.1 2019.05.19 10:35

    이 문제는 불변성에 의해 풀 수 있습니다. 

    이 퍼즐에서 무질서 계수 D라는 것을 정의하겠습니다.  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 (홀수) 이므로 불가능합니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    Ilúvatar Lv.6 2019.06.21 19:51
    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이므로 맟출수 없는 퍼즐이 된다.

    댓글 작성하기 좋아요0 댓글수0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911