中央値と絶対誤差

$a$ が $p$ の左、$p$ と $q$ の間、$q$ の右のどこにあるかで分ける。

• $a< p$ のとき：$p-a>0$、$q-a>0$ なので、左辺は $(p-a)+(q-a)$ である。これを $(q-p)+2(p-a)$ と書き直すと、$2(p-a)>0$ なので左辺は $q-p$ より真に大きい。
• $p\le a\le q$ のとき：$a-p\ge0$、$q-a\ge0$ なので、左辺は $(a-p)+(q-a)=q-p$ で、等号が成り立つ。
• $a>q$ のとき：$a-p>0$、$a-q>0$ なので、左辺は $(a-p)+(a-q)=(q-p)+2(a-q)$ で、$2(a-q)>0$ なので $q-p$ より真に大きい。
  3 つの場合のどれでも不等式が成り立ち、等号は 2 番目の場合だけである。$\square$

方針：候補の点が条件を満たすことと、それより左や右の点が条件を破ることを、並べ替えたデータの番号で数えて示す。
段 1（偶数 $n=2m$、区間の点は属する）。$\frac n2=m$ である。$x_{(m)}\le a\le x_{(m+1)}$ とする。番号 $k\ge m+1$ のデータは $x_{(k)}\ge x_{(m+1)}\ge a$ なので、$a$ より真に小さくない。よって $a$ より真に小さいデータは $x_{(1)},\dots,x_{(m)}$ の中にしかなく、多くても $m$ 個である。同じように、番号 $k\le m$ のデータは $x_{(k)}\le x_{(m)}\le a$ なので $a$ より真に大きくなく、$a$ より真に大きいデータは多くても $x_{(m+1)},\dots,x_{(n)}$ の $m$ 個である。したがって $a$ は中央値の集合に属する。
段 2（偶数、区間の外の点は属さない）。$a< x_{(m)}$ なら、$x_{(m)},x_{(m+1)},\dots,x_{(n)}$ はすべて $a$ より真に大きい。その個数は $n-m+1=m+1$ で、$m$ を超える。$a>x_{(m+1)}$ なら、$x_{(1)},\dots,x_{(m+1)}$ の $m+1$ 個が $a$ より真に小さい。どちらも条件を破る。
段 3（奇数 $n=2m+1$）。$\frac n2=m+\frac12$ で、個数は整数なので、条件は「小さいもの・大きいものがそれぞれ $m$ 個以下」と同じである。$a=x_{(m+1)}$ なら、$a$ より真に小さいデータは番号 $k\le m$ のものに限られ、真に大きいデータは番号 $k\ge m+2$ のものに限られるので、どちらも $m$ 個以下である。$a< x_{(m+1)}$ なら $x_{(m+1)},\dots,x_{(n)}$ の $m+1$ 個が $a$ より大きく、$a>x_{(m+1)}$ なら $x_{(1)},\dots,x_{(m+1)}$ の $m+1$ 個が $a$ より小さいので、条件を破る。$\square$

方針：いちばん小さい値といちばん大きい値、2 番目に小さい値と 2 番目に大きい値、…と組にし、各組に lem-mae-pair を使う。
段 1（並べ替える）。$L(a)$ は足す順序によらないので、$L(a)=\sum_{k=1}^n|x_{(k)}-a|$ と並べ替えたデータで書ける。
段 2（偶数 $n=2m$ の下からの評価）。$k=1,\dots,m$ について、$x_{(k)}$ と $x_{(n+1-k)}$ を組にする。$k\le m< m+1\le n+1-k$ なので $x_{(k)}\le x_{(n+1-k)}$ である。$n$ 個の項はちょうど $m$ 組に分かれるので
$$ L(a)=\sum_{k=1}^m\Bigl(|x_{(k)}-a|+|x_{(n+1-k)}-a|\Bigr) $$
である。各組に lem-mae-pair を $p=x_{(k)}$、$q=x_{(n+1-k)}$ として使うと、各組は $x_{(n+1-k)}-x_{(k)}$ 以上である。足し合わせて
$$ L(a)\ge C,\qquad C:=\sum_{k=1}^m\bigl(x_{(n+1-k)}-x_{(k)}\bigr) $$
を得る。$C$ は $a$ によらない定数である。
段 3（偶数の等号）。$L(a)-C$ は、各組の「左辺 $-$ 右辺」を足したもので、どれも $0$ 以上である。$0$ 以上の数の和が $0$ になるのは、すべてが $0$ のときに限る。よって $L(a)=C$ となるのは、すべての組で等号が成り立つとき、すなわち lem-mae-pair により、$a$ がすべての区間 $I_k:=[x_{(k)},x_{(n+1-k)}]$（$k=1,\dots,m$）に属するときに限る。$x_{(k)}\le x_{(k+1)}$ かつ $x_{(n-k)}\le x_{(n+1-k)}$ なので $I_1\supset I_2\supset\cdots\supset I_m$ であり、これらすべてに属することは、最も内側の $I_m=[x_{(m)},x_{(m+1)}]$ に属することと同じである。$I_m$ は空でないので、$L$ の最小値は $C$ であり、最小にする $a$ 全体は $[x_{(m)},x_{(m+1)}]$ である。
段 4（奇数 $n=2m+1$）。真ん中の $x_{(m+1)}$ は組にならずに残るので
$$ L(a)=\sum_{k=1}^m\Bigl(|x_{(k)}-a|+|x_{(n+1-k)}-a|\Bigr)+|x_{(m+1)}-a|\ge C+0 $$
である（$C$ は段 2 と同じ式。$m=0$ なら空の和で $C=0$）。等号は、$a$ がすべての $I_k$ に属し、かつ $|x_{(m+1)}-a|=0$ のときに限る。後者は $a=x_{(m+1)}$ を意味する。$k\le m+1\le n+1-k$ なので $x_{(m+1)}$ はすべての $I_k$ に属する。よって最小値は $C$ で、最小にする $a$ は $x_{(m+1)}$ ただ 1 つである。
段 5（まとめ）。$\lfloor n/2\rfloor=m$ なので、最小値は主張の式に一致する。最小にする $a$ の集合は、prop-mae-interval により中央値の集合に一致する。$\square$