본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬7. 체스판과 도미노
수학동아 2020.11.01 08:46

n, m은 자연수고 둘 중 하나는 짝수다. 이때 가로 n칸, 세로 m칸의 체스판을 도미노로 채울 수 있다. 예를 들어, 가로 4칸, 세로 3칸의 체스판은 다음과 같이 도미노로 채울 수 있다.

 

 

 

 

체스판의 4개의 칸이 만나는 임의의 꼭짓점 v에 대해, v에 인접한 도미노들을 아래 그림의 왼쪽에서 오른쪽 그림으로, 또는 오른쪽에서 왼쪽 그림으로 바꾸는 변환을 v에서의 '뒤집기'라고 하자. 이때 왼쪽에서 오른쪽으로 가는 움직임을 '세로로 뒤집기', 오른쪽에서 왼쪽으로 가는 움직임을 '가로로 뒤집기'라고 정의하자.

 

 

 

 

 

문제1 아래 그림에서 왼쪽 배치를 오른쪽 배치로 뒤집기만을 이용해서 바꿔보자.

 

 

 

 

 

문제2 임의의 가로 n칸, 세로 m칸의 체스판을 채우는 두 배치에 대해, 한 배치를 다른 배치로 뒤집기만을 이용해서 변환이 가능한가?

 

 

 

문제3 어떤 가로 n칸, 세로 m칸의 체스판을 채우는 한 배치에 뒤집기를 여러번 적용하니 다시 원래 배치로 돌아왔다고 하자. 이때 각 꼭짓점 v에 대해 세로로 뒤집기를 한 도미노 개수와 가로로 뒤집기를 한 도미노 개수가 항상 똑같음을 보여라.

 

 

  •  
    space Lv.7 2020.11.01 13:08 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      space Lv.7 2020.11.02 21:07

      1번 풀이입니다

      좋아요0
  •  
    code Lv.5 2020.11.01 21:39 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      code Lv.5 2020.11.07 12:08 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    Sin X Lv.5 2020.11.01 22:46 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수6
    •  
      Sin X Lv.5 2020.11.01 22:46

      2번 풀이입니다.

      좋아요0
    •  
      Sin X Lv.5 2020.11.02 22:32

      n,m에서 n은 무조건 짝수라고 가정하자. 이제 다음과 같은 배열을 기본배열이라고 정의하자.

      기본배열: 모든 도미노의 2짜리 길이는 길이 n의 선분과 평행한 쪽으로 놓고, 1짜리 길이는 길이 m의 선분과 평행한 쪽으로 놓은것이라고 하자. 

      분배선: 길이 n의 선분과 평행한 직선이고 격자점을 지난다. 또 어느 임의의 도미노도 통과하지 않는다.

      이제 어느 배열이라도 뒤집기를 통해 분배선이 존재하도록 만들수 있음을 보이자.

      ____________________________________________________________________________________________________________________________________________________________________________________________

      먼저 n=2, m=m일때는 자명하게 분배선이 존재한다. 이런경우에는 뒤집기를 통해 원하는 곳에 분배선을 항상 만들수 있다.

      n=n, m=m 일때 분배선이 존재한다고 가정하자.

      n=n+2, m=m 일때는 위쪽부분은 n,m짜리 아래부분은 2,m짜리로 나눌수 있는데 위의 부분의 분배선이 지나는 부분이 아래쪽 부분의 분배선이 안된다면, 세로로 뒤집기를 통해 분배선이 되도록 할수 있다. 따라서 모든 배열에 대해서 뒤집기를 통해 분배선을 만들수 있다.■

      ____________________________________________________________________________________________________________________________________________________________________________________________

      이제 모든 배열에 대해서 뒤집기를 통해 기본배열로 만들수 있음을 보이자.

      n=2k, m=1 일때는 기본배열이다.

      n=2k, m=1........m까지 모두 기본배열로 만들수 있다고 가정하자.

      이때 n=2k, m=m+1 일때 기본배열로 만드는 것이 가능함을 보이면 귀납적으로 모든 배열을 기본배열로 만들수 있다고 할수 있다.

      ____________________________________________________________________________________________________________________________________________________________________________________________이 배열은 위에서 증명한 것과 같이 분배선이 존재하도록 할수 있다. 분배선은 이 직사각형을 2k, i짜리 직사각형과 2k, j짜리 직사각형으로 분배하는데, 0<i<j<m+1 이므로 각각의 직사각형을 기본배열로 만드는 것이 가능하므로 2k, m+1 일때도 기본배열로 만드는 것이 가능하다.■

      ____________________________________________________________________________________________________________________________________________________________________________________________

      따라서 모든 배열을 뒤집기를 통해 기본배열로 만드는 것이 가능하므로,

      어느 한 배열을 뒤집기를 통해 다른 주어진 배열로 만드는 것이 가능하다고 할수 있다. ■

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.11.15 16:34 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      Sin X Lv.5 2020.11.17 23:37

      지적해 주셔서 감사합니다!

      수정가능하면 수정해 보겠습니다!

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.11.23 11:03

      Sin X 님의 풀이 중 '모든 배열을 기본배열로 만들 수 있다면 문제가 증명된다'는 아이디어를 이용해서 비슷한 증명을 생각해냈습니다! 그 아이디어가 없었다면 아마도 해법을 생각해내지 못 했을 것입니다. 감사합니다! 정리가 되는 대로 올리도록 하겠습니다. 

      좋아요0
    •  
      Sin X Lv.5 2020.11.24 14:23

      축하드립니다!

      좋아요0
  •  
    빅수빈데요 Lv.11 2020.11.02 00:45 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    khr519.py Lv.6 2020.11.02 16:29 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      khr519.py Lv.6 2020.11.03 13:47

      1번입니다

      좋아요0
  •  
    2heart Lv.9 2020.11.02 22:27 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    infinitepi Lv.8 2020.11.02 22:58 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    space Lv.7 2020.11.03 15:51 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      space Lv.7 2020.11.03 15:51

      3번 풀이입니다

      좋아요0
    •  
      supremum Lv.1 2020.11.03 21:38

      3번 `각 꼭짓점`에 대한 뒤집기 횟수로 하셨나요?

      좋아요0
    •  
      space Lv.7 2020.11.04 15:35

      좋아요0
  •  
    구머 Lv.5 2020.11.06 22:26

    1번은 꽤나 간단한 문제라 그냥 공개로 처리해도 될 것 같아염 여러분.

    댓글 작성하기 좋아요0 댓글수0
  •  
    조이 Lv.8 2020.11.07 20:35
    확인요청중
    댓글 작성하기 좋아요0 댓글수0
  •  
    피타고라수 Lv.4 2020.11.08 07:08
    확인요청중

    문제 1  풀이입니다.

    1. 노란색부분을 세로로 뒤집기한다.

    2. 초록색부분을 가로로 뒤집기한다.

    3.파란색부분을 세로로 뒤집기한다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    수학토끼 Lv.6 2020.11.14 00:13 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911