두 성별을 서로 바꾸어도 만나는 횟수는 같다. 따라서 라 하고, 더 적은 쪽의 학생을 배치할 개의 칸을 고르자. 이면 어느 쪽을 골라도 된다.
칸의 차수를 그 칸과 변을 공유하는 칸의 개수라고 하자. 내부 칸의 차수는 , 모서리가 아닌 테두리 칸의 차수는 , 모서리 칸의 차수는 이다.
격자를 체스판처럼 두 색으로 칠하면 같은 색의 두 칸은 변을 공유하지 않는다. 한 색의 칸에서만 칸을 고르면, 선택한 칸의 차수의 합이 그대로 만나는 횟수가 된다. 그러므로 각 색에 대해 차수가 큰 칸부터 개 고르고, 두 색 중 차수의 합이 더 큰 쪽을 선택한다. 합이 같으면 어느 쪽을 골라도 된다. 각 색에는 적어도 개의 칸이 있으므로 항상 가능하다.
정렬할 필요는 없다. 각 색에서 차수가 인 칸의 개수를 세고, 그 순서대로 몇 칸씩 선택할지 정하면 된다. 선택한 색과 차수별 개수를 구한 뒤 격자를 다시 순회하면서 해당 개수만큼 더 적은 성별을 배치한다. 나머지 칸은 다른 성별로 채운다. 인 경우에도 같은 과정으로 격자 전체가 한 성별로 채워진다.
격자를 상수 번 순회하므로 시간 복잡도는 이다. 한 행씩 만들어 출력하면 공간 복잡도는 이다.
증명
체스판의 한 색만 사용하는 배치가 최적이라는 사실을 증명해야 한다. 임의의 배치에서 더 적은 성별을 배치한 칸을 선택한 칸이라고 하자. 만나는 횟수를 , 선택한 내부 칸의 수를 , 선택한 모서리 칸의 수를 , 양 끝 칸이 모두 선택된 변의 수를 라고 하자. 선택한 칸의 차수 합에서 이러한 변을 두 번씩 빼면
Solution written by GPT6
를 얻는다. 모든 차수가 이하이므로 도 성립한다.
라고 하자. 내부의 격자에서 서로 변을 공유하지 않는 칸은 최대 개이다. 행마다 진행 방향을 바꾸어 모든 내부 칸을 지나는 뱀 모양 경로를 생각하면, 이 경로에서 이웃한 칸을 동시에 고를 수 없으므로 개 이하이다. 체스판의 더 큰 색을 고르면 개를 얻을 수 있다. 일 때 내부는 비어 있고 이다.
양 끝이 선택된 내부 칸인 변의 수를 라고 하자. 각 변에서 끝점 하나씩을 제거하면 적어도 개의 서로 인접하지 않는 내부 칸이 남으므로 이다. 또한 이므로
라는 상한을 얻는다.
먼저 이 짝수인 경우를 보자. 격자를 서로 겹치지 않는 정사각형들로 나눈다. 한 정사각형에 선택한 칸이 개 있으면, 그 정사각형의 네 변 중 서로 다른 성별이 만나는 변은 최대 개이다. 따라서 같은 성별을 잇는 변은 적어도 개이다. 이를 모든 정사각형에 대해 더하면 전체 격자에 같은 성별을 잇는 변이 적어도 개 있어야 한다. 전체 변이 개이므로
이다.
짝수 에서 체스판의 각 색에는 차수 인 칸이 개, 차수 인 칸이 개, 차수 인 칸이 개 있다. 차수가 큰 칸부터 선택하면 그 합은
이다. 앞에서 구한 세 상한 중 작은 값을 달성하므로 최적이다.
이제 이 홀수인 경우를 보자. 라고 하면 이다. 가 성립하려면 앞의 부등식에서 이어야 한다. 이므로 이고, 따라서 이다.
내부 격자의 칸 수는 이다. 이 내부를 지나는 뱀 모양 경로에서 서로 인접하지 않는 개 칸을 고르는 방법은 첫 칸부터 하나씩 건너뛰며 고르는 방법뿐이다. 따라서 내부의 최대 독립집합은 내부 모서리를 포함하는 체스판 색 전체로 유일하다. 이 색은 바깥 격자의 네 모서리와도 같은 색이다.
이 내부 칸들을 모두 선택했다면 반대 색인 테두리 칸은 선택한 내부 칸과 인접한다. 이므로 그러한 칸은 추가할 수 없고, 이므로 모서리도 추가할 수 없다. 추가할 수 있는 칸은 같은 색인 모서리 이외의 테두리 칸 개뿐이다. 따라서 이면 이어야 한다. 즉, 인 경우에는 정수인 에 대해
이 성립한다.
네 모서리를 포함하는 색에는 차수 인 칸이 각각 개 있다. 다른 색에는 각각 개 있다. 차수가 큰 칸부터 골랐을 때의 합을 비교하면 다음 상한들을 모두 달성한다.
일 때 두 번째 구간은 비어 있으며 나머지 경우는 그대로 성립한다. 따라서 홀수인 경우에도 두 색의 후보 중 좋은 쪽이 모든 배치에 대한 상한을 달성하므로 최적이다.
