Олимпиадная задача про мамонта: максимальное размещение на шахматной доске, классы 8–10
Задача
Фигура мамонт бьёт как слон (по диагоналям), но только в трёх направлениях из четырёх (отсутствующее направление может быть разным для разных мамонтов). Какое наибольшее число не бьющих друг друга мамонтов можно расставить на шахматной доске 8×8?
Решение
Оценка. Из каждого мамонта выпустим три стрелки в тех направлениях, в которых он бьёт. Сопоставим стрелку диагонали (не обязательно главной), если мамонт, из которого ведёт стрелка, стоит в этой диагонали, а стрелка идёт вдоль неё. Тогда каждой диагонали сопоставлено не более двух стрелок: в противном случае две из них будут идти в одном направлении, и один из мамонтов будет бить другого. Поскольку диагоналей всего 30 (по 15 в каждом направлении), стрелок им сопоставлено не более 60, а значит, всего мамонтов не больше 60 : 3 = 20.
Три возможных примера расположения 20 мамонтов, не бьющих друг друга, показаны на рисунке.
Ответ
20 мамонтов.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь