d라이브러리

드디어 대망의 마지막 교시입니다.

확장판 커크먼의 여학생 문제는 ‘조합론적 디자인’의 난제인데요.

이 분야는 조건에 맞게 일정을 짜거나 조를 짜는 방법 등을 연구해요.

프로야구의 예시를 보고, 퀴디치 경기 일정을 짜세요.

각 프로야구 팀은 각자 속한 지역 즉, 연고지를 가져 두 팀이 경기할 때는 서로의 연고지 중 한 곳에서 경기를 치러요. 이때 한 팀의 총 경기에서 홈 경기 수와 원정 경기 수가 같으면서, 한 번 경기를 치른 팀과 연속해서 세 경기를 치르도록 경기 일정을 짜야해요. 예를 들어 A, B, C, D팀이 있다면 화, 수, 목요일엔 A와 B, C와 D가 연달아 세 경기를 하고 경기장을 이동해서 금, 토, 일에는 A와 C, B와 D가 맞붙지요. 이때 최대한 짧은 거리를 이동해야 체력 소모가 적고 비용도 절약할 수 있어요. 이렇게 고려할 점이 많아 미국과 캐나다의 프로야구인 메이저리그에서는 수학을 이용해 일정을 짜는 전문 기업이 따로 있다고 알려져 있어요.

2013년에는 일본 프로야구 일정에 관한 연구도 발표됐어요. 리처드 호시노 캐나다 퀘스트대학교 수학과 교수와 가와라바야시 겐이치 일본 정보과학연구소 교수는 일본의 프로야구에서 정규 시즌 동안 어떻게 경기 일정을 짜야 모든 팀의 이동 거리와 이동횟수를 가장 적게 만들 수 있는지를 계산했습니다.

연구팀은 이 문제를 그래프 문제로 바꿔서 생각했어요. 먼저 한 팀이 상대팀과 연속 세 경기를 치루는 것을 한 차수로 봤을 때 1차에서 나올 수 있는 팀 조합의 경우를 모두 점으로 표현했어요. 만약 4개의 팀이라면, 홈과 원정까지 따졌을 때 12가지(오른쪽 참고)의 팀 조합이 나와요. 각 조합을 그래프의 점으로 표현해 12개의 점을 찍었어요. 2차에서도 마찬가지로 조합 12가지 중 선택해야 하는데 ‘다음 차수에 연달아 같은 팀과 경기할 수 없다’, ‘홈 또는 원정 경기를 3번 이상 연달아 할 수 없다’ 등에 조건에 맞춰 1차 경기에 있는 점과 2차에 경기에 있는 점을 연결했습니다. 그렇게 40차 경기까지 모두 연결한 뒤 컴퓨터를 사용해 연결된 그래프의 이동 거리를 계산했어요.

그 결과 2010년의 프로야구 경기보다 이동 거리는 24.3%, 이동횟수는 14.6%나 적은 경기 일정을 찾아낼 수 있었답니다.

마지막 시험 문제를 풀어 마법학교에 입학하세요!

일본 연구팀의 연구를 참고해 퀴디치 경기 일정을 짜봅시다. 다음은 4개의 팀을 원정과 홈 경기를 구분해 맞붙는 팀 조합을 점으로 찍은 것입니다. 빨간색은 홈 팀, 검은색은 원정 팀이에요. 같은 팀과 연달아 경기할 수 없고, 3번 연달아 홈 또는 원정 경기를 할 수 없다면 어떻게 될까요?

선을 연결해 설명할게요. 1차에서 ①을 선택했다면 같은 팀과 연달아 경기할 수 없다는 규칙에 따라 2차에서는 ⑤~⑫가 가능해요. 2차에서 ⑧을 선택하면 홈 또는 원정 경기를 3번 연달아 할 수 없다는 규칙에 따라 B는 더 이상 홈 경기를 할 수 없어 3차에선 ⑨와 ⑪만이 가능해요. 이렇게 조건에 맞게 그래프를 그리는 겁니다.