Условие
Клетки шахматной доски занумерованы числами от 1 до 32 так, что
каждое число
использовалось дважды. Докажите, что можно выбрать 32 клетки,
занумерованные разными числами, так что на каждой вертикали и на
каждой горизонтали найдется хотя бы по две выбранные клетки.
Подсказка
Можно разбить доску на доминошки размером 1*2 клетки и выбрать
32 клетки,
занумерованные разными числами, так что из каждой доминошки
будет выбрано ровно по одному числу.
Решение
Разобьем доску на доминошки размером 1*2 клетки следующим образом.
Вначале разобьем доску на 4 квадрата 4*4. Затем два квадрата,
расположенные по диагонали, разобьем на вертикальные доминошки,
а два оставшиеся квадрата - на горизонтальные.
Нашей следующей задачей будет выбор 32 клеток,
занумерованных разными числами, так что из каждой доминошки
будет выбрано ровно по одному числу. При этом из каждой ветрикали
и из каждой горизонтали будет выбрано хотя бы 2 числа
(разбиение на доминошки проведено таким образом, что в каждой
горизонтали и каждой вертикали есть хотя бы две целых доминошки).
Итак, достаточно выбрать по одному числу из каждой доминошки.
Выберем одно из чисел, равных 1. Если второе число в доминошке,
в которой находится это число 1, равно m,
то это число отбрасываем. Затем выбираем единственное число m,
которое не отбросили (если m не равно 1).
Пусть в одной доминошке с этим числом m находится
число n, отбрасываем его. Затем выбираем единственное неотброшенное
число n (если n не равно 1).
В конце концов цикл замкнется, когда мы отбросим
второе число, равное 1.
Если после этого не все из чисел 1,2,...,32 выбраны, начнем новый цикл
и т.д. В конце концов из каждой доминошки будет выбрано по одному
числу
и каждое из чисел 1,2,...,32 будет выбрано по одному разу.
Источники и прецеденты использования
