[SW Expert Academy] Computational Thinking 논리와 증명 / 수와 표현 문제풀이 (3)

Sw Expert Academy : Computational Thinking - 논리와 증명, 수와 표현 (링크)

귀류법??

어떤 주장에 대해 그 함의하는 내용을 따라가다보면 이치에 닿지 않는 내용 또는 결론에 이르게 된다는 것을 보여서 그 주장이 잘못된 것임을 보이는 것

유의어 : 반증법 / 간접증명법 / 모순에 의한 증명

(위키백과-귀류법)

문제 풀이

문제 15 : 유리수와 무리수의 합은 무리수임을 증명하라

• 어떤 유리수 a와 무리수 b의 합이 유리수 c가 된다고 가정한다
• a+b = c, b = c-a인데 c-a는 유리수의 성질에 의해 유리수여야 하지만 이는 가정에 모순된다
• 따라서 유리수와 무리수의 합은 무리수이다

문제 16 : $\sqrt{2}$는 무리수임을 증명하라

• $\sqrt{2}$가 유리수라 가정하고 이를 기약분수로 나타내면 $b/a$이고 $a$와 $b$는 서로소이고 $a$는 0이 아니다
• 양 변을 제곱하면 $2=b^2/a^2$ , $2a^2=b^2$이다
• $b^2$이 짝수이므로 $b$도 짝수이고 이를 $2c$로 나타내면 $2a^2=4c^2$이 된다
• 따라서 $a^2$이 짝수이므로 $a$도 짝수가 된다
• $b/a$는 기약분수이기 때문에 $a$와 $b$는 서로소가 되어야 하지만 $a$도 짝수이고 $b$도 짝수이기 때문에 이는 가정에 모순된다
• 따라서 $\sqrt{2}$는 무리수이다

문제 17 : $log2(5)$는 무리수임을 증명하라

• $log2(5)$가 유리수라고 가정하면 이를 기약분수 $b/a$로 나타낼 수 있다
• $log2(5)=b/a$ 는 $5^a=2^b$로 나타낼 수 있다
• 홀수 $\not =$ 짝수 이기 때문에 가정에 모순된다
• 따라서 $log2(5)$는 무리수이다

문제 18 : 1+2+3...+n = n(n+1)/2 임을 증명하라

• n = 1일 때 양변은 1로 성립한다
• n = k일 때 성립한다 가정하면 1+2+3..+k = k(k+1)/2이다
• 양 변에 k+1을 더하면 1+2+3...k+(k+1) = (k^2 + 3k + 2)/2가 되고 우변을 정리하면 (k+1)(k+2)/2이다
• 따라서 n = k+1일 때도 등식이 성립하므로 1+2+3...+n = n(n+1)/2 이다

문제 19 : $1^2+2^2$..$+n^2=n(n+1)(2n+1)/6$임을 증명하라

• n = 1일 때 양변은 1로 성립한다
• n = k일 때 성립한다 가정하면 $1^2+2^2$..$+k^2=k(k+1)(2k+1)/6$이다
• 양 변에 $(k+1)^2$을 더하면 $1^2+2^2$..$k^2+(k+1)^2=k(k+1)(2k+1)/6+(k+1)^2$이 되고 우변을 정리하면 $(k+1)(k+2)(2k+3)/6$이다
• 따라서 n = k+1일 때도 등식이 성립하므로 $1^2+2^2$..$+n^2=n(n+1)(2n+1)/6$이다

문제 20 : $r \not = 1$일 때 $\sum_{i=0}^{n}r^i=(r^{n+1}-1)/(r-1)$임을 증명하라

• n = 0일 때 양 변은 1로 성립한다
• n = k일 때 성립한다 가정하면 $\sum_{i=0}^{k}r^i=(r^{k+1}-1)/(r-1)$이다
• 양 변에 $r^{k+1}$을 더하면 $\sum_{i=0}^{k+1}r^i=(r^{k+1}-1)/(r-1)+r^{k+1}$이고 우변을 정리하면 $(r^{k+2}-1)/(r-1)$이다
• 따라서 n = k+1일 때도 등식이 성립하므로 $r \not = 1$일 때 $\sum_{i=0}^{n}r^i=(r^{n+1}-1)/(r-1)$이다

문제 21 : 2 이상의 모든 자연수 n에 대해 $n^3-n$은 6으로 나누어 떨어짐을 증명하라

• $n^3-n=n(n+1)(n-1)$이다
• n = 2일 때 $2*3*1$ 이므로 6으로 나누어 떨어진다
• n = k일 때 k-1, k, k+1은 연속하는 수로 짝수를 포함하고 3의 배수를 포함한다
• 따라서 6으로 나누어 떨어지기 때문에 모든 자연수 n에 대해 6으로 나누어 떨어진다

문제 22 : 2 이상의 모든 자연수 n에 대해 $\sqrt{n}<\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}}$임을 증명하라

• n = 2일 때 $\sqrt{2}<1+\frac{1}{\sqrt{2}}$ 로 성립한다
• n = k일 때 성립한다 가정하면 $\sqrt{k}<\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}$이다
• 양 변에 $\sqrt{k+1} - \sqrt{k}$를 더하면 $\sqrt{k+1}<\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\sqrt{k+1} - \sqrt{k}$이고 우변을 정리하면 $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{1}{\sqrt{k+1}+\sqrt{k}}$이다
• n = k+1일 때 좌변은 $\sqrt{k+1}$로 위의 식과 같지만 우변은 $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{1}{\sqrt{k+1}}$로 다르다
• 하지만 $\frac{1}{\sqrt{k+1}}$이 $\frac{1}{\sqrt{k+1}+\sqrt{k}}$보다 크기 때문에 부등식이 성립한다
• 따라서 2 이상의 모든 자연수 n에 대해 성립한다

문제 23 : n X n 체스판이 있고 시작 시점에 일부 칸 들이 감염되어있다. 매초마다 감염이 증가할 수 있다. 규칙은 다음과 같다. 어떤 감염되지 않은 칸은 상하나 좌우로 인접한 네개의 칸들 중 2개 이상이 감염된 상태일 때 감염된다. 이 규칙에 따라 모든 칸들을 감염시키기 위해서는 초기에 n개 이상의 칸들이 감염되어 있어야 함을 증명하라

• 감염된 칸을 대각선에 최소 n개 놓은 후 모든 칸에 퍼지는 것을 나타내면 n * n = n + 2((n-1)+(n-2)+..+1)이다
• n = 1일 때 1개 이상의 칸이 감염되므로 성립한다
• n = k이고 초기에 k개의 칸이 감염되어 있을 때 성립한다 가정하면 k * k = k + 2((k-1)+(k-2)+..+1)이다
• 양 변에 2k+1을 더하면 $k^2+2k+1 = k + 2((k-1)+(k-2)+$..$+1)+2k+1$이고 우변을 정리하면 $(k+1)+2(k+(k-1)+(k-2)+$..$+1)$이다
• 따라서 n = k+1일 때도 성립하므로 모든 n에 대해 성립한다

추가

• n X n 체스판에 k개가 감염되어있을 때 감염시킬 수 있는 최대 칸 개수는 $k^2$이다
• n X n 체스판에 n-1개 이상 감염되어 있을 때 성립한다 가정하면 감염시킬 수 있는 최대 칸 개수는 $n^2 -2n + 1$ 이다
• $n^2 > n^2 -2n +1$ 이므로 n-1개 이상 감염되어 있을 때 모든 칸을 감염시킬 수 있다는 가정에 위반한다
• 따라서 모든 칸을 감염시키기 위해서는 n개 이상 칸들이 감염되어 있어야 한다