Introduction to Theory of Computation 1장_2 문제풀이

문제 1.1 Use induction to prove that every integer n≥2 can be written as a product of prime numbers.

 - 해석 : n≥2인 모든 정수는 소수의 곱으로 이루어져 있음을 증명하라.

 - 증명 : 2≤n≤k 에서 자연수 k가 소수들의 곱으로 표현되어 있다고 가정한다.
          ⅰ) n이 소수이면, 2 ≤ n(소수) * 1 ≤ k 이므로 증명이 종료된다.
          ⅱ) n이 소수가 아니라면, n 역시 1을 제외한 약수 중에서 가장 작은 약수를 소수로 갖게 될 것이다.
                n=n₁ x p₁ x p₂ 처럼 n이 소수만 남을 때까지 이 과정이 반복되기에 
         ∴ 따라서 n≥2인 모든 정수는 소수의 곱으로 이루어져있다.


문제 1.2 For every prime number p, prove that √p is irrational.

 - 해석 : 모든 p가 소수에 대하여 √p가 무리수임을 증명하라.

 - 증명 : 모든 p가 소수일 때, √p가 유리수임을 가정한다.
           √p가 유리수 이므로 √p = m/n 으로 표현 가능하다. (n과 m은 서로소, n≠0)
      양변을 제곱하여, p = m²/n² 이다. 이때, p의 약수를 구할 수 있는데 1, m/n, m²/n² 이므로 p가 서로소라는 가정에 모순이 생긴다.
          ∴따라서 모든 p가 소수일 때, √p가 유리수이다.


문제 1.4 Prove by induction that n⁴-4n² is divisible by 3, for all integers n≥1.

 - 해석 : Induction을 이용하여 n≥1인 모든 정수에 대해, n⁴-4n² 가 3의 배수임을 증명하라.

 - 증명 :  ⅰ) n=1일 때, (1)⁴-4(1)² = -3 이므로 3의 배수이다.
                ⅱ) n=k일 때, (k)⁴-4(k)² = (k)⁴-(k)²-3(k)² = { (k)⁴-(k)² } -3(k)² = k²(k-1)(k+1) - 3k² 이므로
                       k²(k-1)(k+1) - 3k² 에서 k(k-1)(k+1) 가 3의 약수가 된다. 따라서 명제가 성립한다.
                ⅲ) n=k+1일 때, 4k(k-1)(k+1)+6k²-3 이 되므로 명제가 성립한다.
          ∴ⅰ,ⅱ,ⅲ 의 경우 모두 명제가 성립하기 때문에 위 명제는 참이다.

문제 1.6 Prove that 9 divides n³+(n+1)³+(n+2)³, for every integer n≥1.

 - 해석 : 모든 정수 n≥1에 대하여 n³+(n+1)³+(n+2)³이 9의 배수임을 증명하라.

 - 증명 :     ( ※필요한 공식 : a³+b³+c³ = 1/2 x (a+b+c) x [(a-b)²+(b-c)²+(c-a)²] + 3abc )
            1/2 x {n+(n+1)+(n+2)} x [(-1)²+(-1)²+(-2)²] + 3(n³+3n²+2n) 
            = 3(3n+3)+3(n³+3n²+2n) 
            = 9(n+1)+3n(n+1)(n+2)
          에서 n(n+1)(n+2)가 3의 배수되어 결과적으로 3n(n+1)(n+2) 식도 9의 배수가 되므로 명제가 성립한다.


문제 1.7 Prove that in any set of n+1 numbers from { 1,2 .... 2n }, there are always two numbers that are consecutive.
 
 - 해석 : {1, 2, ..., 2n} 중에서 임의로 n+1개의 수를 고르면 그중에는 꼭 연속된 두 수가 들어 있음을 증명하라.
 
 - 증명 : {1, 2, ..., 2n} 중에서 임의로 n+1개의 수를 고르면 그중에는 꼭 연속된 두 수가 들어있지 않다고 가정한다
               1부터 2n까지의 숫자 중에서 짝수만 n개를 고르면 나머지 하나는 홀수 하나를 초이스 해야한다.
               이때, 임의의 홀수는 반드시 n개의 짝수 중에서 연속하는 두 수가 있기 때문에 위의 가정은 거짓이다.
         ∴따라서 {1, 2, ..., 2n} 중에서 임의로 n+1개의 수를 고르면 그중에는 꼭 연속된 두 수가 들어있는 명제는 참이다.