'2017/02'에 해당되는 글 6건

'소수의 제곱근은 유리수가 아니다'의 증명
$\sqrt{2}$가 무리수임은 매우 잘 알려져 있고, 그 증명 또한 매우 간단하다. 또한 이 증명법을 조금만 수정하면 임의의 소수 $p$에 대해서도 $\sqrt{p}$가 무리수임을 간단히 증명할 수 있다. 이번 글에서는 소인수분해의 유일성을 이용하여 임의의 소수 $p$에 대하여 $\sqrt{p}$가 무리수임 보이는 증명에 대해서 살펴보고자 한다. 먼저 산술의 기본정리(Fundamental Theorem of Arithmetic)이라고도 불리는 소인수분해의 유일성에 대해서 살펴보자. 정리. 산술의 기본정리(Fundamental Theorem of Arithmetic) $1$이상의 모든 정수 $n$은 소수이거나 소수들의 곱으로 표현 (즉, 소인수분해를) 할 수 있다. 이 때, 인수들의 곱하는 순서를 무시하..
Algebra/Arithmetic  |  2017. 2. 23. 04:29
Problems and Solutions #021
Problem #021 임의의 양의 정수 $n$에 대하여 $n$개의 연속한 합성수가 반드시 존재함을 보여라. 주어진 양의 정수 $n$과 양의 정수 $1 \leq k \leq n$에 대하여, $A_{n,k}$를 다음과 같이 정의하자. \[ A_{n,k} = (n+1)! + k + 1\] 만약 $A_{n,k}$가 모두 합성수임을 보일 수 있으면 증명이 완료된다. 이제 $A_{n,k}$를 정리하면 \[ A_{n,k} = (k+1) \left( \frac{(n+1)!}{k+1} + 1 \right) \] 위 식의 우변의 괄호 안의 식은 언제나 정수이고 $k+1 \geq 2$이므로, 모든 $1 \leq k \leq n$에 대하여 $A_{n,k}$는 합성수임을 알 수 있다.
Others/Olympiad  |  2017. 2. 23. 02:31
디랙의 정리(Dirac's Theorem)
어떤 마을에 $n$개의 집이 있다고 하자. 이제 이 마을에 어떤 집에 문제가 생겼을 때 각 집에 이 사실을 알릴 수 있는 비상연락망을 만들고자 한다. 이 때, 비상연락망이란 ABCDEA와 같이 순환적인 연락망 (이 때, 연락망이란 A가 B의 연락처를 알고 B 또한 A의 연락처를 아는 것을 뜻한다.) 이 존재하여 만일 집 C에 문제가 생겨도 DEAB 순으로 서로 연락이 가능해야 함을 뜻한다. 이러한 비상연락망을 만들기 위해서 각 집마다 다른 집의 연락처를 모두 알고 있다면 제일 이상적이겠지만, (비용 또는 보안의 문제 때문에) 각 집에서 알아야 하는 연락처의 개수를 최소화 하고 싶다. 이러한 상황에서 각 집은 최소한 몇개의 다른 집의 연락처를 알아야 할까? 만일 $n=5$라 가정해 보자. 만일 모든 집이 ..
Discrete Mathematics/Graph Theory  |  2017. 2. 21. 12:59
Problems and Solutions #020
Problem #020 방정식 $n^m = m^n$의 자명하지 않은 모든 양의 정수해를 구하여라. 우선 $n=m$이면 주어진 방정식이 성립함은 자명하다. 따라서 $n \neq m$을 가정하고, 편의상 $0 < n < m$이라 하자. 이제 주어진 방정식의 양변에 로그를 취하면 \[ m \log n = n \log m \quad \iff \quad \frac{\log n}{n} = \frac{\log m}{m} \] 을 얻는다. 이제 이 공통된 값을 $k$라 하면, 아래의 방정식 \[ f(x) := \frac{\log x}{x} = k \] 은 적어도 두개 이상의 서로 다른 근을 가져야만 한다. 하지만 $f'(x) = (1 - \log x)/x^2$이므로 함수 $f$는 구간 $(0,\, e)$에서 증가이고 ..
Others/High School Math  |  2017. 2. 18. 04:32
Problems and Solutions #019
Problem #019 평면 위의 집합 $S$에 대하여, $S$의 경계(boundary)가 평행한 두 직선이 될 때, 이 집합 $S$를 띠(strip)라 정의하자. 또한 $\abs{S}$를 이 평행한 두 직선 사이의 거리로 정의하자. 이제 평면 위의 띠들로 이루어진 수열 $(S_n)$에 대하여, 만약 $\sum_{n=1}^{\infty} \abs{S_n}$이 수렴하면 어떠한 $S_n$에도 포함되지 않는 점이 반드시 평면 위에 존재함을 보여라. $\sum_{n=1}^{\infty} \abs{S_n} = M$이라 하자. 이제 원점이 중심이고 반지름이 $R$인 원을 $B_R$이라 하자. 그러면 임의의 $S_n$에 대하여 $B_R \cap S_n$의 넓이는 언제나 $2R\abs{S_n}$보다 작아야 한다. 따라..
Analysis/Real Analysis  |  2017. 2. 17. 09:47
Problems and Solutions #018
Problem #018 어떤 나라에 유한개의 마을이 있다고 하자. 각각의 마을은 일방통행만이 가능한 길로 연결되어 있다. 또한 이 나라의 어떤 두 마을을 선택하더라도 한쪽 마을에서 다른쪽 마을로 가는 길이 존재한다고 하자. (제 삼의 마을을 거쳐서 가는것이 물론 허용된다.) 이 때, 이 나라의 모든 마을을 한번씩 거쳐갈 수 있는 길이 존재함을 증명하여라. 우선 문제를 수학적 용어로 다시 풀어 써 보자. $n$개의 마을을 $n$개의 점 $a_1,\, a_2,\, \ldots,\, a_n$이라 하고, 이 $n$개의 점으로 이루어진 완전유향그래프(complete digraph)를 생각하자. 이 때, $n$개의 점을 한번씩 모두 지나는 경로\[ a_{i_{1}} \rightarrow a_{i_{2}} \righ..
Discrete Mathematics/Graph Theory  |  2017. 2. 16. 11:52

티스토리툴바