Задача
Поле представляет собой клетчатый квадрат 41×41, в одной из клеток которого замаскирован танк. Истребитель за один выстрел обстреливает одну клетку. Если произошло попадание, танк переползает на соседнюю по стороне клетку поля, если нет – остаётся на месте. При этом после выстрела пилот истребителя не знает, произошло ли попадание. Для уничтожения танка надо попасть в него два раза. Каким наименьшим числом выстрелов можно обойтись для того, чтобы гарантировать, что танк уничтожен?
Решение
Пример. Окрасим клетки в шахматном порядке так, чтобы углы поля были чёрными. Пусть пилот сначала выстрелит по всем белым полям, затем по всем чёрным, а затем снова по всем белым. Если танк был на белом поле, то пилот его подобьёт в первой и второй сериях; если же на чёрном – то во второй и третьей сериях. При этом пилот совершит не более чем 41² + ½ (41² – 1) = ½ (3·41² – 1) = 2521 выстрел. Оценка. Пусть у пилота есть последовательность выстрелов, после которой танк будет гарантированно уничтожен. Ясно, что по любой клетке он должен выстрелить хотя бы раз (иначе танк в этой клетке не будет уничтожен).
Предположим, что есть две соседних клетки A и B, по которым он стрелял ровно по разу, причём выстрел по B произошёл позже. Тогда, если танк изначально находился в B, он мог после выстрела по B переползти в A, и второго попадания не произошло бы. Значит, таких пар клеток нет.
Разобьём всю доску на ½ (41² – 1) доминошек 1×2 и одну клетку. В каждую доминошку истребитель должен сделать как минимум три выстрела, а в оставшуюся клетку – хотя бы один выстрел. Итого, он сделал не менее чем ½ 3·(41² – 1)+ 1 = ½ (3·41² – 1) выстрелов.
Ответ
2521 выстрел.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь