上記の割り当てが最大値を最小にして、かつ最小値を最大にすることを示します。

最大値を最小化していることを示します。

\(\displaystyle \max_{1 \le i \le N} iP_i = kP_k\)をみたす \(k\) について考えます。（複数ある場合も以下の議論で全てについて考えればよいです）

この要素が既に入力で決定している場合は小さくできません。

そうでない時、もし \(P_k\) が \(k\) より大きい値とマッチングするならば、明らかに最大値は大きくなります。

もし \(P_k\) が \(k\) よりも小さい値とマッチングするならば、鳩の巣原理から \(k\) 以上のいずれかの値が \(P_k\) より大きい値とマッチングすることとなり、最大値が大きくなります。

以上よりこの割り当ては最大値を最小化していることが示されました。最小値に対しても同様の議論で証明が可能です。