Как доказать правильность этого утверждения?

Математика
1

Есть две последовательности a и b, размеров n и m соответственно.

Для них выполняется:
a_i - a_{i - 1} < a_{i +1} - a_{i}, a_2 > a_1, b_i - b_{i - 1} < b_{i +1} - b_{i} и b_2 > b_1.

Рассматривается c таблица n x m, c_{i,j} = a_i + b_j .

В данную таблицу на клетку (1, 1) таблицы c, высаживается персонаж, он может ходить только вниз или вправо(Из клетки (i, j) в (i, j + 1) или (i + 1, j)). Ему нужно дойти до клетки (n, m) так чтобы сумма на пути была минимальной.

Утверждается что в данной таблице достаточно придерживаться подобной стратегии чтобы достигнуть минимальной суммы на пути между (1, 1) и (n, m):
Если ты находишься в клетке (i, j), то из неё нужно пойти в клетку с наименьшим значение, то есть, если c_{i + 1, j} < c_{i, j + 1} то ты идёшь в клетку (i + 1, j), иначе в клетку (i, j + 1).

Как доказать что вышеуказанное утверждение истинно?

2

Обозначим min(c_{i,j}) = min (c_{i+1,j}, c_{i,j+1}) (Аналогично max(c_{i,j}))
Тогда нам достаточно доказать, что min(min(c_{i,j})) \le min(max(c_{i,j}))

То есть, если мы делаем “выгодный” выбор, то и следующий шаг будет выгоднее, чем самый выгодный невыгодного )

Пусть min(c_{i,j})=c_{i,j+1}=a_i+b_{j+1}
Тогда

c_{i+1,j}=a_{i+1}+b_j > a_i+b_{j+1} = c_{i,j+1}\ \Rightarrow
a_{i+2}-a_{i+1}>a_{i+1}-a_i>b_{j+1}-b_j \ \Rightarrow
c_{i+2,j}>c_{i+1,j+1} \ \Rightarrow
min(c_{i+1,j})=c_{i+1,j+1}

Т.к. max(c_{i,j})=c_{i+1,j}, получается

min(min(c_{i,j}))=min(c_{i,j+1})=min(c_{i+1,j+1},c_{i,j+2}) \le c_{i+1,j+1}=min(c_{i+1,j})=min(max(c_{i,j}))

ч.т.д.

Только выглядит заморочено, на самом деле если написать на сетке эти числа, то становится гораздо легче

4 лайка