최~~~~고로 인기!
용건만 간단히, 움짤은 한 번 더 생각
금병영에 상의하세요
야생의 이벤트가 열렸다
즐겨찾기
최근방문

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

정수론민수
24.02.29
·
조회 8008

 

자 요로케 생긴 체스판이 있다고 해봅시다. 이 체스판은 가로 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 체스판에서 이 성질은 성립한다.

 

오늘의 수학 이야기 끗.

댓글
침등학교
24.03.01
BEST
딱 여기까지 이해함
https://resources.chimhaha.net/comment/1709232752681-0njpe64dwox.jpg
펄펄끓는쭈펄
24.02.29
오오 재밌네요
칡하하
24.02.29
지식추
경고드립니다
24.02.29
신가하네요 ㅋㅋㅋㅋ
SATELLITE
24.02.29
체스판은 예시일 뿐 핵심은 수학적 귀납법이었군요
정수론민수 글쓴이
24.02.29
핵심맨 따봉추!
국밥부장관
24.03.01
아하 그런거군요 (이해못함)
pmghiz
24.03.01
학생 빨리 연구실적 가져와요
침등학교
24.03.01
BEST
딱 여기까지 이해함
https://resources.chimhaha.net/comment/1709232752681-0njpe64dwox.jpg
침착해도될까요
24.03.01
뺘나나우유
24.03.01
이제 침철단 옷만 생각남
대인국대표하남자
24.03.01
이야 재밌는데요??
위슬러
24.03.01
이 문제도 해결할 때 사람 수가 2명일 때부터 가정하던데, 저는 처음 볼 때 ‘오 이렇게 푸는 거구나’하고 넘어갔거든요.
그런데 이 게시물 보고나니까 이 문제의 해결법도 고등학교 때 배우는 수학적 귀납법이었다는 게 보이네요.
시야가 더 넓어진 것 같습니다 굳굳
정수론민수 글쓴이
24.03.01
아 저도 예전에 재밋게 본 영상입니다. 1명일 때의 경우를 기반으로 논리를 쌓아간다는 점에서 귀납법적인 접근이 눈에 띄네요!
곽싸울
24.03.01
이런 거 배우는 거 넘 재밌는데... 안타까운 건 응용을 못한다는거에요... 수학적 머리가 없어서인지
주황개굴
24.03.01
호옹 너무 재밌어오
침아크
24.03.01
이런거 개좋아
우와와앙
24.03.01
재밌어요!
별사람
24.03.01
수학자들 무한 리스펙!
두다리갈매기
24.03.01
머싯다... 학교에서 이렇게 생각하는 법을 배우고 싶었어요 고마워요 횐님
유인원
24.03.01
추억돋네요 ㅋㅋ 중학생때 영재원에서 했었는데

전체게시글 전체글

TWICE <THIS IS FOR> 월드 투어 파트1 발표 3
취미
쿤하로
·
조회수 132
·
4일전
르세라핌 'DIFFERENT' OFFICIAL MV
취미
토냥천사
·
조회수 161
·
4일전
풍전무님 근황 8
유머
꼬불이
·
조회수 3971
·
4일전
진짜 이세돌님한테 이런 질문 하는 사람은 침착맨이 유일할듯 12
침착맨
침태식
·
조회수 7049
·
4일전
뒤에서 개가 쫒아 오는 궤도.avi 1
침착맨
꼬불이
·
조회수 360
·
4일전
금병영티셔츠입고 달리는 인간
취미
고추사냥
·
조회수 265
·
4일전
침둥 딸기잼 포도잼 사과잼! 1
침착맨
청담동
·
조회수 331
·
4일전
침철단 광고에 나오는 한우 에너지 스틱이 뭔가 했더니 16
침착맨
생전존문가김병철
·
조회수 4259
·
4일전
이름이 언덕언덕언덕언덕인 언덕이 있는 줄 알았는데.... 2
유머
야채김밥
·
조회수 382
·
4일전
아일릿 ‘bomb’ 컨셉포토 (GLLIT Ver.)
취미
토냥천사
·
조회수 146
·
4일전
요리재료들끼리 싸움이붙었을때 최약체는? 3
유머
통모짜먹으면잠을통모짜
·
조회수 338
·
4일전
25.06.08. 침투부 일력👨‍⚖️
침착맨
정제탄수붕어
·
조회수 187
·
4일전
꺄악ㄱ가가가각가아아각가가가가아악‼️‼️‼️‼️‼️‼️
침착맨
덴져러스우먼댱잉
·
조회수 298
·
4일전
빠니 어디갔어?
유머
기저귀차고지리기
·
조회수 390
·
4일전
성대님 사전 인터뷰때 이미 침착맨님 지목하셨네
인방
치마하하
·
조회수 520
·
4일전
침둥에 귀한 분들 참 많이 나오셨네요 29
침착맨
썬더블러프차돌짬뽕진동토템
·
조회수 4946
·
4일전
전무님에게 복수 성공한 맛피자 10
침착맨
인저얼미
·
조회수 4566
·
4일전
힙한 K시장 짤 모음 9
알짤도
여섯시내고향
·
조회수 1193
·
4일전
냥이 벌써 더워하네 2
취미
호방한호빵맨
·
조회수 247
·
4일전
현대판 레미제라블
유머
와기와기
·
조회수 291
·
4일전