В некоторые 16 клеток доски 8×8 поставили по ладье. Какое наименьшее количество пар бьющих друг друга ладей могло при этом оказаться?
Это задача 10.5 Всероссийской олимпиады по математике 2005 года. Автор задачи - Е. Куликов.
Пусть на вертикали a стоят A ладей. Тогда на ней есть A-1 пара ладей, которые бьют друг друга. Аналогично с другими вертикалями. Так как количество ладей всегда 16, чтобы получить количество бьющих пар поменьше, надо вычесть как можно больше единиц. Мы сможем вычесть единицу восемь раз,например, если на каждой вертикали будет стоять по паре ладей. Тогда будет 8 пар бьющих друг друга ладей.
Аналогично количество пар ладей, бьющих друг друга по горизонтали, не меньше 8.
Значит, в сумме не менее 16.
Пример для 16 пар бьющих друг друга ладей получается, например, если расставить по 8 ладей на главных диагоналях.
Но понятно, что это не единственный пример. Можно задаться вопросом, а сколько таких примеров может быть? Эту интересную задачу, связанную с числами Стирлинга, я оставляю читателям.