Пусть минимальное число всей таблицы m. Сумма минимумов столбцов не меньше Nm. В строке, содержащей m, минимум равен m, а в остальных не больше U наибольшего разрешённого числа. Поэтому сумма минимумов строк не больше m+(N−1)U. Их отношение не больше N1+(N−1)U, поскольку m≥1.
Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.
Применение в задаче
Шаг 1. Пусть минимальное число всей таблицы m. Сумма минимумов столбцов не меньше Nm. В строке, содержащей m, минимум равен m, а в остальных не больше U — наибольшего разрешённого числа. Поэтому сумма минимумов строк не больше m+(N−1)U. Их отношение не больше N1+(N−1)U, поскольку m≥1.