Задача
Юра и Яша имеют по экземпляру одной и той же клетчатой таблицы 5×5, заполненной 25 различными числами. Юра выбирает наибольшее число в таблице и вычёркивает строку и столбец, содержащие это число, затем выбирает наибольшее из оставшихся чисел и вычёркивает строку и столбец, содержащие это число, и т.д. Яша производит аналогичные действия, но выбирает наименьшие числа. Может ли случиться, что сумма чисел, выбранных Яшей a) больше суммы чисел, выбранных Юрой? б) больше суммы любых других пяти чисел исходной таблицы, удовлетворяющих условию: никакие два из них не стоят в одной строке или в одном столбце?
Решение
a) Юрины числа M1 > M2 > M3 > M4 > M5, Яшины – m5 < m4 < m3 < m2 < m1. Ясно, что M1 ≥ m1. Докажем, что M2 ≥ m2. При выборе M2 уже были вычеркнуты одна строка и один столбец, а при выборе m2 – по три строки и столбца (число выбиралось на четвёртом шаге). В сумме вычеркнуто не более чем по четыре строки и столбца, значит, хотя бы одно число a осталось невычеркнутым в обоих случаях, откуда M2 ≥ a ≥ m2.
Аналогично доказывается, что Mi ≥ mi при любом i, и поэтому Юрина сумма не меньше Яшиной. б) Рассмотрим, например, таблицу:
Ответ
a) Не может; б) может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь