KAIST POW 2021-24 The squares of wins and losses라는 문제입니다.
카이스트에 재학중이신 학생분께서 이 문제의 해답을 해주셨는데 이해가 안되는 부분이 있어서 질문을 드리려고 합니다.
문제
n명의 학생이 체스 토너먼트에 참가한다. 각각의 두 선수는 한번씩 게임을 한다. 비기는 경우는 없다.
ai를 i번째 선수가 각각의 경기에서 승리하는 회수라고 하고 bi를 i번째 선수가 각각의 경기에서 패배하는 회수라고 하자.
Σ(ai)²=Σ(bi)² 임을 증명하시오.
명제1. 모든 선수는 n-1번의 경기에 참가하므로 ai+bi=n-1
명제2. 총 n(n-1)/2번의 경기가 있고 각각의 경기에서 승자와 패자가 만들어지므로 Σ(ai)=Σ(bi)=n(n-1)/2
해답
Σ(ai)²-ai = Σ(bi)²-bi를 증명하자. 이 식은 명제 2에 의해서 원래의 문제와 같다.
그러면 좌변은 다음과 같은 i,j,k 세 쌍의 선수의 정렬된 개수와 같다.
(원문은 then, the quantity in LHS is equal to the number of ordered triplets of person i,j,k such that 입니다.)
i가 j를 이긴다(따라서 i≠j)
i가 k를 이긴다(따라서 i≠k)
j≠k
따라서 우변은 다음과 같은 i,j,k 세 쌍의 선수의 정렬된 개수와 같다.
(원문은 consequantly, the quantity in RHS is equal to the number of ordered triplets of person i,j,k such that 입니다.)
i가 j에게 진다(따라서 i≠j)
i가 k에게 진다(따라서 i≠k)
j≠k
i,j,k 세 쌍의 선수의 정렬되지 않은 모든 3!개의 순서들 중에서 몇 가지 순서가 양변에 기여하는지 확인하자.
(원문은 Let's enumerate all unordered triplets of person i,j,k and check how many order (among all 3! oders) contributes to the both quantity 입니다.)
두 가지 경우가 있다.
첫번째 경우는 i,j,k 사이의 경기의 결과가 i가 j를 이기고 j가 k를 이기고 k가 i를 이기는 경우이다. 이 경우는 어떤 선수도 두 번 패배하지 않으므로 이 경우는 양변에 기여하지 못한다.
두번째 경우는 i,j,k 사이의 경기의 결과가 i가 j를 이기고 j가 k를 이기고 i가 k를 이기는 경우이다. 그러면 i는 두 번 이기고 k는 두 번 지고 j는 한 번 이기고 한 번 진다. 정확히 좌변에는 (i,j,k , i,k,j)의 two triplet이 기여하고 우변에는 (k,i,j , k,j,i)의 two triplet이 기여한다.
그러므로 모든 i,j,k 세 명의 선수의 정렬된 triplet이 좌변과 우변에 같은 양으로 기여한다.
따라서 Σ(ai)²-ai = Σ(bi)²-bi 이다.
영어로 되어 있는 것을 우리말로 해석했습니다. 이제 질문을 드리려고 합니다.
해답에 따르면 Σ(ai)²-ai = Σ(bi)²-bi가 좌변에서 각각의 i가 j,k 모두에게 승리하는 경기의 수의 합을 나타내고 우변에서 각각의 i가 j,k 모두에게 패배하는 경기의 수의 합을 나타낸다고 합니다. 이때 특별히 i,j,k 쌍으로 모든 경기의 수를 어떻게 나타낼 수 있을까요? 가령 n명의 경기의 합을 Σ(ai)=Σ(bi)로 나타낼 때는 각각의 i에 대하여 i≠j인 j사이에서 순위를 정하는 비교를 통해서 양변의 값을 n(n-1)/2!로 나타낼 수 있지만 n명의 경기의 합을 Σ(ai)²-ai = Σ(bi)²-bi로 나타낼 때 (i,j,k) 사이에서 순위를 정하는 비교를 통해서 양변의 값을 n(n-1)(n-2)/3!로 나타낼 수 있는가에 대한 의문이 있습니다. 분명히 두명씩 비교할 때는 모든 경기의 경우의 수를 나타낸다는 걸 알 수 있지만 해답에서 처럼 세명씩 비교할때 모든 경기의 경우의 수를 나타낼 수 있는가가 의심스럽고 실제로 경우의 수를 따져보아도 세 명씩 비교하면 모든 경기의 경우의 수를 중복때문에 표현할 수 없다는 문제가 일어날 수밖에 없다고 생각합니다.
두번째 질문은 만약에 첫번째 질문에 대한 이해가 이루어졌을 때 i,j,k 사이의 순위의 경우의 수는 총 3!가지가 있습니다. 즉 (i,j,k , i,k,j) , (j,i,k , j,k,i) , (k,i,j , k,j,i)로 말입니다. 그런데 해답에서는 Σ(ai)²-ai = Σ(bi)²-bi를 만족하는 경우가 좌변은 정확히 (i,j,k , i,k,j)의 두 가지 경우뿐이고 우변도 정확히 (k,i,j , k,j,i)의 두 가지 경우 뿐이라고 했습니다. 그런데 이 경우의 전제는 i가 j,k를 모두 이김으로써 승리의 순위에서는 1위이고 j가 i에게 지고 k에게 이김으로써 승리의 순위에서는 2위이고 k가 i,j 모두에게 짐으로써 승리의 순위에서는 3위인데 좌변에서 (i,j,k)는 이 경우와 일치하지만 (i,k,j)는 이 경우와 일치하지 않는 것 같습니다. j는 2위여야 하는데 3위가 되었으니까요. 또한 패배의 순위에서는 k가 1위 j가 2위 i가 3위라고 할 수 있지만 우변에서 (k,i,j)와 (k,j,i)가 과연 앞에 말을 나타내는 순위인지 도저히 알 수 없었습니다. 그리고 좌변과 우변에서 각각 이 두 가지씩의 triplet만 가능하다고 하였는데 그렇다면 왜 (j,i,k , j,k,i)인 triplet은 가능하지 않는 것일까요? 이 경우도 순위를 정할 수 있으므로 좌변과 우변에 기여하는데 말입니다.
긴 글 되었지만 꼭 알고 싶어서 도움을 요청하게 되었습니다. 끝까지 읽어주시고 저와 같이 고민해주셔서 정말 감사의 말씀을 드립니다.
