jjycjn's Math Storehouse

어떤 마을에 $n$개의 집이 있다고 하자. 이제 이 마을에 어떤 집에 문제가 생겼을 때 각 집에 이 사실을 알릴 수 있는 비상연락망을 만들고자 한다. 이 때, 비상연락망이란 ABCDEA와 같이 순환적인 연락망 (이 때, 연락망이란 A가 B의 연락처를 알고 B 또한 A의 연락처를 아는 것을 뜻한다.) 이 존재하여 만일 집 C에 문제가 생겨도 DEAB 순으로 서로 연락이 가능해야 함을 뜻한다. 이러한 비상연락망을 만들기 위해서 각 집마다 다른 집의 연락처를 모두 알고 있다면 제일 이상적이겠지만, (비용 또는 보안의 문제 때문에) 각 집에서 알아야 하는 연락처의 개수를 최소화 하고 싶다. 이러한 상황에서 각 집은 최소한 몇개의 다른 집의 연락처를 알아야 할까? 만일 $n=5$라 가정해 보자. 만일 모든 집이 ..

Problem #018 어떤 나라에 유한개의 마을이 있다고 하자. 각각의 마을은 일방통행만이 가능한 길로 연결되어 있다. 또한 이 나라의 어떤 두 마을을 선택하더라도 한쪽 마을에서 다른쪽 마을로 가는 길이 존재한다고 하자. (제 삼의 마을을 거쳐서 가는것이 물론 허용된다.) 이 때, 이 나라의 모든 마을을 한번씩 거쳐갈 수 있는 길이 존재함을 증명하여라. 우선 문제를 수학적 용어로 다시 풀어 써 보자. $n$개의 마을을 $n$개의 점 $a_1,\, a_2,\, \ldots,\, a_n$이라 하고, 이 $n$개의 점으로 이루어진 완전유향그래프(complete digraph)를 생각하자. 이 때, $n$개의 점을 한번씩 모두 지나는 경로\[ a_{i_{1}} \rightarrow a_{i_{2}} \righ..

Problem #001 어떤 나라에 유한개의 마을이 있다고 하자. 각각의 마을은 일방통행만이 가능한 길로 연결되어 있다. 또한 이 나라의 어떤 두 마을을 선택하더라도 한쪽 마을에서 다른쪽 마을로 가는 길이 존재한다고 하자. (제 삼의 마을을 거쳐서 가는것이 물론 허용된다.) 이 때, 이 나라에 어떤 마을이 존재하여, 이 마을로부터 다른 모든 마을을 갈 수 있음을 증명하여라. 각 마을을 $a_1,\, a_2,\, \ldots,\, a_n$와 같이 나타내자. 또한 임의의 $k = 1,\,2,\, \ldots,\, n$에 대하여, $\abs{a_k}$를 마을 $a_k$ 로부터 갈 수 있는 모든 마을의 개수라 하자. 따라서 이 문제는 $\abs{a_k}=n$인 $k$가 존재함을 증명하는 문제와 같다. 이제 $k..