말랑말랑 수학문제 #12

<문제>

자연수 $n$ 은 $2$ 이상의 자연수이고 $n^2$ 개의 단위 정사각형을 가지고 있는 $n \times n$ 체스판을 생각하자. 체스판 위에 $n$ 개의 룩을 놓게 되는데, 모든 행과 모든 열에 정확히 한 개의 룩만 존재하면 "평화롭다"라고 하자.

"평화롭다"의 조건을 만족하는 $n$ 개의 룩을 어떻게 놓더라도, 어떠한 룩도 포함하지 않는 $k \times k$ 단위 정사각형이 항상 존재할 최대의 자연수 $k$ 를 구하여라. 

 

$1$
		$1$
	$1$
			$1$

 

위 그림은 $n = 4$ 일 때의 예시인데, 룩을 $1$ 이라고 생각하고 위처럼 배치하면 $n=4$ 일 때 $k=1$ 임을 알 수 있다.

 

-----풀이 스포를 주의하세요-----

 

 

 

 

 

 

 

 

 

 

<풀이>

일단 문제를 단순화 시켜서 $n$ 이 제곱수인 경우를 먼저 생각하자. $n = p^2$ 이라 하면, $k = p-1$ 임을 보일 것이다. $( p=2$ 인 경우가 위의 예시$)$

 

$k = p-1$ 임을 보이기 위해 우선 $(p-1) \times (p-1)$ 정사각형이 항상 존재함을 보일 것이다.

$p^2 \times p^2$ 정사각형에서 가능한 $(p-1) \times (p-1)$ 정사각형의 총수는 $(p^2-p+2)^2$ 개다. 각각의 룩에 대하여 룩이 포함될 수 있는 $(p-1) \times (p-1)$ 정사각형의 총수는 최대 $(p-1)^2$ 개다. 룩은 총 $p^2$ 개 존재하므로 룩이 포함된 $(p-1) \times (p-1)$ 정사각형의 총수는 최대 $(p-1)^2 \cdot p^2 = (p^2-p)^2$ 개다.

 

$p^2 \times p^2$ 정사각형에서 가능한 $(p-1) \times (p-1)$ 정사각형의 총수는 $(p^2-p+2)^2$ 개 이므로 무조건 룩이 포함되지 않은 $(p-1) \times (p-1)$ 정사각형이 존재한다. 방금과 아주 동일한 논리로 $n$ 이 증가할수록 $k$ 도 단조 증가한다는 사실도 보일 수 있다. (즉, $k$ 는 같아도 된다.)

 

$k = p$ 인 경우에 $p \times p$ 정사각형이 존재하지 않는 경우가 존재함을 보일 것이다.

실제 예시는 위에서 보여줬던 $4 \times 4$ 의 경우처럼 배치를 하면 된다.

제일 왼쪽, 제일 상단에 있는 칸을 $(1,1)$ 이라 하고 룩의 위치를 (몇 번째 행, 몇 번째 열)로 좌표를 표현한다면 다음과 같다.

 

첫 번째 행부터 $p$ 번째 행까지 : $\{(1,1), (2, p+1), (3, 2p+1), \cdots, (p, p(p-1)+1)\}$

$\vdots$

$1+pi$ 번째 행부터 $p(i+1)$ 번째 행까지 : $\{ (1+pi, i+1), (2+pi, i+1+p), \cdots, (p+pi, i+1+p(p-1)) \}$

$\vdots$

$1+p(p-1)$ 번째 행부터 $p^2$ 번째 행까지 : $\{ (1+p(p-1), p), (2+p(p-1), 2p), \cdots, (p^2, p^2) \}$

 

임의의 점을 중심으로 가장 인접한 점들의 $x$ 좌표들, $y$ 좌표들 차이의 절댓값이 모두 $p+1$ 보다 작게 구성되어 있기 때문에 $p \times p$ 정사각형이 존재할 수 없어 예시가 존재한다.

 

따라서 $n = p^2$ 일 때 $k = p-1$ 이고, $n = (p+1)^2$ 일 때 $k=p$ 가 성립하는데 $k$ 는 $n$ 에 따라 단조 증가하므로 $p^2 < m < (p+1)^2$ 인 자연수 $m$ 에 대해 $p-1 \leq k \leq p$ 가 성립한다.

 

$m = p^2+1$ 일 때 항상 $p \times p$ 정사각형에 룩이 존재한다면 1행에 놓인 룩의 열을 $j$ 번째 열이라고 가정하자.

세로로 긴 직사각형 $(p^2+1) \times p$ 직사각형을 생각할 것인데 행은 모두를 포함하는 것이고 열은 $\{j, j+1, \cdots, j+p-1\}$ 이라 하자. $(p^2+1) \times p$ 직사각형에는 $p \times p$ 정사각형이 총 $p^2-p+2$ 개 존재한다. 그럴 때 $(p^2+1) \times p$ 직사각형의 모든 $p \times p$ 에 포함된 룩을 세어보자. 하나의 룩당 최대로 포함될 수 있는 정사각형은 $p$ 개이고, 첫 번째 행에 있는 룩은 하나의 $p \times p$ 정사각형에만 포함 가능하므로 다음과 같은 부등식에 의해 모순이다.

 

$$ p^2-p+2 > 1+ p(p-1)$$

 

따라서 $m = p^2+1$ 일 때 $k \geq p$ 이므로 $k$ 의 단조 증가 성질에 의해 $p^2 < m \leq (p+1)^2$ 일 때 $k=p$ 를 만족한다. 그러므로 답은 $[x]$ 가 $x$ 를 넘지 않는 최대의 정수를 나타낼 때 다음과 같다.

답) $[\sqrt{n-1}]$