말랑말랑 수학문제 #13

<문제>

$5 \times 5$ 정사각형 판을 $3 \times 1$ 직사각형 타일 $16$ 개로 덮으려고 한다. 각 타일은 $5 \times 5$ 정사각형 판에서 $3$ 개의 정사각형을 덮고, 각각의 $25$ 개 정사각형들은 한 개 혹은 두 개의 $3 \times 1$ 직사각형 타일로 덮이는 것이 불가능함을 보여라. (단, $3 \times 1$ 직사각형 타일은 $5 \times 5$ 정사각형 판에 수평적 또는 수직적으로 배열이 가능하다.)

 

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

 

 

 

 

 

 

 

 

 

 

<풀이>

귀류법을 사용하기 위해 각각의 $25$개 정사각형들은 한 개 혹은 두 개의 $3 \times 1$ 직사각형 타일로 덮이는 것이 가능하다고 가정하자. 그랬을 때 $5 \times 5$ 정사각형 판에서 각각의 정사각형 칸들에서 몇 개의 $3 \times 1$ 직사각형 타일로 덮이게 되는지 카운팅을 해보자. 

 

$25$ 개의 정사각형 칸들에 대해 $1$ 번 덮인 칸들을 $k$ 개, $2$ 번 덮인 칸들을 $25-k$ 개라 하자. 각각의 칸들에 대해 칸을 덮는 $3 \times 1$ 직사각형들을 중복을 허용하여 세어보면 $1 \cdot k + 2 \cdot (25-k) = 50 - k$ 개다. 반대로 각각의 직사각형 타일들은 3개의 칸들만 덮으므로 $50-k = 3 \cdot 16$ 이 되어 $k = 2$ 라는 사실을 얻게 된다.

 

이제 $5 \times 5$ 정사각형 판을 '컬러링' 할 것인데 3가지의 색깔을 2가지의 방식으로 칠해볼 것이다. 여기서 색깔은 편의상 $1, 2, 3$ 으로 하겠다.

 

첫 번째 방법)

 

$1$	$2$	$3$	$1$	$2$
$3$	$1$	$2$	$3$	$1$
$2$	$3$	$1$	$2$	$3$
$1$	$2$	$3$	$1$	$2$
$3$	$1$	$2$	$3$	$1$

 

위와 같은 방식으로 칠하게 되면 어떤 식으로 $3 \times 1$ 직사각형 타일을 놓아도 $1, 2, 3$ 색깔들이 골고루 하나씩만 들어가게 된다. 풀이 초반에 증명한 바에 따르면 $2$ 개의 칸만 하나의 $3 \times 1$ 직사각형 타일에 덮이므로 $1$ 이 색칠된 칸 중에서 그 $2$ 개의 칸이 나와야 한다. $(\because$ $1$ 이 유일하게 다른 숫자들보다 하나 많다.$)$

 

두 번째 방법)

 

$1$	$2$	$3$	$1$	$2$
$2$	$3$	$1$	$2$	$3$
$3$	$1$	$2$	$3$	$1$
$1$	$2$	$3$	$1$	$2$
$2$	$3$	$1$	$2$	$3$

 

앞선 경우와 동일하게 위와 같은 방식으로 칠하게 되면 어떤 식으로 $3 \times 1$ 직사각형 타일을 놓아도 $1, 2, 3$ 색깔들이 골고루 하나씩만 들어가게 된다. $2$ 개의 칸만 하나의 $3 \times 1$ 직사각형 타일에 덮이므로 $2$ 가 색칠된 칸 중에서 그 $2$ 개의 칸이 나와야 한다. $(\because$ $2$ 가 유일하게 다른 숫자들보다 하나 많다.$)$

 

첫 번째 방법과 두 번째 방법의 결론을 종합해보면 첫 번째 방법에서 $1$ 이 있던 위치와 두 번째 방법에서 $2$ 가 있던 위치의 교집합에 $3 \times 1$ 직사각형 타일이 한 번만 덮이는 $2$ 개의 칸이 나와야 한다. 따라서 두 방법의 결과를 $5 \times 5$ 에 동시에 색칠해보면 아래와 같다.

 

$1$	$2$		$1$	$2$
$2$	$1$		$2$	$1$
		$1,2$
$1$	$2$		$1$	$2$
$2$	$1$		$2$	$1$

 

두 방법의 결과를 교집합 해봤을 때 $1$ 칸만 겹치게 되어 모순이다. $\blacksquare$