최대 차이를 최소로 하는 원형 배열

[BOJ 11497] Log Jumping 라는 문제를 접했는데, 증명을 내버려두기는 아까워서 올린다.

Problem. \(n \geq 3\)이고, 길이 \(n\)의 원형 배열이 주어졌을 때, 이를 원형으로 재배열해서 인접한 수의 차이 중 최댓값을 최소화하기.

이 문제의 답은 \((a_1, a_3, \ldots, a_{n-1}, a_n, a_{n-2}, a_{n-4}, \ldots, a_2)\)와 같이 배치하는 것이다. (\(n\)이 짝수인 경우만 쓴 것이다) 이걸 수학적으로 표현해보자. 이론적 최솟값을 구하고, 저러한 배치가 concrete example이 된다는 방식으로 보인다.

Given: \(a_1 \leq \ldots \leq a_n\).

Want to show: 임의의 길이 \(n\)의 순열 \(P\)에 대해, $$ D_n = \min_{P} \max(\vert a_{p_1}-a_{p_2} \vert, \ldots, \vert a_{p_n}-a_{p_1} \vert) = \max(a_3-a_1, a_4-a_2, \ldots, a_{n}-a_{n-2})$$

Proof

수학적 귀납법을 사용. \(n\)일 때 성립한다고 가정. \(n+1\)일 때, 길이 \(n+1\)의 순열 \(P\)에 대해 만들어지는 통나무 배치를 생각한다. \(a_{n+1}\)이 \(a_i\)와 \(a_j\) 사이에 끼어 있다고 하자. 이 배치에서 우리가 궁금한 값은 $$X(P) = \max(\vert a_{p_1}-a_{p_2} \vert, \ldots, \vert a_i - a_{n+1} \vert, \vert a_{n+1}-a_j \vert, \ldots, \vert a_{p_{n+1}}-a_{p_1} \vert)$$ 이다. 삼각 부등식에 의해 \(\vert a_i - a_{n+1} \vert + \vert a_{n+1} - a_j \vert \geq \vert a_i - a_j \vert\)이고, 그러므로 \(D_n\)의 정의에 의해 \(X(P) \geq D_n\)이므로, \(D_{n+1}\)의 정의에 의해 \(D_{n+1} \geq D_n\).

또한, 임의의 배치에서 \(a_{n+1}\) 양 옆에 통나무가 하나씩 존재하므로, \(D_{n+1} \geq a_{n+1}-a_{n-1}\)도 성립한다.

따라서 \(D_{n+1} = \max(a_3-a_1, \ldots, a_{n+1}-a_{n-1})\)임을 보일 수 있다.