[알고리즘] L-트로미노

1. 트로미노란?

트로미노는 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형 이다.

따라서 다음과 같은 모양이 가능하다.

 

2. 트로미노로 구성된 불완전 보드 증명

트로미노중에서 L 모양의 트로미노를 한 변의 길이가 2^n인 정사각형에 배치하는 것이 목표이다. 

결론부터 말하자면,

L-트로미노는 1x1 한 칸을 제외하고, 한 변의 길이가 2^n인 정사각형을 항상 채울 수 있다.

 위 가정의 증명은 다음과 같이 수학적 귀납법으로 가능하다. 

 

1) Base 단계 (n = 1일때)

만약 n = 1 이면 2x2의 불완전 보드는 트로미노 자신이며, 하나의 트로미노에 의해 덮일 수 있다.

2) Step 단계 (n = k 일때)

n = k일 때, 즉 정사각형의 한 변이 2^k일 때, L-트로미노로 한 칸을 제외하고 모두 채울 수 있다고 가정하자.

n = k+1 일때 를 생각해보자.

n이 k+1이라면, 이전에 Step에서 만든 도형이 총 4개가 된다. 다음 그림과 같이 말이다.

왼쪽 하단의 사각형을 제외한, 나머지 사각형들을 합치면 하나의 L 트로미노로 매꿀수 있는 공간이 생긴다.

이 부분을 L 트로미노로 배꿔주면 k+1일때도 1x1짜리 타일만 남은 불완전 타일이 가능하다.

 

3) Result

base와 step이 둘다 증명되었기 때문에 P(n)은 모든 자연수 n에 대해서 참이다.

따라서 결과적으로, 수학적 귀납법에 의해서 위 정리는 모든 자연수 n에 대해서 항상 참이다.

 

참고

https://wogud6792.tistory.com/64  

[분할 정복] L-트로미노(L-Tromino) 타일링

http://www.aistudy.com/math/induction_johnsonbaugh.htm

수학적 귀납법 : Mathematical Induction