해당 문제를 풀다가 식 세우는것을 어떻게 해야 할지 몰라서 검색을 해보았는데 일부 풀이들에서 아이디어를 얻고 나름 증명?을 해봤습니다. 아직 하드 로직이 익숙하지 않고, 수학에 대한 지식이 얕아 조금 미숙합니다. 혹시 개선 사항이나 추가되어야 할 내용이 있다면 답글 부탁드려요:)
Problem 23. NxN 체스판이 있다. 시작 시점에 일부 칸 들이 감염되어 있다.
매초마다 감염이 증가할 수 있다. 규칙은 다음과 같다. 어떤 감염되지 않은 칸은
상하나 좌우로 인접한 네개의 칸들 중 2개 이상이 감염된 상태일 떄 감염된다.
이 규칙에 따라 모든 칸들을 감염시키기 위해서는 초기에 n개 이상의 칸들이
감염되어 있어야 함을 증명하라.
저는 이 문제를 수학적 귀납법을 통해 증명했습니다.
(m.blog.naver.com/PostView.nhn?blogId=jamogenius&logNo=221198859160&proxyReferer=https:%2F%2Fwww.google.com%2F 참고)
[수학적 귀납법]
어떤 명제가 참이 되려면 다음의 조건 포인트를 만족해야 한다.
해당 명제의 식을 F(n)이라고 했을 떄,
1. F(1)이 성립해야 합니다.
2. F(n) -> F(n+k) 이 성립해야 합니다.
2번 부분은 사실상 F(n + k)만 성립해도 해당 명제가 참이 됩니다.(이전 [컴퓨팅 사고] 참조)
1x1 체스판일 때,
최소 1개의 칸이 감염되어 있다면 (초항 1) 1x1 체스판이 전부 감염 됩니다.
2x2 체스판일 때,
X |
O |
O |
X |
최소 2개의 칸이 감염되어 있다면 (초항 2: O 2개), (2번째 2 x 1: X 2개)로 2x2체스판이 전부 감염됩니다.
3x3 체스판일 때,
ㅁ |
X |
O |
X |
O |
X |
O |
X |
ㅁ |
최소 3개의 칸이 감염되어 있다면 (초항 3: O 3개), (2번째, 2 x 2: X 4개), (3번째, 2 x 1: ㅁ 2개)로 체스판이 전부 감염됩니다.
(이렇게 대각선방향으로 최소한 감염됨.)
이를 일반화 해보면
NxN 체스판이 있을 때,
체스판의 모든 칸을 감염시키려면 최소 n개의 칸이 감염되어 있다면 (초항 n: O n개), (2번째, 2 x n -1개 감염), (3번째, 2 x n - 2개 감염)....
(n-1번째, 2 x 1개 감염)으로 체스판이 전부 감염됩니다.
이를 통해 F(n) = n + 2(n - 1) + 2(n - 2) + ... + 2(1)이라는 것을 알 수 있고 이는
전체 체스판을 감염시킨 식이므로 총 n^2이라는 결과값을 가져야 합니다.
F(n) = n + 2(n - 1) + 2(n - 2) + ... + 2(1) = n^2
F(n + k)일때 참인지 확인해보면, (k는 임의의 0이 아닌 정수, 저는 k = 1 로 했습니다, k로 놓고 해두 됨.)
F(n + 1) = (n + 1) + 2(n) + 2(n - 1) + ... + 2(1) = (n + 1)^2
=> (n + 1) + 2(n) + 2(n - 1) + ... + 2(1) = (n + 1)^2 (n + 1을 우항으로 이항)
= 2(n) + 2(n - 1) + ... + 2(1) = (n + 1)^2 - (n + 1) = n^2 + n (우항을 정리)
= 2(n) + 2(n - 1) + ... + 2(1)을 초항(a)이 0이고 공차(d)가 2인 등차수열의 합 공식 사용하여 정리
(등차수열 공식(n이 1부터 n-1까지의 수열의 합) => S(n) = n{ 2a + (n - 1)d) / 2 )
= 2(n) + S(n) = 2(n) + n(n - 1) = n^2 + n (좌항)
= n^2 + n(우항)
서로 같으므로 F(n + 1)은 참. 따라서 해당 명제는 참. 그러나 역이 참이므로 본 명제가 참이라고 보기는 어려움.!!!!!
(본명제, 모든 체스판이 감염 -> 최소 n개 이상의 체스판이 감염)
이같은 식을 작성한 이유는 해당 식을 세우는 방법과 어떻게 이런 결과까지 도달했는지를 나타내기 위함입니다.
풀이
명제가 NxN개의 체스판이 감염 -> 초기에 n개 이상의 체스판이 감염되어 있어야 함.
대우증명볍
초기에 n개 이상의 체스판이 감염되어 있지 않다. -> NxN개의 체스판을 전부 감염시킬 수 없음
명제 : 최소 n - 1개의 체스판이 감염되어 있다면 n x n의 체스판이 감염되지 않는다.
식 : (n - 1) + 2 x (n - 2) + 2 x (n - 3) + ... + 2(1) = n^2 (위와 동일)
=> 2 x (n - 2) + 2 x (n - 3) + ... 2(1) = n^2 - (n -1) (n - 1을 좌황으로 이항)
=> S(n - 1) = n^2 - (n - 1) (S(n) = (n - 1) { 2 x 0 + (n - 2)2 } / 2 = (n - 1)(n - 2)
=> n^2 - 3n + 2 < n^2 - n - 1 (전부 감염 못시킴!! 좌항이 우항보다 작음.)
해당 대우가 참이므로 본 명제는 참이다!!!
처음에 풀때는 대우증명법으로 증명한다는 생각을 못했습니다. :)