Минимумы строк и столбцов

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Общая наименьшая клетка
  2. Постоянные строки

    Сначала: Общая наименьшая клетка

  3. Ответ: да

    Сначала: Постоянные строки

  4. Общая наименьшая клетка

    Сначала: Ответ: да

  5. Ответ: нет

    Сначала: Общая наименьшая клетка

  6. Общая наименьшая клетка

    Сначала: Ответ: нет

  7. Постоянные строки

    Сначала: Общая наименьшая клетка

  8. Ответ

    Сначала: Постоянные строки

Разобранный пример

В каждой клетке квадратной таблицы 6×66 \times 6 стоит натуральное число, меньшее 7. Вася в каждом столбце находит наименьшее число и складывает шесть найденных чисел. Петя в каждой строке находит наименьшее число и складывает шесть найденных чисел.

а) Может ли сумма у Пети получиться в два раза больше, чем сумма у Васи?

б) Может ли сумма у Пети получиться в шесть раз больше, чем сумма у Васи?

в) В какое наибольшее число раз сумма у Пети может быть больше, чем сумма у Васи?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Пусть минимальное число всей таблицы mm. Сумма минимумов столбцов не меньше NmNm. В строке, содержащей mm, минимум равен mm, а в остальных не больше UU - наибольшего разрешённого числа. Поэтому сумма минимумов строк не больше m+(N−1)Um+(N-1)U. Их отношение не больше 1+(N−1)UN\frac{1+(N-1)U}{N}, поскольку m≥1m\geq 1.
N=6N=6
U=6U=6
Шаг 2. Первую строку заполняем единицами, остальные строки - выбранными постоянными числами от 1 до UU. Тогда все минимумы столбцов равны 1, а сумма минимумов строк равна сумме выбранных постоянных. Для максимума берём остальные строки равными UU; для меньшего заданного отношения распределяем нужную сумму по N−1N-1 разрешённым постоянным.
T=(1;6;2;1;1;1)\mathcal T=\left(1;6;2;1;1;1\right)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Пусть минимальное число всей таблицы mm. Сумма минимумов столбцов не меньше NmNm. В строке, содержащей mm, минимум равен mm, а в остальных не больше UU - наибольшего разрешённого числа. Поэтому сумма минимумов строк не больше m+(N−1)Um+(N-1)U. Их отношение не больше 1+(N−1)UN\frac{1+(N-1)U}{N}, поскольку m≥1m\geq 1.
N=6N=6
U=6U=6
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Пусть минимальное число всей таблицы mm. Сумма минимумов столбцов не меньше NmNm. В строке, содержащей mm, минимум равен mm, а в остальных не больше UU - наибольшего разрешённого числа. Поэтому сумма минимумов строк не больше m+(N−1)Um+(N-1)U. Их отношение не больше 1+(N−1)UN\frac{1+(N-1)U}{N}, поскольку m≥1m\geq 1.
Шаг 2. Первую строку заполняем единицами, остальные строки - выбранными постоянными числами от 1 до UU. Тогда все минимумы столбцов равны 1, а сумма минимумов строк равна сумме выбранных постоянных. Для максимума берём остальные строки равными UU; для меньшего заданного отношения распределяем нужную сумму по N−1N-1 разрешённым постоянным.
T=(1;6;6;6;6;6)\mathcal T=\left(1;6;6;6;6;6\right)
Шаг 3. Записываем найденное значение.
316\frac{31}{6}

Открыть задачу целиком

Попробовать самостоятельно