1. 귀류법
https://ko.wikipedia.org/wiki/%EA%B7%80%EB%A5%98%EB%B2%95
귀류법 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전.
ko.wikipedia.org
귀류법 : 명제의 부정이 맞다고 가정해서 명제가 모순임을 보이는 방법.
2. 문제
문제 15 : 유리수와 무리수의 합은 무리수임을 증명하라
- 어떤 유리수 a와 무리수 b의 합이 유리수 c가 된다고 가정한다
- a+b = c, b = c-a인데 c-a는 유리수의 성질에 의해 유리수여야 하지만 이는 가정에 모순된다
- 따라서 유리수와 무리수의 합은 무리수이다
문제 16 : 는 무리수임을 증명하라
- 가 유리수라 가정하고 이를 기약분수로 나타내면 이고 와 는 서로소이고 는 0이 아니다
- 양 변을 제곱하면 , 이다
- 이 짝수이므로 도 짝수이고 이를 로 나타내면 이 된다
- 따라서 이 짝수이므로 도 짝수가 된다
- 는 기약분수이기 때문에 와 는 서로소가 되어야 하지만 도 짝수이고 도 짝수이기 때문에 이는 가정에 모순된다
- 따라서 는 무리수이다
위 글로는 이해가 안될 수 있다. (본인 아님 ㅎ;;;)
a, b가 서로소가 아니라는 것을 볼 거다.
귀류법에 의해 a, b가 서로소인 정수라고 가정하고 모순을 찾자.
a, b는 서로소라고 가정했는데 둘 다 짝수가 나왔다. 모순이다.
즉, 유리수라고 가정했는데 말이 안되므로 무리수이다.
문제 17 : 는 무리수임을 증명하라
- 가 유리수라고 가정하면 이를 기약분수 로 나타낼 수 있다
- 는 로 나타낼 수 있다
- 홀수 짝수 이기 때문에 가정에 모순된다
- 따라서 는 무리수이다
문제 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 : ..임을 증명하라
- n = 1일 때 양변은 1로 성립한다
- n = k일 때 성립한다 가정하면 ..이다
- 양 변에 을 더하면 ..이 되고 우변을 정리하면 이다
- 따라서 n = k+1일 때도 등식이 성립하므로 ..이다
문제 20 : 일 때 임을 증명하라
- n = 0일 때 양 변은 1로 성립한다
- n = k일 때 성립한다 가정하면 이다
- 양 변에 을 더하면 이고 우변을 정리하면 이다
- 따라서 n = k+1일 때도 등식이 성립하므로 일 때 이다
문제 21 : 2 이상의 모든 자연수 n에 대해 은 6으로 나누어 떨어짐을 증명하라
- 이다
- n = 2일 때 이므로 6으로 나누어 떨어진다
- n = k일 때 k-1, k, k+1은 연속하는 수로 짝수를 포함하고 3의 배수를 포함한다
- 따라서 6으로 나누어 떨어지기 때문에 모든 자연수 n에 대해 6으로 나누어 떨어진다
문제 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을 더하면 ..이고 우변을 정리하면 ..이다
- 따라서 n = k+1일 때도 성립하므로 모든 n에 대해 성립한다
추가
- n X n 체스판에 k개가 감염되어있을 때 감염시킬 수 있는 최대 칸 개수는 이다
- n X n 체스판에 n-1개 이상 감염되어 있을 때 성립한다 가정하면 감염시킬 수 있는 최대 칸 개수는 이다
- 이므로 n-1개 이상 감염되어 있을 때 모든 칸을 감염시킬 수 있다는 가정에 위반한다
- 따라서 모든 칸을 감염시키기 위해서는 n개 이상 칸들이 감염되어 있어야 한다
[참고]
'CS 백엔드 > Computational Thinking' 카테고리의 다른 글
| [SWEA] Computational Thinking 논리와 증명/수와 표현 문제 (2) (0) | 2023.01.03 |
|---|---|
| [SWEA] Computational Thinking 논리와 증명/수와 표현 문제 (1) (0) | 2023.01.03 |
| [SWEA] SWEA Computational Thinking 프로그래밍과 논리/수학 (0) | 2023.01.02 |
