퀴즈 308 원탁의 기사
12명의 기사가 원탁에 앉아 있다.
기사 회의에서 다음 전쟁에 나갈 선봉 4명을 뽑으려고 한다.
인접하게 앉아 있는 사람은 함께 선출 될 수 없다고 할 때,
선봉을 뽑는 방법의 수는?
이 문제는 여러가지 풀이법이 존재한다. 여사건을 이용해서 푸는 방법과 직접 세서 푸는 방법이 있다.
풀이 1 여사건
전체 경우의 수는 12 C 4
인접하여 앉아 있는 사람은 함께 선출될 수 없다. 여사건으로 풀 거니까 2명이 인접할 경우, 3명이 인접할 경우, 4명이 인접할 경우를 고려하면 된다.
편의상 시계방향으로 1,2, ... 12 까지 번호를 붙이자.
1 ) 2명이 인접할 경우
- 두명만 인접할 경우
인접한 한 조 (1,2) 를 뽑았다고 하면, 나머지는 이웃하면 안되니까 3,12 를 제외한 8명 중에 인접한 경우를 빼면 된다. 즉 8C2 - 7C1 = 21 [인접한 두 사람을 한명 취급]
처음 (1,2) 인접한 두 조를 뽑을 경우의 수는 12 가지니까 전체 경우의 수는 12x21 = 252 가지이다.
- 이번엔 두명씩 두 조가 인접한 경우 OO x OO
시작은 앞부분과 똑같다. 인접한 한 조 (1,2) 를 뽑고, 거기서 12, 3을 제외한 8명 중에 인접한 조를 뽑는다. 처음 인접한 두 조를 뽑을 경우는 12 가지이고 인접한 조를 셀 경우는 7 가지, 거기다가 이 경우는 중복이 되니까 1/2 [ 처음에 (1,2) 를 뽑고 (4,5) 를 뽑는 것과 처음에 (4,5) 를 뽑고 (1,2) 를 뽑는 경우가 중복된다.] 즉 전체 경우의 수는 7x6=42
2 ) 3명이 이웃한 경우
(1,2,3) 을 뽑고 4, 12 를 제외한 나머지 7명 중 한명을 뽑을 경우의 수니까
처음 (1,2,3) 을 뽑을 경우의 수 12가지 [(1,2,3), (2,3,4) 이렇게 하나씩 shift 하는 것이라 전체 경우의 수는 12가지가 된다.] 각 경우마다 7개씩 있으니 총 경우의 수는 12x7=84
3 ) 4명이 이웃한 경우
(1,2,3,4) [(2,3,4,5) shift 총 12가지]
즉 전체 경우의 수는
풀이 2
위원으로 선출된 네 사람을 앉아있는 차례로, b1,b2,b3,b4 라 하고
인접한 두 선출 위원 사이의 간격을 c1+1, c2+1, c3+1, c4+1 이라 하자
그럼 c1+c2+c3+c4 = 12-4 =8 , c_i >=1
이 문제의 정수해의 갯수는 [사실 이러한 정수해를 구하는 방법은 일반적인 중복조합의 문제인데, 교육과정이 바뀌면서 이 부분이 빠졌다. 이런 정수해 문제는 칸막이 문제로 대체가능하다. ]
8개의 공 사이에 7곳 중 3곳을 선택하여 칸막이를 두는 경우의 수와 같다. 35 = 7C3
여기서 12명의 위원 중 b1 을 선택하는 방법이 12가지, b1,b2,b3,b4 의 순서가 서로 돌아가는 4가지는 같은 경우이니까