퀴즈 313 친구와 적

---

어떤 왕국에 n 명의 기사가 살고 있다. 각 기사들은 서로 친구이거나 적이다.

그리고 각 기사들은 정확히 3명의 적을 가지고 있다고 한다.

만약 이 왕국이 "친구의 적은 나의 적이다" 라는 법에 의해 지배된다면

가능한 n 의 값은 몇명인가

풀이

여러 방법이 있겠지만[그래프 이론을 이용해서 멋있는 용어를 써서 보일 수도 있겠지만] 그냥 그려보는게 가장 쉽다.

각 기사별로 정확히 적을 3명을 가지고 있으니까 n=1,2,3 은 그릴 수 없다. n=4 부터 그려보자.

n=4 일 때는 모든 기사가 적이면 그릴 수 있다.

n=5 일 때는

먼저 기준을 정하고

친구는 연결하자, 그러면

모순이 생긴다.

n=6 이면

n이 7이상이면

기준이 정한 3명의 적 빼고는 나머지 모두가 친구가 된다.

친구의 적은 나의 적이니까 저 나머지 친구들의 적은 저 3명으로 할당할 수 있다. 문제는 저 3명의 적의 적을 할당하는 과정에서 일어난다.