세 후보 A,B,C를 모든 표에서 빠짐없이 순위로 정해요. 동순위와 기권은 없고,1·2·3순위에2·1·0점을 줘요. 총점이 다른 두 후보보다 엄격히 큰 후보만 유일승자다. 실제 선거 자료가 아닌 자체 점수 모형이에요.
6표에서 A가7점으로 이기는 순위표를 만들 수 있을까요? 만들 수 있다면7점만 확인해 언제나 이긴다고 해도 될까요?
모든 표는 합계3점을 주므로 후보들의 총점 합은18입니다. A가7점일 때 가능한 두 순위표를 볼까요?
| 순위 | 첫 표 모임의 표 수 | 둘째 표 모임의 표 수 |
|---|---|---|
| A>B>C | 2 | 1 |
| B>A>C | 1 | 5 |
| B>C>A | 1 | 0 |
| C>A>B | 2 | 0 |
첫 모임은 A7,B6,C5로 A가 이겨요. 둘째는 A7,B11,C0으로 진다. 같은 A점수와 같은 총표 수지만 상대 점수가 달라요.
이제 n≥1표로 일반화해요. 유일승자가 x점을 얻었다면 다른 두 후보는 정수이므로 각각 x−1점 이하예요.
따라서 x≥n+1입니다. 이 하한이 실제 순위표에서도 달성되는지 확인해야 해요.
ABC는 A>B>C의 줄임말이에요. 다음 기초 모임의 점수를 직접 합산하자.
| 표 수 | 순위 목록 | (A,B,C) 총점 |
|---|---|---|
| 1 | ABC | (2,1,0) |
| 2 | ABC,CAB | (3,1,2) |
| 3 | ABC,BAC,CAB | (4,3,2) |
ABC,BCA,CAB 세 표를 추가하면 모든 후보에게3점씩 더해져 순서는 유지돼요. n을3으로 나눈 나머지에 따라 기초1·2표에서 시작하거나, 나머지0이면 기초3표에서 시작해 이 세 표 묶음을 반복해요. 그러면 모든 n에서 A가 n+1점으로 유일하게 이겨요. 따라서 가능한 최소 승자 점수는 n+1입니다.
반면 점수만으로 승리를 보장하려면 A점수 s가 전체3n의 절반보다 커야 해요. s>3n/2이면 다른 두 점수의 합3n−s가 s보다 작고, 각 점수도 그 합 이하여서 A보다 작아요.
⌊u⌋는 u를 넘지 않는 최대 정수예요. 이보다 한 점 낮은 기준에서 실제로 보장이 깨지는지도 확인해 볼까요?
n=2k이면 ABC와 BAC를 k표씩 쓰면 A와B가 각각3k점으로 동점이에요. n=2k+1이면 이 모임에 BAC 한 표를 더해 A3k+1,B3k+2,C0이므로 A가 진다. k=0인1표도 포함돼요. 각각 A점수가 ⌊3n/2⌋이므로 기준을 더 낮춰도 이 반례가 남아요.
6표에서는 최소7점으로 이길 수 있지만,10점 이상이어야 점수만으로 유일승리를 보장해요. 7점이 모든 순위표에서 이긴다는 뜻은 아니에요. 어떤 표 모임이 가능한가라는 질문과 모든 표 모임에서 성립하는가라는 질문은 달라요.
Eppstein의 문제는 이 두 수준을 따로 물어요. 여기서는 실제 기초 모임과 균형 묶음을 구성해 하한의 달성을 증명했어요. 교사는 숫자만 적은 답에 가능한 순위표와 보장 기준 바로 아래의 동점·패배 표를 각각 요구해요.
착안: David Eppstein, UCI Practice Problem Set4, question1, 순위 점수 정의 — Lecture4a, PDF12쪽. 표·기초 모임 구성·증명·설명은 새로 작성한 자체 해설이며 공식 해설의 번역이 아니에요.