|
|
 |
Условие
Клетки шахматной доски 8×8 как-то занумерованы числами от 1 до 32, причём каждое число использовано дважды. Докажите, что можно так выбрать 32 клетки, занумерованные разными числами, что на каждой вертикали и на каждой горизонтали найдётся хотя бы по одной выбранной клетке.
Решение 1
Выберем 32 клетки так, чтобы максимально возможное число строк и столбцов содержали хотя бы по одной выбранной клетке. Допустим, что в некотором ряду (столбце или строке) нет ни одной выбранной клетки. Без ограничения общности можно считать, что в левом столбце нет ни одной выбранной клетки. В этом столбце стоят разные числа (если бы в нём стояли два одинаковых числа, то одно из них было бы выбрано). Рассмотрим восемь соответствующих им клеток с теми же числами на оставшейся части доски размера 8×7 (заметим, что в этой части доски 24 свободные клетки). Пусть К – одна из этих клеток. В одном из рядов, содержащих К, других отмеченных клеток нет (иначе вместо К мы могли бы отметить соответствующую ей клетку в левом столбце). Отметим этот ряд.
Проделаем это для всех клеток левого столбца и вычеркнем отмеченные ряды. Останется доска из восьми рядов, площадь которой не больше 16. Значит, было выбрано не более 16 + 8 = 24 чисел. Противоречие.
Решение 2
Всего есть 232 выборов 32 клеток (из каждой пары клеток, занумерованных одинаково, надо выбрать одну). Оценим число плохих выборов. Пусть в первом столбце нет выбранных чисел. Это значит, что в нём все числа различны, поэтому таких выборов 224. Умножая на число срок и столбцов, получим 228 < 232. Поэтому хороших выборов очень много.
Замечания
8 баллов
