|
|
 |
Условие
а) На каждом из полей верхней и нижней горизонтали шахматной доски 8×8 стоит по фишке: внизу – белые, вверху – чёрные. За один ход разрешается передвинуть любую фишку на соседнюю свободную клетку по вертикали или горизонтали. За какое наименьшее число ходов можно добиться того, чтобы все чёрные фишки стояли внизу, а белые – вверху?
б) Тот же вопрос для доски 7×7.
Решение
а) Оценка. Чтобы попасть на противоположную сторону доски, фишке надо сделать семь вертикальных ходов. Но хотя бы одна из двух фишек, стоящих на одной вертикали, должна сделать горизонтальный ход (иначе им не разминуться). Поэтому вместе эти фишки сделают не менее 15 ходов. А таких пар на доске восемь. Значит, менее чем за 120 ходов добиться требуемой расстановки нельзя.
Пример. Разобьём фишки на четвёрки, стоящих на двух соседних вертикалях. Каждую четвёрку передвинем за 30 ходов так, как показано на рисунке:
б) Пример. Покажем, как получить требуемое расположение за 92 хода, сделав 14·6 = 84 хода по вертикали и 8 ходов по горизонтали. На трёх парах вертикалей поменяем фишки местами, как в пункте а), сделав 6 горизонтальных ходов. Два оставшихся горизонтальных хода израсходуем на последней вертикали: белая фишка на полпути пропускает чёрную и возвращается на вертикаль.
Оценка. Из решения п. а) ясно, что нужно не менее чем (2·6 + 1)·7 = 91 ход. То, что этого не хватит, можно показать по-разному.
Первый способ. Если бы 91 хода хватало, то на каждой вертикали ровно одна из фишек осталась бы, а другая ушла бы на соседнюю, то есть сменила бы чётность вертикали. При этом на трёх чётных вертикалях должно остаться три фишки, и еще на них должны попасть четыре фишки с чётных вертикалей, всего 7 фишек. Противоречие.
Второй способ. После каждого хода число фишек на белых полях меняется на 1, поэтому его чётность меняется (происходит чередование). Но в начале и в конце на белых полях фишек поровну, поэтому нужно чётное число ходов.
Замечания
баллы: 3 + 4
