수학쟁이의 공부 이야기

$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$ 정사각형 판에서 각각의 정사각형 칸들에서 몇 개의 ..

$5 \times n$ 직사각형을 다음과 같은 두 종류의 타일로 빈틈없이 덮을 수 있을 때, $n$ 이 짝수임을 보여라. (단, 타일을 회전하는 것이 가능하다) -----풀이 스포를 주의하세요----- 귀류법을 통해 증명하기 위해 $n$ 이 홀수라고 가정하자. 우리의 문제와 같이 타일을 덮는 문제를 해결할 때 '컬러링'이라는 방법을 사용하는데 아래와 같은 방법으로 칠하겠다. 즉, $1,3,5$ 번째 행을 모두 검은색으로 칠하고 나머지를 모두 흰색으로 칠해보자. 이런 방식을 채택한 이유는 당연히 두 종류의 타일 모양 때문인데 어떻게 배치를 하더라도 두 가지 경우만 발생한다. 1. 검은색 타일 3개를 덮고, 흰색 타일을 2개를 덮는 경우 2. 검은색 타일 2개를 덮고, 흰색 타일을 3개를 덮는 경우 총 $n..