Задача 67410
|
|
 |
Условие
На белых клетках шахматной доски 100×100 стоят 100 слонов, среди которых есть белые и чёрные. Они могут делать ходы в любом порядке и бить слонов противоположного цвета. Какого наименьшего числа ходов заведомо достаточно, чтобы на доске остался один слон?Решение
Алгоритм. Все ходы будем делать так, чтобы на доске оставались слоны обоих цветов, пока слонов хотя бы два.Если есть возможность сделать экономичное взятие (слон за один ход бьёт слона другого цвета, стоящего с ним на одной диагонали), делаем его.
В противном случае сделаем неэкономичное взятие (за два хода). Выберем двух слонов разного цвета и рассмотрим путь, по которому первый слон мог бы пройти ко второму за два хода (такой путь всегда есть). Если на этом пути есть ещё слоны, найдём среди них двух ближайших друг к другу слонов разного цвета, и пусть один из них возьмёт другого за два хода.
Изначально все слоны стоят на 99 белых диагоналях, параллельных главной белой диагонали. Тогда на одной из них стоит не меньше двух слонов. Назовём двух из этих слонов особыми. Если особые слоны разного цвета, экономичное взятие возможно уже на первом ходу вдоль этой диагонали; сделаем его.
Пусть эти особые слоны белые. Тогда при взятиях будем бить чёрными слонами белых. После того как будет взят первый особый слон, это ограничение снимается. Заметим, что сразу после этого возможно экономичное взятие.
Поскольку всего взятий 99 и хотя бы одно из них экономичное, потребуется не больше 2·99 – 1 = 197 ходов.
Оценка. Расставим по 50 слонов произвольного цвета на нижней и верхней строке доски. При этом на всех 199 белых диагоналях обоих направлений будут стоять слоны (угловые белые клетки доски мы считаем «одноклеточными» диагоналями). За ход число диагоналей, на которых есть слон, может уменьшиться не более, чем на 1 (поскольку «исчезнуть» может только та диагональ, с которой уходит слон, делающий ход). Когда останется один слон, занятых диагоналей будет 2. Итого, понадобится хотя бы 199 – 2 = 197 ходов.
