반복 재생할 일곱 곡 중 A 장르는 네 곡, B 장르는 두 곡, C 장르는 한 곡이다. 곡을 빼거나 다시 넣지 않고 순서만 바꾼다. 마지막 곡 다음에는 첫 곡으로 돌아간다. 장르가 바뀌는 경계는 한 바퀴에 몇 번 만들 수 있을까? 3회와 6회 사이의 모든 횟수가 가능할까?
이 글에서는 실제 장르 분석 대신 각 곡에 미리 A·B·C 중 라벨 하나만 붙인 자체 모형을 쓴다. 곡은 서로 구별되며 각각 한 번씩 재생한다. a,b,c는 0 이상인 정수, N=a+b+c≥1이다. 순환 순서의 N개 경계 중 양쪽 라벨이 다른 경계의 수를 m이라 한다. 한 곡이면 자기 자신으로 돌아오는 경계 한 개를 세고 m=0이다. 두 곡이면 첫째→둘째와 둘째→첫째 두 경계를 따로 센다.
모든 a,b,c에서 가능한 m의 집합을 구하고, 가능한 각 목표를 만드는 순서를 구성하라. 세 종류가 모두 있을 때와 두 종류만 있을 때의 차이를 설명하라. 배열의 개수나 임의 셔플의 확률을 묻는 문제는 아니다.
일곱 곡의 자체 예에서는 다음 네 순서가 모두 A 네 개·B 두 개·C 한 개를 사용한다. 마지막 글자에서 첫 글자로 가는 경계도 포함한다.
| 순환 순서 | 장르 전환 수 |
|---|---|
| AAAABBC | 3 |
| AAABBAC | 4 |
| AAABABC | 5 |
| AABABAC | 6 |
일반적으로 쓰는 라벨이 한 종류면 m=0뿐이다. 두 종류의 양수 곡 수를 u,v라 하면 가능한 집합은 다음과 같다.
원형 순서에서 같은 라벨이 이어지는 최대 묶음들을 줄여 보자. 두 종류의 묶음은 번갈아 나오고, 원을 닫으므로 두 종류의 묶음 수는 같은 r개다. 묶음 사이에 경계가 2r개 생긴다. 각 묶음에 적어도 한 곡이 있어야 하므로 r≤min(u,v)다. 반대로 두 라벨을 각각 r번 번갈아 놓고, 각 라벨의 남은 곡을 그 라벨의 한 묶음에 더하면 정확히 2r회가 된다.
세 종류가 모두 있으면 N=a+b+c, M=max(a,b,c)로 두었을 때 가능한 집합은 다음과 같다.
상한만 맞춘 것이 아니라 이 범위의 모든 정수가 가능하다. 최소 세 묶음이 있어 m≥3이고, 전체 경계는 N개이므로 m≤N이다. 가장 많은 라벨을 A라 하자. 서로 다른 두 라벨의 경계에는 A가 아닌 곡이 적어도 하나 있다. A가 아닌 N−M개 곡은 각각 두 경계에만 닿으므로 m≤2(N−M)다. 이 논증은 다른 두 라벨끼리의 경계를 두 번 셀 수 있어서 상한으로 쓴다.
이제 임의의 허용 정수 m을 실제로 만들어 충분성을 보인다. h=⌊m/2⌋라 하고 세 라벨의 묶음 수 r₁,r₂,r₃를 다음 범위에서 정한다.
그런 선택이 가능한 이유를 확인하자. 곡 수를 a≥b≥c로 다시 이름 붙인다. a≤h이면 세 상한의 합은 N≥m이다. a>h,b≤h이면 그 합은 h+b+c이고, m≤2(b+c)에서 b+c≥⌈m/2⌉이므로 m 이상이다. a>h,b>h이면 앞의 두 상한만으로 2h, 셋째 상한은 적어도 1이어서 역시 m 이상이다. 세 묶음 수를 1에서 시작해 각 상한 안에서 하나씩 늘리면 합 m까지 도달한다.
묶음 수가 가장 많은 라벨을 A로 다시 이름 붙이고 그 수를 rA, 나머지를 rB,rC라 하자. rA≥rB,rC이며 2rA≤m이므로 rA≤rB+rC다. 원형으로 A 묶음 rA개를 놓아 그 사이에 rA개 틈을 만든다. rB개 틈에 B를 하나씩, 나머지 rA−rB개 틈에 C를 하나씩 넣는다. 모든 틈이 채워지고, 아직 남은 C는 rB+rC−rA개다. 이 수는 0 이상이고 rB 이하이므로 그만큼의 B 뒤에 C를 하나씩 덧붙일 수 있다. 각 틈은 B·C·BC 중 하나가 된다. 틈 안에서도, A를 사이에 둔 틈 사이에서도 같은 라벨이 붙지 않는다.
이렇게 세 라벨을 정확히 rA,rB,rC개 사용하는 m개 묶음의 원형 순서를 얻었다. 각 라벨의 남은 곡을 그 라벨의 한 묶음에 보태면 원래 a,b,c곡을 모두 쓰면서 전환 수 m은 그대로다. 곡이 서로 구별되므로 같은 라벨의 곡은 어느 순서로 그 자리를 채워도 이 경계 수는 달라지지 않는다. 이 구성으로 중간 정수도 전부 달성했다.
예의 N=7,M=4에서는 상한이 6이고 가능한 집합이 {3,4,5,6}이다. A 네 곡과 B 세 곡만 있다면 같은 N,M이어도 {2,4,6}뿐이다. 가장 많은 라벨의 수가 같은 경우에도, 실제 쓰는 라벨 종류 수가 중간 빈값을 결정한다.
교사는 먼저 한 예에서 상한을 얻었다는 주장과 상한 아래의 모든 정수를 만들었다는 주장을 나눠 쓰게 한다. 두 종류에서 전환 수가 짝수라는 사실을 세 종류에도 그대로 적용하면 표의 3회·5회를 놓친다. 가능한 정수 m의 진리집합을 적은 뒤, 필요조건만으로 그 집합을 모두 찾았는지 실제 구성으로 확인한다. 제공 교재의 진리집합은 이 표현의 용어 근거이며 원형 묶음 구성의 정리를 제공한 것은 아니다.
착안: Spotify, Play Queue. 원문에서 재생 대기 목록의 순서를 직접 바꿀 수 있다는 배경만 참고했다. 곡의 라벨·개수·순환 경계 정의·가능한 모든 횟수의 구성은 자체 교육용이며, 실제 음원의 장르 분석이나 서비스의 셔플 방식·청취 반응을 조사한 결과는 아니다.