팀 나누기

1번부터 12번까지의 번호가 붙은 총 12명의 선수가 있다. 이 선수들을 6명씩 두 팀(A팀, B팀)으로 정확히 나누려 한다.

두 팀은 미리 정해진 다음과 같은 순서로 선수를 한 명씩 선발한다: A → B → B → A → A → B → B → A → A → B → B → A

각 팀은 자신의 차례가 왔을 때, 아직 선발되지 않은 선수들 가운데 가장 선호하는 선수를 선발한다. 각 팀의 선수 선호 기준은 아래와 같다.

• A팀: 번호가 더 작은 선수를 선호한다.
• B팀: 선수들에 대한 선호 순위를 나타내는 의 순열 를 가지고 있다. 각 에 대해, 번 선수는 전체에서 번째로 선호하는 선수이다. 즉, 의 값이 더 작은 선수 를 선호한다.

가능한 모든 가지의 순열 에 대해 위의 선발 규칙을 수행하여 두 팀(A, B팀)의 최종 구성을 결정할 때, 나올 수 있는 서로 다른 팀 구성 결과는 모두 몇 가지인가?

두 팀의 구성 결과가 서로 다르다는 것은, 소속팀이 다른 선수가 적어도 한 명 이상 존재한다는 것을 의미한다.

문제 형식

주관식

출처

• KOI 2025 1차대회 고등부 1교시 11번