L1距離(マンハッタン距離)の意味と性質

マンハッタン距離

座標平面上の2点 A(a1,a2),B(b1,b2)A(a_1,a_2),B(b_1,b_2) の間の距離を

d(A,B)=a1b1+a2b2d(A,B)=|a_1-b_1|+|a_2-b_2|

で測ったものを L1L^1 距離(マンハッタン距離)と言う。

マンハッタン距離とユークリッド距離

2点間の遠さを定量的に表現するのが距離です。我々が普段よく使うのは以下の L2L^2 距離(ユークリッド距離)です:

d(A,B)=(a1b1)2+(a2b2)2d(A,B)=\sqrt{(a_1-b_1)^2+(a_2-b_2)^2}

しかし,場合によっては L1L^1 距離を用いたほうがよい場合があります。例えば,座標軸に平行にしか移動できない場合,L1L^1 距離で測るのが適切です。

実際,碁盤の目状の都市(アメリカのマンハッタン,日本だと平城京など)の2点間の最短距離は L1L^1 距離で表現できます(マンハッタン距離と呼ばれる理由!)。

マンハッタン距離

A(2,3)A(2,3)B(5,7)B(5,7) の距離は,

  • ユークリッド距離だと 32+42=5\sqrt{3^2+4^2}=5
  • マンハッタン距離だと (52)+(73)=7(5-2)+(7-3)=7

(平城京で二条三坊から五条七坊に移動するには最低7ブロックの移動が必要)

当然ですが,ユークリッド距離よりもマンハッタン距離の方が長くなっています。

L1L^1 距離の性質など

L1L^1 距離は一般の「距離」が満たすべき以下の性質(距離の公理)を満たしています:

  1. d(A,B)0d(A,B)\geq 0  また,d(A,B)=0    A=Bd(A,B)=0\iff A=B

  2. d(A,B)=d(B,A)d(A,B)=d(B,A)

  3. d(A,B)+d(B,C)d(A,C)d(A,B)+d(B,C)\geq d(A,C) (三角不等式)

(証明は練習問題にどうぞ)

また,原点から L1L^1 距離が 11 であるような点の集合(単位球)は図のような正方形になります。 l1距離の単位球

三次元以上の空間においても,L1L^1 距離を同様に定義できます:

d(A,B)=i=1naibid(A,B)=\displaystyle\sum_{i=1}^n|a_i-b_i|

東大の入試問題

L1L^1 距離に関する東大の問題を紹介します。

1994年東大理系第6問の(1)です(文言は少し変えています)。

問題

d(O,A)d(O,A)OOAAL1L^1 距離とする。原点 OOA(1,1)A(1,1) に対し,d(O,P)=d(P,A)d(O,P)=d(P,A) を満たす点 P(x,y)P(x,y) の範囲を (x,y)(x,y) 平面上に図示せよ。

解答

x+y=x1+y1|x|+|y|=|x-1|+|y-1| を満たす点の集合を図示せよ,という問題。愚直にやると,絶対値を外すために場合分けが 3×3=93\times 3=9 通り必要だが,対称性を考えると以下の四通りだけ調べればよいことが分かる。

L1距離にまつわる東大の問題

  • x1,y1x\geq 1,y\geq 1 の場合,
    x+y=x1+y1x+y=x-1+y-1 を満たす点は存在しない。

  • 0<x<1,y10 <x <1,y\geq 1 の場合,
    x+y=1x+y1    x=0x+y=1-x+y-1\\\iff x=0
    となり不適。

  • x0,y1x\leq 0, y\geq 1 の場合,
    x+y=1x+y1-x+y=1-x+y-1 は常に成立。

  • 0<x<1,0<y<10 <x <1,0 <y <1 の場合,
    x+y=1x+1y    x+y=1x+y=1-x+1-y\\\iff x+y=1

以上より,答えは図の青い領域(境界含む)。

「垂直二等分線」が二次元の広がりを持つというのは驚きですね。

急いでいるときに「直線で進んだら 22\frac{\sqrt{2}}{2} 倍に時短できるのに!」と思うことありますよね。

Tag:東大入試数学の良問と背景知識まとめ