자연계열 4번

(1) 4개의 주민센터를 다음과 같이 설치하면 주어진 조건을 만족한다.

(2) 36개의 교차점을 위치에 따라 다음 세 가지로 나눌 수 있다.a) 외점 - 가장자리에 있는 점으로 모두 20개가 있다.b) 중간점 - 가장자리에서 한 칸 이내에 있는 점으로 12개가 있다.c) 내점 - 가장자리에서 두 칸 이내에 있는 점으로 모두 4개가 있다.

왼편 아래 꼭지점을 $\displaystyle (X_0,Y_0)$, 다른 교차점을 직교좌표 $\displaystyle (X_i,Y_j)$, $\displaystyle 0\le i,j\le5$ 로 표시하면,외점의 좌표는 $\displaystyle (X_i,Y_j)$, $\displaystyle i,j=0$ 또는 $\displaystyle 5$Comment. 외점은 격자의 가장 바깥 테두리에 있는 점이다. $\displaystyle (X_i,Y_j)$에서 $\displaystyle i$ 또는 $\displaystyle j$ 중 하나라도 $\displaystyle 0$이나 $\displaystyle 5$이면 외점이다. 그 안쪽 테두리의 점은 중간점, 가운데 네 점은 내점이다. 원문의 $\displaystyle i,j=0$ 또는 $\displaystyle 5$를 두 수가 모두 $\displaystyle 0$이나 $\displaystyle 5$여야 한다는 뜻으로 읽으면 안 된다.중간점의 좌표는 $\displaystyle (X_i,Y_j)$, $\displaystyle i,j=1$ 또는 $\displaystyle 4$내점의 좌표는 $\displaystyle (X_i,Y_j)$, $\displaystyle i,j=2$ 또는 $\displaystyle 3$

각각의 교차점은 2km 내에 있는 교차점의 수로 다음과 같이 세분화된다.(i) 외점의 경우 2km 내에 있는 교차점(외점, 중간점, 내점)의 개수: <5, 1, 0>, <5, 3, 1>, 또는 <5, 3, 0>(ii) 중간점의 경우 2km 내에 있는 교차점(외점, 중간점, 내점)의 개수: <5, 5, 1>, 또는 <4, 5, 3>(iii) 내점의 경우 2km 내에 있는 교차점(외점, 중간점, 내점)의 개수: <2, 7, 4>

=> 하나의 교차점이 (유형에 관계없이) 커버할 수 있는 외점의 수는 최대 5개이다.=> 외점 20개를 모두 커버하기 위해서는 적어도 4개의 주민센터가 필요하다.=> 이 경우, (i)의 <5, 3, 1>, <5, 3, 0>, <5, 1, 0>이거나, (ii)의 <5, 5, 1> 유형 중 선정해야 한다.=> 4개의 주민센터로 내점 4 곳을 커버해야 하므로, <5, 3, 0>과 <5, 1, 0> 유형은 선정할 수 없다.=> 따라서 8개의 <5, 3, 1> 유형의 외점과 <5, 5, 1> 유형의 중간점 중 네 곳을 선정해야 한다.

• <5, 3, 1> 외점과 <5, 5, 1> 중간점을 동시에 선정할 수 없다.예로, 하나의 <5, 3, 1> 유형 외점 $\displaystyle P=(X_2,Y_6)$를 선정한 경우, 중간점 $\displaystyle (X_1,Y_5)$, $\displaystyle (X_5,Y_5)$은 외점 $\displaystyle P$와 반경 2km 내에 외점 2개를 공통으로 갖게 되어 커버할 수 있는 총 외점의 수가 18개 이하가 된다. 따라서 $\displaystyle (X_2,Y_6)$와 동시에 선정될 수 있는 중간점은 $\displaystyle (X_1,Y_1)$이거나 $\displaystyle (X_5,Y_1)$이다. $\displaystyle (X_1,Y_1)$을 선정하면, 다른 외점 $\displaystyle (X_0,Y_2)$와 $\displaystyle (X_3,Y_0)$는 2km 이내에 공통 외점을 포함하므로 이 경우도 제외된다. 남은 중간점 $\displaystyle (X_5,Y_1)$와 외점 $\displaystyle (X_5,Y_3)$을 포함하여 4개를 선정해야 하는데, 이들 역시 반경 2km 이내에 공통점이 존재하여 조건을 만족할 수 없게 된다. 따라서, 외점에서 4개를 선정하거나, 중간점 4개를 선정해야 한다.Correction. 앞에서 정한 첨자 범위는 $\displaystyle 0$부터 $\displaystyle 5$까지이다. 이에 맞추면 이 문단의 $\displaystyle P=(X_2,Y_6)$은 $\displaystyle P=(X_2,Y_5)$로, 중간점 $\displaystyle (X_1,Y_5)$, $\displaystyle (X_5,Y_5)$, $\displaystyle (X_5,Y_1)$은 각각 $\displaystyle (X_1,Y_4)$, $\displaystyle (X_4,Y_4)$, $\displaystyle (X_4,Y_1)$로 읽어야 한다. 위쪽 두 중간점 $\displaystyle (X_1,Y_4)$, $\displaystyle (X_4,Y_4)$와 $\displaystyle P$가 반경 2km 내에 공통으로 갖는 외점은 각각 3개와 2개이므로, 두 점 모두 2개씩 공유한다는 설명도 맞지 않는다. 다만 적어도 2개의 외점이 겹치므로 이 중간점들을 $\displaystyle P$와 함께 선정할 수 없다는 결론은 그대로 성립한다. 최종적으로 제시한 세 배치에는 영향이 없다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.

1) 꼭지점에서 시계방향으로 두 칸 떨어진 외점 4 곳에 주민센터를 설치할 수 있다.이들 외점 $\displaystyle (X_0,Y_2)$, $\displaystyle (X_2,Y_5)$, $\displaystyle (X_5,Y_3)$, $\displaystyle (X_3,Y_0)$에 세운 주민센터는 2km이내에서 서로 다른 외점, 중간점, 내점을 (5, 3, 1)개씩 갖게 된다. 즉, 외점 20개, 중간점 12개, 내점 4개 모두를 커버한다.

2) 꼭지점에서 반시계방향으로 두 칸 떨어진 외점에 4 곳에 주민센터를 설치할 수 있다.이들 외점 $\displaystyle (X_0,Y_3)$, $\displaystyle (X_3,Y_5)$, $\displaystyle (X_5,Y_2)$, $\displaystyle (X_2,Y_0)$도 같은 이유로 조건을 만족한다.

3) 중간점 $\displaystyle (X_1,Y_1)$, $\displaystyle (X_1,Y_4)$, $\displaystyle (X_4,Y_1)$, $\displaystyle (X_4,Y_4)$에 주민센터를 설치할 수 있다.모든 교차로는 이들로부터 반경 2km 이내에 놓이게 되어 조건을 만족한다.

요약하면, 주어진 조건을 만족하는 4개의 주민센터는 다음의 세 경우이다.① 각 꼭지점에서 시계방향으로 2칸 떨어진 외점에 위치한다.② 각 꼭지점에서 반시계방향으로 2칸 떨어진 외점에 위치한다.③ 수직 경계선과 수평 경계선에서 한 칸 안으로 있는 중간점에 위치한다.