L-tromino tiling

트로미노란?

크기가 같은 정사각형 3개를 이어 붙여서 만든 다각형이다. 아래 그림과 같이 두가지의 트로미노가 존재한다.

---

$2^n \times 2^n$ L-tromino tiling

일자 모양이 아닌 'ㄴ' 모양의 트로미노를 한변의 길이가 $2^n$인 정사각형에 배치하는 것으로, 정사각형에서 $1\times 1$의 한칸을 제외한 모든 칸을 L-tromino로 채울 수 있다. 수학적 귀납법을 통해 증명할 수 있다.

증명

• n = 1일 때

• n = k일 때

• n = k + 1일 때
  3개의 부분 정사각형의 비어있는 각각의 $1\times1$ 칸을 큰 정사각형의 중앙으로 모일 수 있도록 회전시키면 L-tromino로 채울 수 있는 공간(노란색으로 표시된 공간)이 만들어진다. 결과적으로 한칸을 제외하고 모두 채울 수 있다.

수학적 귀납법에 따라서 위의 정리는 모든 자연수 n에 대하여 참이다.

---

관련 문제

백준 14601: 샤워실 바닥 깔기(Large)
https://www.acmicpc.net/problem/14601