체스판 문제로 배우는 수학적 귀납법

자 요로케 생긴 체스판이 있다고 해봅시다. 이 체스판은 가로 8칸, 세로 8칸해서 총 64칸으로 이루어져 있습니다.

그리고 여러분들에게 ㄴ자 모양으로 생긴 3칸짜리 블록이 있다고 할게요. 아래 그림처럼 말이죠.

이 예시 그림에서는 ㄴ자 모양으로 뒀는데, 테트리스처럼 얼마든지 회전시켜도 괜찮습니다. ㄱ자 모양으로 둬도 괜찮단 의미지요.

자 그렇다면 이 ㄴ자 블록으로 8x8칸 체스판을 빠짐없이 겹치지 않게 모두 채울 수 있을까요?

물론 불가능합니다. 체스판은 총 64칸이고, ㄴ자 블록은 3칸인데 64는 3으로 나뉘지 않으니까요.

그렇다면 체스판에서 랜덤하게 한 칸을 딱 빼버린다면요? 한 칸을 빼버리면 63칸이 되겠지요. 그렇다면 ㄴ자 블록이 3칸이니까 체스판을 전부 덮을 수 있을까요?

예를 들어 이렇게 빨간색 칸이 빠졌다고 가정한다면?

물론 직접 해볼 순 있지만, 처음에 빠지는 칸의 경우의 수가 64개나 되니 너무 시간이 많이 잡아먹힐 것 같네요.

그럼 이 문제를 어떻게하면 쉽고 간단하게 해결할 수 있을까요?

수학자들은 가장 극단적으로 쉬운 경우를 먼저 가정합니다. 예컨대 2x2칸의 체스판을 떠올려 볼까요?

이 4칸 중에 한 칸을 지워보도록 하죠.

그렇다면 남은 칸은 ㄴ자 블록을로 채울 수 있을까요? 물론 가능합니다.

여기서 아무렇게나 한 칸을 빨간색으로 칠해 빼버리면, 나머지 3칸은 ㄴ자 블록으로 쉽게 채워넣을 수 있겠죠.

자 그렇다면 총 4x4칸의 체스판이라면 어떨까요?

예컨대 이번엔 저 빨간색 칸이 빠졌다고 가정합시다. 그렇다면 어떻게 해야 이 칸들을 채울 수 있을까요?

이 4x4 체스판은 2x2 체스판의 4개 묶음으로 볼 수 있습니다. 이렇게 말이죠.

보면 이 4개의 2x2 체스판 중 왼쪽 위에를 제외한 나머지 3개는 모두 4칸으로 꽉 차 있습니다. 좌상단 하나만 1칸이 부족한 상황이지요.

그렇다면 저희의 첫번째 ㄴ자 블록을 다음처럼 놔봅시다.

그러면 나머지 3개의 2x2 체스판도 ‘하나의 칸이 채워진 상태’가 되겠는군요!

그렇다면 나머지 칸들을 ㄴ자로 채울 수 있을까요? 물론이죠!

왜냐하면, 이 2x2 체스판에서 한 칸을 어떻게 제외한들 ㄴ자 블록으로 채울 수 있다는 것을 이미 보였기 때문입니다.

만약 처음 칸이 다른 곳에서 빠졌다면 어떨까요? 예컨대 이렇게 말이죠.

마찬가지로 가상의 선을 그어 4개의 2x2 체스판으로 쪼개어 준 뒤, 나머지 체스판에서 한칸씩을 ㄴ자 블록으로 채워주면 됩니다.

역시 1칸이 제외된 2x2 체스판들이 되니, 나머지 칸들도 ㄴ자 블록으로 전부 채워줄 수 있겠죠!

즉 요약하자면…

정리: 4x4 칸의 체스판에서 어느 한 칸이 제외되어도 ㄴ자 블록으로 채울 수 있다.

증명:

1. 가상의 선을 그어 4개의 작은 2x2 체스판을 상상한다.
2. 첫번째 ㄴ자 블록을 배치해, 나머지 3개의 정상 체스판도 1칸씩 없애준다.
3. 2x2 체스판 중 어느 한 칸을 없애도 ㄴ자로 채울 수 있음을 보였으니, 기존의 체스판도 ㄴ자로 채울 수 있다.
4. 이 방식은 처음에 제외된 칸이 어디든지 ‘항상’ 성립할 수 있다. 그러므로 4x4 칸에서 어느 칸이 없애지든, ㄴ자 블록으로 채울 수 있다.

즉 2x2 체스판에서 해당 성질이 성립한다는 것을 근거로, 4x4 체스판에서도 해당 성질이 성립한다는 것을 보인 것입니다.

그렇다면 원래 문제인 8x8은 어떨까요? 다시 원래 그림으로 돌아가보죠.

이 체스판을 ㄴ자 블록으로 채울 수 있을까요? 4x4 때의 경우와 마찬가지로, 이 체스판을 4개의 작은 4x4 체스판으로 쪼개줍니다.

그리고 빨간색 칸이 없는 나머지 3개의 작은 체스판에 걸치도록 ㄴ자 블록을 배치합니다.

그렇다면 이 나머지 칸들은 ㄴ자 블록으로 채울 수 있을까요?

물론 가능하죠. 왜냐하면 앞서 우리가 `4x4 체스판에서 어느 한칸이 없어지더라도 나머지 칸은 ㄴ자 블록으로 채울 수 있음'을 보였기 때문입니다.

즉 8x8 체스판에서도 이 성질이 성립하게 되는군요.

이 논지를 계속해서 확장시키면, 16x16에서도, 32x32에서도, 64x64에서도, 2^n x 2^n에서도 성립함을 보일 수 있습니다.

바로 이것이 수학적 귀납법의 핵심 아이디어죠.

2^n x 2^n 체스판에서 이 성질이 성립하는가? => 2^(n-1) x 2^(n-1) 체스판에서 성립한다면, 성립한다.

.

.

.

8 x 8 체스판에서 이 성질이 성립하는가? => 4 x 4 체스판에서 성립한다면, 성립한다.

4 x 4 체스판에서 이 성질이 성립하는가? => 2 x 2 체스판에서 성립한다면, 성립한다.

2 x 2 체스판에서 이 성질이 성립하는가? => 직접 해보니까 성립하더라.

그런고로 n이 몇이든 2^n x 2^n 체스판에서 이 성질은 성립한다.

오늘의 수학 이야기 끗.