주말에 푸는 수학문제

 

비행정 8대가 2열(위쪽 줄과 아래쪽 줄)에 각각 4대씩, 총 8대가 대기하고 있다. 
각 줄의 양끝에는 신호등이 있어, 파란불이 켜진 해당 방향 끝에 있는 비행정 한 대가 출동한다. 
한 대가 출발하면 잠시 후 다시 4개의 신호등 중 하나가 파란불이 켜지고, 그쪽 끝의 비행정 한 대가 또 출동하는 과정을 반복한다. 

결국 8대의 비행정이 모두 출동할 때 가능한 출동 순서의 가짓수를 구하는 문제이다.

조건을 정리하면 다음과 같다.

위 줄에 비행정 A1, A2, A3, A4가 왼쪽에서 오른쪽으로 놓여 있고, 
아래 줄에 비행정 B1, B2, B3, B4가 왼쪽에서 오른쪽으로 놓여 있다고 하자
각 줄별로 왼쪽 끝 또는 오른쪽 끝 중 하나를 선택해 해당 끝의 비행정을 출동시킬 수 있다.
결국 A열 4대와 B열 4대, 총 8대를 모두 출동시킬 때 가능한 순서를 세는 것이다

중요한 점은 각 줄(위줄, 아래줄)은 모두 '데크(deque)'와 같은 구조로 생각할 수 있다. 
즉, 한 줄에 대해 왼쪽 끝 또는 오른쪽 끝에서만 순서대로 뽑아낼 수 있다.
단일 열(4대)에서 가능한 순서의 수

먼저 한 줄(예: A열)에서 A1, A2, A3, A4를 양 끝에서만 뽑아낼 때 만들 수 있는 순열의 가짓수를 생각해 보자

A열: [A1, A2, A3, A4]
첫 번째로 뽑을 수 있는 비행정은 A1(왼끝) 또는 A4(오른끝) 2가지 선택이 있다.
A1을 먼저 뽑았다고 가정하면, 남은 [A2, A3, A4]에서 다시 A2(왼끝) 또는 A4(오른끝)를 뽑을 수 있으며, 이런 식으로 끝까지 가면 가능한 패턴을 모두 나열하면 총 8가지가 나온다
대칭적으로 A4를 먼저 뽑는 경우 역시 8가지 중 절반인 4가지를 더 얻게 되고, 두 경우를 합하면 한 줄에서 나올 수 있는 순열의 가짓수는 총 8가지이다. (직접 나열해보면 중복 없이 8가지임을 확인할 수 있다.)
결론적으로 한 줄(4대)에서 '양 끝에서만 하나씩 꺼낼 때' 나올 수 있는 순열 패턴은 8가지이다.

두 열(A열과 B열)을 합쳤을 때

이제 위쪽 줄 A열에서 가능한 패턴이 8가지, 아래쪽 줄 B열에서도 같은 방식으로 가능한 패턴이 8가지이다. 
최종적으로 8대(A열 4대 + B열 4대)를 모두 출동시킬 때, A열에서 형성 가능한 8가지 패턴 중 하나와 B열에서 가능한 8가지 패턴 중 하나를 선택한 뒤, 이 두 패턴을 적절히 섞어(인터리빙) 최종 순서를 만들 수 있다.

A열의 가능한 순열: 8가지
B열의 가능한 순열: 8가지
각각 하나씩 선택하면 조합은 8 × 8 = 64가지 (A열 패턴 1개와 B열 패턴 1개를 선택하는 경우의 수)

이제 A열과 B열에서 정해진 각각의 패턴(예: A에 대한 어떤 1가지 구체적 순열, B에 대한 어떤 1가지 구체적 순열)을 어떻게 섞을 수 있을까?

A열에는 4개, B열에도 4개, 총 8개를 하나의 순서로 합치는 방법은, 
8개의 위치 중에서 A열의 4개를 어느 자리에 놓을지 결정하는 것과 같다. 
즉, 8칸 중 4칸을 A열 비행정 위치로 고르면, 나머지 4칸은 B열 비행정이 들어가는 식이며 이는 조합으로 C(8,4) = 70 가지이다 

즉, A열과 B열 각각에서 특정한 1가지 패턴을 골랐다면, 이를 섞는 방법은 70가지이다

따라서 총 경우의 수는
A열 패턴(8가지) × B열 패턴(8가지) × 두 패턴을 섞는 방법(70가지)
= 8 × 8 × 70
= 64 × 70
= 4480 가지