Дано:
Cлова a, b, c; Длина каждого слова — n символов;
Доказать:
d(a, b) + d(b, c) >= d(a, c)
Доказательство:
Пусть слова a и c отличаются в некоторых позициях. Тогда любое слово b будет отличаться в этих позициях хотя бы от одного из слов а и c. Следовательно, расстояние между словами (a, c) всегда будет не больше, чем сумма расстояний между словами (a, b) и (b, c).
Пример:
Пусть имеются три слова a, b, c длины n = 4 символа каждое:
a = yyyy
b = yyxx
c = yyyx
Расстояния между словами (различия в позициях) равны:
d(a, b) = 2;
d(a, c) = 1;
d(b, c) = 1;
Получаем, что d(a, b) + d(b, c) >= d(a, c) , то есть 2 + 1 > 1;
d(a, b) + d(a, c) >= d(b, c), то есть 2 + 1 > 1;
d(b, c) + d(a, c) >= d(a, b), то есть 1 + 1 = 2.