학술대회 세션 배치 - 제약 충족 추론
학술대회 조직위원회는 3일 동안 여섯 개 세션 A, B, C, D, E, F를 하루에 두 개씩 오전과 오후로 나누어 배치해야 한다. 다음 조건을 지켜야 한다. (1) A는 1일차 오전에 배치한다. (2) B는 C보다 앞선 날에 배치한다. (3) D와 E는 같은 날에 배치한다. (4) F는 3일차에 배치한다. (5) E는 오전에 배치하지 않는다. 한 사람이 두 세션을 맡는 경우는 없고, 하루에 같은 트랙의 세션이 두 번 배치되는 일도 없다. A와 D는 같은 트랙이고, 나머지 네 세션은 트랙이 서로 다르다. 조직위는 A를 1일차 오전으로 이미 확정했고 나머지 다섯 세션의 배치는 공개하지 않았다. 등록 안내문에는 ‘D의 날짜가 정해지면 먼저 알리겠다’고만 적혀 있다. 한 위원은 C가 3일차 오전에 들어갈 수 있는지 확인해 달라고 요청했고, 다른 위원은 ‘F가 C보다 앞선 날에 배치된다’는 조건을 추가하자고 제안했다. 지난해에는 조건 (2)를 뒤늦게 위반한 사실이 드러나 일정을 전면 재작성한 적이 있다.
1. D와 E가 배치될 수 있는 날을 정하고, 다른 날이 왜 불가능한지 배제법으로 서술하라. 그 결과 확정되는 나머지 세션의 위치도 밝혀라.
Read the worked answer
결론: D와 E는 2일차에만 배치될 수 있고, E는 2일차 오전, D는 2일차 오후다.
E의 성질부터 고정한다. 조건 (3)에 따라 D와 E는 같은 날이고, 조건 (5)에 따라 E는 오전이다. 즉 E가 오전에 놓이는 날이 곧 D·E의 날이다.
1일차 배제. 조건 (1)이 1일차 오전을 A로 채웠다. E가 1일차 오전일 수 없고, 1일차 오후에도 올 수 없다(오전이어야 하므로).
3일차 배제. 3일차에는 F가 반드시 들어간다(조건 4). 3일차의 두 자리는 오전·오후뿐이므로, E가 3일차 오전이라면 D가 3일차 오후로 가야 하고 F는 설 자리를 잃는다. 세 세션(D, E, F)이 두 자리에 들어갈 수는 없다. 따라서 3일차도 불가능하다.
2일차 확정. 남은 날은 2일차뿐이다. E는 2일차 오전, D는 2일차 오후로 확정된다.
나머지 세션. 이제 빈 자리는 1일차 오후, 3일차 오전, 3일차 오후이고 여기에 B, C, F가 들어간다. F는 3일차(조건 4)다. B가 3일차라면 C는 그보다 뒤의 날이어야 하는데 3일차 뒤에는 날이 없다. 따라서 B는 1일차 오후이고, C는 3일차다.
결과적으로 A(1일차 오전), B(1일차 오후), E(2일차 오전), D(2일차 오후)가 확정되고, C와 F만 3일차의 오전·오후를 나누어 갖는다.
2. C가 3일차 오전에 배치되는 것이 가능한가? 가능하다면 조건을 모두 만족하는 전체 배치를 제시하고, 불가능하다면 그 이유를 밝혀라.
Read the worked answer
결론: 가능하다. 두 가지 배치가 모두 성립한다.
앞서 확정된 바는 A(1일차 오전), B(1일차 오후), E(2일차 오전), D(2일차 오후)다. 3일차의 두 자리를 C와 F가 나눠 가지면 되고, 조건 (4)는 F가 3일차이기만 하면 충족된다. C의 날짜에 관한 조건은 (2) “B가 C보다 앞선 날”뿐인데, B가 1일차이므로 C가 3일차이기만 하면 언제나 충족된다.
배치 1
- 1일차 오전 A / 1일차 오후 B
- 2일차 오전 E / 2일차 오후 D
- 3일차 오전 C / 3일차 오후 F
배치 2
- 1일차 오전 A / 1일차 오후 B
- 2일차 오전 E / 2일차 오후 D
- 3일차 오전 F / 3일차 오후 C
검토. 배치 1에서 C는 3일차 오전이고, 요청받은 질문에 대한 답은 ‘가능하다’이다. 두 배치 모두 조건 (1)~(5)를 위반하지 않는다. A와 D는 서로 다른 날이므로 ‘같은 날 같은 트랙 금지’도 문제되지 않는다.
함의. 따라서 3일차 오전 자리에 관해서는 C와 F 중 누가 오는지가 조건만으로 결정되지 않는다. 조직위가 등록 안내문에서 D의 날짜만 먼저 알리겠다고 한 것은, 이 미결정 지점을 드러내지 않으려는 선택으로 읽을 수 있다.
3. ‘F가 C보다 앞선 날에 배치된다’는 조건을 추가하면 무엇이 새로 확정되는가? 추가 조건이 없다면 확정할 수 없었던 항목을 중심으로 설명하라.
Read the worked answer
결론: 3일차의 순서가 확정되어 전체 배치가 하나로 정해진다.
추가 조건의 작용 범위. 두 세션은 모두 3일차에 있으므로 ‘앞선 날’은 ‘앞선 시간대’, 즉 오전과 오후의 순서로 환산된다. F가 C보다 앞서려면 F가 3일차 오전, C가 3일차 오후여야 한다.
확정되는 항목. 추가 조건이 없을 때 미결정이던 것은 3일차 오전·오후의 C와 F의 배열이었다. 추가 조건이 이 두 자리를 하나로 고정한다. 나머지 네 세션(A, B, E, D)의 위치는 이미 확정되어 있었으므로 영향을 받지 않는다.
최종 배치. 1일차 오전 A, 1일차 오후 B, 2일차 오전 E, 2일차 오후 D, 3일차 오전 F, 3일차 오후 C.
왜 유일해가 되는가. 추가 조건 이전의 해는 두 개였다. 새 조건은 그중 하나만 남기므로 해의 수가 1로 줄어든다. 즉 새 조건은 ‘제약을 하나 더한 것’이 아니라 ‘남은 선택지를 절반으로 자른 것’과 같다.
실무적 함의. 조건이 하나 늘어나면 일정이 경직된다. 발표자 변경이나 세션 추가 요청이 들어올 때 조정 여지가 사라지므로, 조직위는 이런 유형의 조건을 추가할 때 확정성과 유연성 사이의 교환을 감수해야 한다.