全員集合問題(4)考察を示します。
(4)考察
2m+1人のいる交差点を、(x(1),y(1)), …,(x(2m+1),y(2m+1))とする。
交差点(x,y)で会うとするときの総移動距離をD(x,y)とすると、
D(x,y) = {|x(1)-x|+|x(2)-x|+ … +|x(2m+1)-x|}
+ {|y(1)-y|+|y(2)-y|+ … +|y(2m+1)-y|}
となる。
一般に、F(z)={|a(1)-z|+|a(2)-z|+ … +|a(2m+1)-z|} は、a(1),…,a(2m+1)を昇順に並べた結果をb(1)≦b(2)≦…≦b(m+1)≦…≦b(2m+1)としたとき、
z=b(m+1)で最小となることを使うと、
{x(1),x(2),…,x(2m+1)}の小さい方からm+1番目の値の添え字をp
{y(1),y(2),…,y(2m+1)}の小さい方からm+1番目の値の添え字をq とすると、
求める交差点は、(p,q)となり、最短総移動距離は、D(p,q)となる。
(証明)
F(b(j))={|a(1)-b(j)|+|a(2)-b(j)|+…+|a(2m+1)-b(j)|}
={|b(1)-b(j)|+|b(2)-b(j)|+…+|b(2m+1)-b(j)|}
=-(b(1)-b(j))-(b(2)-b(j))-…-(b(j)-b(j))
+(b(j+1)-b(j))+(b(j+2)-b(j))+…+(b(2m+1)-b(j))
=jb(j)-(2m+1-j)b(j)-{b(1)+b(2)+…+b(j)}
+{b(j+1)+b(j+2)+…+b(2m+1)}
=(2j-2m-1)b(j)+{b(1)+b(2)+…+b(2m+1)}
-2{b(1)+b(2)+…+b(j)}
F(b(j))-F(b(j+1))=(2j-2m-1)b(j)-{2(j+1)-2n-1}b(j+1)+2b(j+1)
=(2j-2m-1){b(j)-b(j+1)}
したがって、j≦mのとき F(b(j))≧F(b(j+1))
j>mのとき F(b(j))≦F(b(j+1))
となる。すなわち、
F(b(1))≧…≧F(b(m))≧F(b(m+1))≦F(b(m+2))≦…≦F(b(2m+1))
F(b(m+1))が最小値となる。