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

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

Условие

В каждой клетке таблицы размером 13×13 записано одно из натуральных чисел от 1 до 25. Клетку назовём хорошей, если среди двадцати пяти чисел, записанных в ней и во всех клетках одной с ней горизонтали и одной с ней вертикали, нет одинаковых. Могут ли все клетки одной из главных диагоналей оказаться хорошими?


Решение

  Для каждой клетки одной из главных диагоналей рассмотрим крест совокупность из двадцати пяти клеток: её саму и все клетки, стоящие с ней в одной горизонтали или вертикали.
  Рассмотрим все кресты, образованные клетками выделенной главной диагонали. Заметим, что каждая клетка этой диагонали входит только в один крест (свой собственный), а любая другая клетка таблицы входит ровно в два таких креста.
  Далее можно рассуждать по-разному.

  Первый способ. Рассмотрим натуральное число от 1 до 25, отсутствующее на выделенной главной диагонали (такое наверняка найдётся, так как на диагонали всего лишь 13 клеток). Пусть все клетки главной диагонали – хорошие, тогда это число входит в каждый из тринадцати крестов ровно один раз. Но любое число, стоящее вне главной диагонали, должно входить в два креста, поэтому все кресты должны разбиваться на пары, а для тринадцати крестов это невозможно. Противоречие.

  Второй способ. Для того, чтобы число 1 встретилось в каждом из 13 крестов, оно должно быть записано в таблицу не менее семи раз. Это же можно сказать о каждом из двадцати пяти данных чисел. Значит, для того, чтобы все клетки рассматриваемой главной диагонали были хорошими, потребуется заполнить не менее чем  7·25 = 175  клеток. Но в таблице всего  13·13 = 169  клеток. Противоречие.

  Таким образом, все клетки главной диагонали не могут оказаться хорошими.


Ответ

Не могут.

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

олимпиада
Название Окружная олимпиада (Москва)
год
Год 2015
класс
Класс 8
задача
Номер 8.6

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

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