三角不等式

三角形についての不等式

a, b, cを正数として、a, b, cを三辺とする三角形が存在する必要十分条件は、次の不等式が成立することである。

$$a<b+c$$

$$b<c+a$$

$$c<a+b$$

この不等式を少し変形してみよう。

1変数についての条件に整理する

上の不等式を、$b$について整理する。

2つ目の式で右辺の$c$を左辺に移項すると

$$a-c<b$$

3つ目の式で右辺の$a$を左辺に移項すると

$$c-a<b$$

である。$a-c=-(c-a)$だから、この両方の式が成立するということは、

$$|c-a|<b$$

と書ける。2つ目の式とまとめると、

$$|c-a|<b<c+a$$

と書ける。

a, b, cは正であること

絶対値は非負であるから、

$$0\le |c-a|<b$$

よって、$b$は正である。同様に、$a$, $c$も正である。

すなわち、三角不等式を満たすためには、$a$, $b$, $c$が正であることが必要である。

一番上で、$a$, $b$, $c$について正数という条件を与えていたが、三角不等式の成立はこの条件を含むので、実はこの仮定は必要ない、ということである。

a, b, cの大小関係を仮定する場合

今、$0<a\le b\le c$なる大小関係を仮定する。すると、

$$0<a$$

と、

$$b\le c$$

の辺々を加えることで、

$$b<a+c$$

が出る。これは、$b$に関して整理した三角不等式の後半部分である。

つまり、$0<a\le b\le c$の大小関係を仮定すると、後半部分は大小関係を仮定した時点で成立していることになる。

一方、前半部分について考えると、

$$a\le c$$

だから、

$$c-a\ge 0$$

よって、

$$|c-a|=c-a$$

したがって、この大小関係の仮定のもとで三角不等式は

$$c-a<b$$

と同値である。

bを固定する場合

同じく、$0<a\le b\le c$なる大小関係を仮定し、$b$は固定で$a,c$は動くとすると、上で求めた式が示唆するところにより、

$a$も$c$も$b$に近いほうが三角不等式は成立しやすく、逆に$a,c$が$b$から離れるほど三角不等式は成立しづらい。

この関係をa-cグラフに表すと次のようになる。

図の赤く塗った部分が三角不等式の成立する範囲である (直線$c=a+b$上の点は含まない)。

この図は少し面白く、この領域の各点が、一つの三角形の「形」に対応していることになる。 たとえば、右下の頂点$(a,c)=(b,b)$は正三角形という形に対応する。

例題 (Codility)

Codilityというコーディングテストのプラットフォームがあり、そこの練習問題に Triangleというものがある。

次のような問題である。

N個の整数値からなる配列Aが与えられるので、Aの中に三角不等式を満たす組が存在するかしないかを判定するような関数をかけ。

今までの考察からいえば、次のような解答例が考えられる。

#include <algorithm>

int solution(vector<int> &A) {
    // 配列Aをソート
    std::sort(A.begin(), A.end());

    // 配列Aのサイズ
    int size = A.size();

    // 正になるまでインデックスを進める
    int i = 0;
    while (i < size && A[i] <= 0) {
        ++i;
    }

    // 3つ組を順に見ていって三角不等式が成立するかを見る
    for (; i < size - 2; ++i) {
        if (A[i + 2] - A[i] < A[i + 1]) {
            return 1;
        }
    }

    // ループの最後に到達したら成立しなかったことになる
    return 0;
}

キーとなる考察は、「できるだけ近い値同士を見ていって、三角不等式が成立するかを確認する」という点である。