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