Изменения

# Если бы выполнялось <tex> z_k \neq x_m </tex>, то к <tex> Z </tex> можно было бы добавить элемент <tex> x_m = y_n </tex>, и тогда получилась бы общая подпоследовательность длины <tex> k + 1 </tex>, что противоречит предположению, что <tex> Z </tex> — НОП. Значит, выполняется <tex> z_k = x_m = y_n </tex>. Значит, <tex> Z_{k - 1} </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>. Докажем от противного, что <tex> Z_{k - 1} </tex> — НОП. Пусть : тогда есть общая подпоследовательность <tex> W </tex>, длина которой больше <tex> k - 1 </tex> (т.е. больше длины <tex> Z </tex>). Добавив к <tex> W </tex> элемент <tex> x_m = y_n </tex>, получим НОП, длина которой больше <tex> k </tex>((т.е. больше длины <tex> Z </tex>), что приводит к противоречию.