ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65859
Темы:    [ Числовые таблицы и их свойства ]
[ Примеры и контрпримеры. Конструкции ]
[ Принцип Дирихле (прочее) ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Юра и Яша имеют по экземпляру одной и той же клетчатой таблицы 5×5, заполненной 25 различными числами. Юра выбирает наибольшее число в таблице и вычёркивает строку и столбец, содержащие это число, затем выбирает наибольшее из оставшихся чисел и вычёркивает строку и столбец, содержащие это число, и т.д. Яша производит аналогичные действия, но выбирает наименьшие числа. Может ли случиться, что сумма чисел, выбранных Яшей
  a) больше суммы чисел, выбранных Юрой?
  б) больше суммы любых других пяти чисел исходной таблицы, удовлетворяющих условию: никакие два из них не стоят в одной строке или в одном столбце?


Решение

  a) Юрины числа  M1 > M2 > M3 > M4 > M5,  Яшины –  m5 < m4 < m3 < m2 < m1.  Ясно, что  M1m1.  Докажем, что  M2m2.  При выборе M2 уже были вычеркнуты одна строка и один столбец, а при выборе m2 – по три строки и столбца (число выбиралось на четвёртом шаге). В сумме вычеркнуто не более чем по четыре строки и столбца, значит, хотя бы одно число a осталось невычеркнутым в обоих случаях, откуда  M2a ≥ m2.
  Аналогично доказывается, что  Mi ≥ mi  при любом i, и поэтому Юрина сумма не меньше Яшиной.

б) Рассмотрим, например, таблицу:

  Будем складывать числа любой разрешённой пятерки. В разряде единиц сумма будет равна количеству чисел пятерки, стоящих на диагонали. В разряде десятков сумма всегда будет равна 10  (0 + 1 + 2 + 3 + 4:  цифра десятков зависит только от строки, а у нас есть представитель каждой строки). И в разряде сотен сумма равна 10 (цифра сотен зависит только от столбца). Значит, наибольшей будет сумма, где все пять чисел взяты с диагонали. Именно их Яша и выберет.


Ответ

a) Не может;  б) может.

Замечания

баллы: 6 + 2

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Номер 27
Дата 2005/2006
вариант
Вариант весенний тур, основной вариант, 8-9 класс
задача
Номер 7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .