СПбГУ 2024, 10–11 классы, задача 1
( баллов) Хромая ладья бьёт ближайшие клеток слева, справа, сверху и снизу (т. е. на бесконечной клетчатой плоскости она бы била клеток, не считая той, на которой стоит). Какое наибольшее количество не бьющих друг друга хромых ладей можно поставить на доску так, чтобы они не били друг друга?
Ответ
Ответ: .
Решение. Обозначим через — -ю по горизонтали и -ю по вертикали клеточку; от до . Будем расставлять хромые ладьи «диагоналями»:
- на , где от до ;
- на и на , где от до ;
- на и на , где от до ;
- и т. д.
- на и на , где .
Легко заметить, что при такой расстановке хромые ладьи не бьют друг друга, т. к. расстояние между ними в любой горизонтали и в любой вертикали ровно клеток. Вычислим количество расставленных хромых ладей:
Теперь покажем, что большее количество хромых ладей на заданном поле не расставить. Рассмотрим полосу поля размера ( строк во всю длину поля). В такой полосе нельзя расставить более хромых ладей, т. к. иначе в какой-нибудь вертикали окажется более хромой ладьи и они будут бить друг друга. Наше поле разбивается на таких полос и остается полоска . В полоске можно расставить не более хромых ладей (потому что на любой полосочке — не более одной, а таких полосочек в полоске штук и ещё клеточка, на которую можно поставить одну хромую ладью). Таким образом, расставить более хромых ладей, чтобы они не били друг друга, на поле нельзя.
Верное решение