36명의 도적이 있다. 이들이 도적단을 결성하는데, 도적 한 명이 도적단을 한 번에 여러 개 가입할 수도 있고, 한 도적단에 있는 구성원은 서로가 친구라고 한다. 단, 어떤 도적이 가입하지 않은 도적단 각각에는 항상 적어도 한 명의 그 도적의 적이 있다. 이 때, 결성될 수 있는 도적의 최대 수는 얼마인가?(12점)
참고로 중학생 한 명이 3점 받은 게 최고점이었음 나머지는 전체 1위부터 시작해서 올 0점 받음
36명의 도적이 있다. 이들이 도적단을 결성하는데, 도적 한 명이 도적단을 한 번에 여러 개 가입할 수도 있고, 한 도적단에 있는 구성원은 서로가 친구라고 한다. 단, 어떤 도적이 가입하지 않은 도적단 각각에는 항상 적어도 한 명의 그 도적의 적이 있다. 이 때, 결성될 수 있는 도적의 최대 수는 얼마인가?(12점)
참고로 중학생 한 명이 3점 받은 게 최고점이었음 나머지는 전체 1위부터 시작해서 올 0점 받음
Toft는 뭐냐 올림피아드냐 경시냐 어디서 풀수있는거냐
ㄴTournament of the towns라고 한국에서의 정식 명칭은 '도시대항국제수학토너먼트'임
올림피아드이긴 한데 일반적인 올림피아드랑은 좀 문제 출제 방식이 다름
오타 수정:결성 될 수 있는 도적->결성될 수 있는 도적단
구성원이 같은 도적단이 여러개 있을수는 없는거지
ㄴ ㅇㅇ 그거도 조건
푼 거 같다. 3^12
문제가 n(>1)개의 정점으로 이루어진 그래프의 the number of maximal cliques의 최댓값을 물어보는거라면 Moon과 Moser의 유명한 정리에 의해서 3^{n/3} (n이 3의 배수인 경우), 4*3^{(n-4)/3} (n이 3으로 나눈 나머지가 1인 경우), 2*3^{(n-2)/3} (n이 3으로 나눈 나머지가 2인 경우) 임. 증명은 어렵지 않음.
그건 맞지만 그 정리를 증명하라는게 이 문제의 의미겠지 ㅋㅋ
다만 Moon-Moser theorem의 결과물을 묻는 문제라면, 누가 출제했는지는 몰라도 문제가 별로 좋아보이지는 않네. 문제가 창의적이지 않으니까. maximal independent set (MIS) 의 개수를 묻는것과 동치고, general한 그래프의 경우 Moon-Moser theorem이 잘 알려져있지만 특별한 그래프의 경우 (예를 들어서 grid라든지, planar graph라든지, minor-free graph라든지, 등등) 계수조합론의 연구주제 중 하나임.
http://m.dcinside.com/view.php?id=mathematics&no=231726&page=1