본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[슬기로운 수학생활] 슬29. 체스판 나누기
수학동아 2022.08.31 20:53 조회 732

슬기로운 수학생활 29번

 

 

 

체스판 나누기

 

 

 

문제 출제자 : 백진언 미시간 대학교 수학과 박사과정생

 

 

 

 

 

 

 

 

 

8   imes 8 칸으로 이루어진 체스판이 있다. 이 위에 직선을 몇 개 그려서 모든 칸이 적어도 직선 하나로는 나뉘게 하고 싶다.

 

 

여기서 한 칸이 어떤 직선으로 나뉜다는 건 직선이 칸의 안쪽을 관통한다는 것(경계에만 닿는 건 허용하지 않음)일 때,

 

 

다음 문제를 풀어보자.

 

 

 

문제 1

최소 몇 개의 직선을 그려야 할까?

 

 

 

문제 2

8   imes 8 체스판이 아니라 n   imes n 체스판인 경우에는 최소 몇 개의 직선을 그려야 할까? 증명할 수 있는 상한과 하한을 찾아보자.

 

 

 

 

백진언 연구원의 팁

 

직선 8개로는 가로줄이나 세로줄을 죽죽 그으면 바로 나눌 수 있다. 직선 7개로도 가능하다.

 

 

  •  
    Funmaster Lv.7 2022.09.01 01:03

    문제 1번 n=7일때 증명입니다.

    n=6일때 불가능한 이유는,정확하진 않지만 잇는 선이서 선마다 지나는 칸의 수가 줄어들어 6개는 어떠한 방식상 중앙을 채우면 가장자리는 선분 하나로 몇개 못 채우는 상황이 오는 것을 알아냈습니다(수학적 증명은 다음에). 

     

    수정본(이제 다 지나갑니다)

     

    댓글 작성하기 좋아요0 댓글수2
    •  
      그로텐디크 Lv.5 2022.09.01 08:30

      4번째 열 7번째 행 검정 사각형은 선이 닿지 않습니다

      좋아요0
    •  
      Funmaster Lv.7 2022.09.01 16:58

      앗 다시 해봐야겠네요.

      좋아요0
  •  
    RedoC Lv.6 2022.09.01 15:34

    매우 당연하긴 하지만, 일단 올려봅니다.

    a_n를 n \times n 체스판에서 그려야 하는 선의 최소 개수라고 두면

    a_n \leq a_{n+1} \leq a_{n}+2고 또 a_n \leq n입니다.

    댓글 작성하기 좋아요0 댓글수1
  •  
    그로텐디크 Lv.5 2022.09.01 16:59

    지금까지 제가 얻은 결과를 말해보자면, f(n)을 n*n체스판의 선의 최소 개수라 할때

    f(n)\leq f(n+1)\leq f(n)+2입니다.

    그리고 한 직선이 체스판에서 만날 수 있는 칸의 최대 개수는 2n-1입니다. 실례는 그냥 대각선 약간 올린 것으로 확인 가능하고, 이유는 기울기가 1이상이라면 대각선으로 반전시켜서 1아래로 만든 다음에, 한 x값에서 만나는 칸이 2이하라는 것을 생각하고, 2n칸을 만나게 하면 모순 된다는 것을 쉽게 확인하면 알 수 있습니다. 그러므로 f(n)의 하한과 상한은 \frac{n}{2}< \frac{n^2}{2n-1}\leq f(n)\leq n이 됩니다. 1번에 적용하면 5<= f(8) <=8이 되겠네요

    댓글 작성하기 좋아요0 댓글수4
    •  
      pure math Lv.7 2022.09.01 17:12

      그런데 n^2/(2n-1)이라는 것은 모든 점이 대각선 약간 올린 거에 포함될 수 있다는 것인데 그건 아니지 않나요?

      좋아요0
    •  
      그로텐디크 Lv.5 2022.09.01 17:17

      일단 최소한의 하한으로써 한 것입니다

      좋아요0
    •  
      pure math Lv.7 2022.09.01 17:19

      아하

      좋아요0
    •  
      수냥이 Lv.5 2022.09.02 07:53

      그러면 일단 문제 1번 n=8은 되는 것이 확실합니다.

      좋아요0
  •  
    Amath Lv.8 2022.09.02 17:51

    저도 지금까지 생각해 본 결과를 올리겠습니다. n*n 체스판은 가로 n+1개, 세로 n+1개의 선분으로 구성되어 있는데, 그러면 한 가로로 배치된 선분 위엔 교점이 9개가 있게 되고, 그 선분은 그 교점들이 왼쪽부터 오른쪽 순서대로 0,1,2,3,..., n에 대응되는 수직선으로 생각할 수 있습니다. 

     

    가로 선분 n+1개를 전부 수직선으로 생각하고, 그 연장선을 그린다면, 수직선 n+1개는 임의의 기울기가 음수인(오른쪽을 x축이 증가하는 방향이라고 보는 평범한 좌표평면을 기준으로) 직선 L과 만나는 점이 각각 한 개씩 있게 됩니다. 그 수직선을 위에서부터 아래로 내려가며 m_{1}, m_{2}, ..m_{n+1}이라고 이름붙이고, 수직선에서 0보다 왼쪽에 있는 점들은 전부 0에, 8보다 오른쪽에 있는 점들은 전부 8에 대응된다고 생각할 때, 수직선 m_{i}와 직선 L이 만나는 점을 P_{i}(L)이라고 하면, 다음의 사실을 알 수 있습니다. 

     

    수직선 m_{i}와 수직선 m_{i+1} 사이에 있는 정사각형 칸들 중 직선 L과 만나는 칸의 개수는 \left \lceil P_{i+1}(L) \right \rceil - \left \lfloor P_{i}(L) \right \rfloor이다. 

     

    왜냐하면, P_{i}(L)이 수직선에서 r과 r+1 사이에 있다면(r도 포함) 선분 (r,r+1)이 한 변인 정사각형 칸을 포함하고, P_{i+1}(L)이 s와 s+1 사이에 있다면(s+1도 포함) 적어도 선분 (s+1,s)가 한 변이 정사각형 칸을 포함하는데, 직선 L의 기울기가 음수이므로 r이 한 꼭짓점인 정사각형부터 s+1이 한 꼭짓점인 정사각형까지의 s-r+1개의 정사각형을 지나게 되고, 수직선 m_{i}와 수직선 m_{i+1} 사이에 있는 정사각형 칸들 중엔 그 정사각형들만 지난다는 것에서, 이 결과를 분석하면 \left \lceil P_{i+1}(L) \right \rceil - \left \lfloor P_{i}(L) \right \rfloor이 된다는 것을 알 수 있습니다.

     

    또, 수직선에서 0보다 왼쪽에 있는 점을 0에 대응되고, 8보다 오른쪽에 있는 점이 8에 대응된다고 한 것은 직선 L이 체스판을 이루는 가로 선분과 만나지 않게 되는 경우에도 이 식이 성립하게 만들려고 한 것입니다. 

     

     

    이 공식을 이용하면, 직선 L은 

    \sum_{k=1}^{n+1} \left \lceil P_{k+1}(L) \right \rceil - \left \lfloor P_{k}(L) \right \rfloor= \left \lceil P_{n+1}(L) \right \rceil - \left \lfloor P_{1}(L) \right \rfloor +\sum_{k=2}^{n}\left \lceil P_{k}(L) \right \rceil - \left \lfloor P_{k}(L) \right \rfloor

    개의 정사각형 칸과 만난다는 것을 알 수 있는데, 여기서 시그마 항은 n-1에서 <직선 L이 만나는 '정사각형 칸을 이루는 격자점들'의 개수>를 뺀 값과 같습니다.

     

    따라서, 직선 L이 만나는 칸의 개수는 오직 가장 위의 가로선과 만나는 위치, 가장 아래의 가로선과 만나는 위치, 만나는 격자점의 개수와만 상관있습니다. 또, 적당히 직선 L을 격자점과 만나지 않게 한다면 임의의 직선이 최대로 만날 수 있는 칸의 개수를 구할 수 있는데, 그 값은 n-0+n-1=2n-1개가 됩니다. (위 그로텐디크 님과 결과가 같네요. )

     

    어쨌든 이 식을 다양한 방식으로 해석하면 의미있는 결과가 나올 것 같고, 이 방법을 확장해서 이 문제를 조금 정수론 관련 문제로도 바꿀 수 있을 것 같습니다. 

    댓글 작성하기 좋아요0 댓글수0
  •  
    그로텐디크 Lv.5 2022.09.04 15:22 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    수냥이 Lv.5 2022.09.04 19:01

    우리는 n=2->2 n=3->3 n=4->4를 알 수 있습니다.

    n=x->y라고 하면 x>y가 되지 않음을 설명하면 되지 않나요?

    일단 x=y가 되는 이유는 그냥 사각형을 일자로 가로 지르면 되기 때문입니다.

    댓글 작성하기 좋아요1 댓글수7
    •  
      수학인재 Lv.3 2022.09.04 19:08 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      Funmaster Lv.7 2022.09.04 19:50

      그런데,힌트가 n=8->7인게 가능하다고 써있어요.

      좋아요0
    •  
      그로텐디크 Lv.5 2022.09.04 20:16 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      수냥이 Lv.5 2022.09.04 22:26

      @그로텐디크

      그 경우의 예시를 알려주세요

      좋아요0
    •  
      수냥이 Lv.5 2022.09.04 22:34

      그런데 제가 시도해 봤는데 계속 결과가 1개가 부족하더라구요

      좋아요0
    •  
      그로텐디크 Lv.5 2022.09.05 05:02

      n=3일때 2

      좋아요0
    •  
      Amath Lv.8 2022.09.05 15:47

      그리고 n=4->3입니다. 

      좋아요0
  •  
    다시 도전
    수학인재 Lv.3 2022.09.04 19:04 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      수냥이 Lv.5 2022.09.05 07:35 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      수학인재 Lv.3 2022.09.06 08:29 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      수냥이 Lv.5 2022.09.06 19:01 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    Amath Lv.8 2022.09.06 19:47

    여러 경우를 시도해 보니, 제 예상으로는 직선의 개수의 최솟값은 n-1 이하가 될 것으로 보이네요. 

    댓글 작성하기 좋아요0 댓글수1
    •  
      Amath Lv.8 2022.09.06 19:49

      n=1,2일 때를 제외하고, n=3,4,5,6일 때 직선을 n-1개 그려 모든 칸을 다 지나게 하는 것이 가능했습니다. 

      좋아요0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911