세 좌석을 고르되 고른 두 좌석이 이웃하지 않아야 한다. 방법 수와,20개 조합을 같은 확률로 선택할 때 조건을 만족할 확률을 구하라.
고른 번호를 a₁<a₂<a₃로 쓰면 a₂≥a₁+2, a₃≥a₂+2다. 새 번호를
로 놓으면1≤b₁<b₂<b₃≤4다. 따라서 방법 수는 C(4,3)=4다.
번호를 줄이는 대응이 되돌아가는가
반대로1~4에서 서로 다른 세 번호 b₁<b₂<b₃를 고른 뒤 aᵢ=bᵢ+(i−1)로 복원하면 사이가2 이상이고 마지막 번호도6 이하다. 서로 다른 선택이 같은 세 좌석으로 겹치지 않으므로 이 대응은 일대일이다.
실제 네 선택은(1,3,5),(1,3,6),(1,4,6),(2,4,6)이다. 같은 확률로 고른 전체 C(6,3)=20개 중 네 개가 남아 확률은1/5다.
고른 세 좌석 사이에 빈자리 두 개를 확보하여 번호의 허용 범위가6에서4로 줄었다. 각 좌석 사이 간격이 정확히2여야 한다는 조건은 아니다. 첫째와 둘째 간격이3인(1,4,6)도 허용된다.
문항을 준비할 때 일렬 좌석이라는 전제를 남긴다.1번과6번이 이웃하는 원형 좌석이면 위 네 목록에서 조건을 다시 확인해야 한다. 해설은 줄인 번호의 선택 수만 적지 않고 되돌리는 식까지 보여 주어, 필요 범위를 맞게 구한 뒤 실제 선택을 빠뜨렸는지 검산한다.
압축한 번호의 마지막 값은 최대4다. 서로 다른 세 번호를 고른 뒤 첫째는 그대로, 둘째에는1, 셋째에는2를 더하면 실제 자리로 돌아간다. 원래 자리의 최솟값·최댓값과 이웃하지 않는 조건을 복원하는 식으로 다시 확인한다.
출처·착안: Colleen Young, 「Systematic Listing Strategies」. 문항과 예시 답안은 새로 작성했다.