|
|
 |
Условие
В каждой клетке таблицы размером 13×13 записано одно из натуральных чисел от 1 до 25. Клетку назовём хорошей, если среди двадцати пяти чисел, записанных в ней и во всех клетках одной с ней горизонтали и одной с ней вертикали, нет одинаковых. Могут ли все клетки одной из главных диагоналей оказаться хорошими?
Решение
Для каждой клетки одной из главных диагоналей рассмотрим крест совокупность из двадцати пяти клеток: её саму и все клетки, стоящие с ней в одной горизонтали или вертикали.
Рассмотрим все кресты, образованные клетками выделенной главной диагонали. Заметим, что каждая клетка этой диагонали входит только в один крест
(свой собственный), а любая другая клетка таблицы входит ровно в два таких креста.
Далее можно рассуждать по-разному.
Первый способ. Рассмотрим натуральное число от 1 до 25, отсутствующее на выделенной главной диагонали (такое наверняка найдётся, так как на диагонали всего лишь 13 клеток). Пусть все клетки главной диагонали – хорошие, тогда это число входит в каждый из тринадцати крестов ровно один раз. Но любое число, стоящее вне главной диагонали, должно входить в два креста, поэтому все кресты должны разбиваться на пары, а для тринадцати крестов это невозможно. Противоречие.
Второй способ. Для того, чтобы число 1 встретилось в каждом из 13 крестов, оно должно быть записано в таблицу не менее семи раз. Это же можно сказать о каждом из двадцати пяти данных чисел. Значит, для того, чтобы все клетки рассматриваемой главной диагонали были хорошими, потребуется заполнить не менее чем 7·25 = 175 клеток. Но в таблице всего 13·13 = 169 клеток. Противоречие.
Таким образом, все клетки главной диагонали не могут оказаться хорошими.
Ответ
Не могут.
