Олимпиадная задача по принципу Дирихле: максимальное количество ладей на доске
Задача
На шахматной доске расставили n белых и n чёрных ладей так, чтобы ладьи разного цвета не били друг друга. Найдите наибольшее возможное значение n.
Решение
Докажем, что при n > 16 осуществить указанную расстановку невозможно. Заметим, что на каждой горизонтали и на каждой вертикали могут располагаться ладьи только одного цвета (либо она может оказаться свободной от ладей). Условимся обозначать горизонталь (вертикаль) тем же цветом, что и цвет ладей, стоящих на ней.
Так как ладей больше 16, то белых горизонталей не меньше трёх.
Если белых горизонталей ровно три, то в одной из них – не менее шести ладей, то есть белых вертикалей не менее шести, а чёрных – не больше двух. Это, как показано выше, невозможно.
Итак, белых горизонталей – не меньше четырёх, значит, черных – не больше четырёх. То же верно и для чёрных вертикалей. Следовательно, чёрных ладей не больше 16. Противоречие.
Пример возможной расстановки при n = 16 см. на рисунке.
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь