퀴즈 313 친구와 적
어떤 왕국에 n 명의 기사가 살고 있다. 각 기사들은 서로 친구이거나 적이다.
그리고 각 기사들은 정확히 3명의 적을 가지고 있다고 한다.
만약 이 왕국이 "친구의 적은 나의 적이다" 라는 법에 의해 지배된다면
가능한 n 의 값은 몇명인가
풀이
여러 방법이 있겠지만[그래프 이론을 이용해서 멋있는 용어를 써서 보일 수도 있겠지만] 그냥 그려보는게 가장 쉽다.
각 기사별로 정확히 적을 3명을 가지고 있으니까 n=1,2,3 은 그릴 수 없다. n=4 부터 그려보자.
n=4 일 때는 모든 기사가 적이면 그릴 수 있다.
n=5 일 때는
먼저 기준을 정하고
친구는 연결하자, 그러면
모순이 생긴다.
n=6 이면
n이 7이상이면
기준이 정한 3명의 적 빼고는 나머지 모두가 친구가 된다.
친구의 적은 나의 적이니까 저 나머지 친구들의 적은 저 3명으로 할당할 수 있다. 문제는 저 3명의 적의 적을 할당하는 과정에서 일어난다.