리그전 대진표짜기 문제

  잠깐 토막상식. 토너먼트(tournament)란 경기 때마다 1:1로 싸워 승자는 올라가고, 패자를 제외시켜서 마지막에 남은 두 편으로 우승을 결정하게 하는 시합을 말하고, 리그전(league戰)은 여러 팀이 일정한 기간에 서로 같은 횟수만큼 시합하여 그 성적에 따라 순위를 결정하는 경기 방식을 말한다. 그런데 여기서 리그전이라는 말은 실은 콩글리쉬이다. 영어에서 리그전에 해당하는 말은 Round-robin tournament이다.

 

 

첫 번째 문제

 어느 도시에 아마추어 야구 팀이 5팀 생겼다고 한다. 이 야구팀들은 하루에 2번씩 총 5일동안 경기를 열어서 리그 순위를 매기고자 한다.

(리그 총 경기수는 5C2=10이고, 하루에 할 수 있는 최대 경기 수는 [n/2]=2이므로, 이는 타당한 설정이다.) 당연히 하루에 한 팀이 두 번 경기할 수는 없다. 이 때 이 리그전의 대진표는 어떻게 될 것인가?

 

 

두 번째 문제

 앞선 도시에 새로운 아마추어 야구팀이 하나 더 생겨서, 이제 총 6팀의 야구 팀이 있다. 이제 이 야구팀들은 하루에 3번씩 총 5일동안 경기를 열어서 순위를 매기고자 한다.(6C2=15, [n/2]=3, 15/3=5) 이 경우 리그전의 대진표는 어떻게 될 것인가?

 

 

출처 : Alan Tucker, Applied Combinatorics, wiley. p72-73 

참고 : http://en.wikipedia.org/wiki/Round-robin_tournament

 

 

 

 

해답

첫 번째 문제

1일 : B-E, C-D

2일 : A-C, D-E

3일 : A-E, B-D

4일 : A-B, C-E

5일 : A-D, B-C

 

두 번째 문제

1일 : A-F, B-E, C-D

2일 : A-C, B-F, D-E

3일 : A-E, B-D, C-F

4일 : A-B, C-E, D-F

5일 : A-D, B-C, E-F

 

 

 

 

아이디어

 이 문제의 아이디어는 완전그래프를 그리는 것이다. 완전그래프란 각 점(vertex)끼리 모두 선분(edge)을 그은 그래프로, 점이 n개인 완전그래프는 총 nC2=n(n-1)/2개의 선분을 가진다. 표기는 K_n(n은 K 오른쪽 아래에 작은 첨자로 쓴다.)

 

 

 

 

정오각형을 기반으로 이 완전그래프를 그리면 아름다운 오각별을 얻는다. (Pentagram이라는 상징이기도 하다.)

 

 

 각 점을 야구팀이라 하고, 선분을 각 팀끼리의 경기로 생각하자.  하루에 한 팀이 두 번 경기할 수 없다는 말은 두 선분이 하나의 점을 공유할 수 없다는 말이 된다. 두 선이 교차하지 않는다. 여기에서 우리는 평행선이라는 아이디어를 얻는다.

 

 

 

 

평행선 쌍을 5개 찾아냄으로써 원하는 대진표를 만들 수 있다.

 

 

 

 5 팀에 대한 대진표를 찾았으므로, 6팀에 대한 대진표는 누워서 떡먹기다. 5팀이 하던 경기에는 하루마다 늘 한 팀이 남았다. 위 예시의 경우 각 날마다 순서대로, A, B, C, D, E가 그날 경기를 쉬었다. 따라서 신생 야구단 F는 위 대진표를 유지한 생태에서 각 날마다 쉬는 팀과 하면 딱이다. 고로 5팀의 대진표에서 순서대로 A-F, B-F, C-F, D-F, E-F를 추가시키면 된다.