주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[대한수학회] 대7. 무한바둑판에 바둑 두기

2017.07.01

같이 풀어볼까?

네이버밴드 구글플러스

 

수학 국가대표를 키우는 대한수학회의 일곱 번째 문제입니다. 

 

무한바둑판에 바둑돌 두기 

 

정수 n\geq 0에 대해 \left [ 0, n \right ]\times \left [ 0,n \right ] 상의 정수 격자점, 즉 집합 \left ( \left [ 0, n \right ]\times \left [ 0,n \right ] \right )\cap {\mathbb{Z}^2의 각 점 위에 흰색과 검은색의 바둑돌을 놓아둔 모양을 바둑돌 패턴이라 하고, 이러한 패턴들을 모아놓은 집합 \mathbb{S}를 생각하자. \mathbb{S}는 무한집합일 수도 있고, \mathbb{S} 안의 두 패턴이 크기가 같을 필요는 없다.

맨 왼쪽 아래가 $(0,0)$이고 오른쪽과 위로 무한히 긴 바둑판을 생각하자. 이 바둑판의 모든 교차점에 \mathbb{S} 안의 패턴들을 피해서 흰색과 검은색의 바둑돌을 놓으려고 한다. 이는 평면 1사분면 상의 정수 격자점 위의 각 점에 바둑돌을 놓는 것과 같다. 다음 조건을 만족하게 바둑판에 바둑돌을 놓았다면 이 모양을 '\mathbb{S}-회피모양'이라고 부르자.
    
"\mathbb{S}의 원소인 [0,n] \times [0,n] 바둑돌 패턴 각각에 대해, 이 패턴이 모든 정수 k에 대해 바둑판의 [k, k+n] \times [0,n] 위치에 나타나지 않는다."

 

다음은 가능한 집합 \mathbb{S}의 몇가지 예이다. 

바둑판의 맨 아랫줄, 즉 각 정수점 (m,0) (단, m \ge 0)에만 검은 돌을 놓은 모양은 모두 \mathbb{S}_1-회피모양이 됨을 알 수 있다. 비슷하게, 바둑판 아래에서 두 번째 줄, 즉 각 정수점 (m,1)(단 m \ge 0) 에 흰색 돌만 놓여있으면 다른 격자점에 어떤 색의 돌을 놓든지 \mathbb{S}_2-회피모양이 된다. 바둑판의 각 열마다 같은 색깔의 돌을 놓으면 \mathbb{S}_3-회피모양이 되는 것도 쉽게 확인할 수 있다.

위의 집합 중 \mathbb{S}_3은 다음 조건을 만족함을 관찰해 보자: 각 정수점 (m,0) (단, m \ge 0) 에 바둑돌을 놓고 나면 나머지 정수점에 바둑돌을 놓아서 \mathbb{S}_3-회피모양을 만드는 방법은 단 하나 뿐이다.
 

<지금부터 문제 나갑니다>

문제 0. 워밍업: 위의 \mathbb{S}_3을 변형하여, 각 자연수 K에 대해 다음 조건을 모두 만족하도록 집합 \mathbb{S}를 찾아라.
(a) 각 정수점 (m,n) (단, m \ge 0, 0 \le n \le K) 에 바둑돌을 놓고 나면 나머지 정수점에 바둑돌을 놓아 만들 수 있는 \mathbb{S}-회피모양은 한 개뿐이다.
                    
(b) 각 정수점 (m,n) (단, m \ge 0, 0 \le n \le K-1$) 에서는 놓는 방법이 같지만 나머지 정수점에서 놓는 방법이 다른 두 \mathbb{S}-회피모양이 존재한다.

 

 

문제 1. 다음 조건을 모두 만족하도록 집합 \mathbb{S}를 찾아라.

(a) 각 정수점 (m,n) (단, m \ge 0, 0 \le n \le K$) 에 바둑돌을 놓고 나면 나머지 정수점에 바둑돌을 놓아 만들 수 있는 서로 다른 \mathbb{S}-회피모양이 많아야 두 개뿐인 자연수 K가 존재한다.

(b) 임의의 자연수 L$에 대해, 각 정수점 (m,n)$ (단, m \ge 0, 0 \le n \le L$) 에서는 놓는 방법이 같지만 나머지 정수점에서 놓는 방법이 다른 두 \mathbb{S}-회피모양이 존재한다.
            
주의: 조건 (a)에서, 처음 놓는 방법에 따라 만들 수 있는 \mathbb{S}-회피모양이 없을 수도 있다.

 


문제 2. 문제 1의 조건을 만족하면서 다음 조건 역시 만족하도록 집합 $\mathbb{S}$를 찾아라.

 - 임의의 자연수 p에 대해, 다음 조건을 만족하는 p보다 크거나 같은 자연수 q가 존재한다.

"모든 자연수 k에 대해 바둑판의 [k, k+q] \times [0,q] 위치에 놓인 모양이 어떤 \mathbb{S}-회피모양의 일부(즉, 어떤 \mathbb{S}-회피모양[k, k+q] \times [0,q] 위치에 놓인 모양)가 되게 바둑돌을 놓으면, 각 정수점 (m,n) (단, m \ge 0, 0 \le n \le p)에서는 바둑돌을 그대로 두고 나머지 정수점에서는 바둑돌을 새로 놓아 만들 수 있는 \mathbb{S}-회피모양이 존재한다."

 

 

 

 

댓글 4

  • shine 2017.07.02 14:23:31

    문제0 

    \mathbb{S}= 적어도 한 "y좌표가 0~(K-1)인 점들을 제외한 열" 에서 흰 바둑돌, 검은 바둑돌이 둘 다 있는 패턴의 집합

    으로 하면 만족합니다.

    좋아요0 댓글수1
    • 좀좀 2017.07.23 08:17:24

      왜..죠...

      좋아요0
  • shine 2017.07.08 12:07:34

    문제 1

    음이 아닌 정수 n에 대하여 (0,0)에서 (n,0)까지와 x+y=n 직선이 지나는 점만 검은 돌, 나머지는 흰 돌로 배치하는 모양의 집합을 \mathbb{T} 라고 하자. 또, \mathbb{T}의 모든 모양에 대해 (0,n)만 흰색으로 바꾼 것을 \mathbb{U}라 하여  \mathbb{V}= \mathbb{T}\cup\mathbb{U}를 정의하자.

     그 어떤 \mathbb{V}에 속한 모양의 일부도 되지 않는 패턴의 집합을 \mathbb{S}라 하자. (즉 \mathbb{V}가 \mathbb{S}-회피모양이 되도록 정의하는 것이다.)

    이때 이 \mathbb{S}는 문제의 조건을 만족한다.

     

    좋아요0 댓글수0
  • shine 2017.07.19 18:35:14

    풀이의 이해를 위해 \mathbb{T},\mathbb{U},\mathbb{V}를 다음 그림을 통해 보여드리겠습니다.

    좋아요0 댓글수0