ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65252
Темы:    [ Теория алгоритмов ]
[ Шахматная раскраска ]
[ Разбиения на пары и группы; биекции ]
[ Доказательство от противного ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Поле представляет собой клетчатый квадрат 41×41, в одной из клеток которого замаскирован танк. Истребитель за один выстрел обстреливает одну клетку. Если произошло попадание, танк переползает на соседнюю по стороне клетку поля, если нет – остаётся на месте. При этом после выстрела пилот истребителя не знает, произошло ли попадание. Для уничтожения танка надо попасть в него два раза. Каким наименьшим числом выстрелов можно обойтись для того, чтобы гарантировать, что танк уничтожен?


Решение

  Пример. Окрасим клетки в шахматном порядке так, чтобы углы поля были чёрными. Пусть пилот сначала выстрелит по всем белым полям, затем по всем чёрным, а затем снова по всем белым. Если танк был на белом поле, то пилот его подобьёт в первой и второй сериях; если же на чёрном – то во второй и третьей сериях. При этом пилот совершит не более чем  412 + ½ (412 – 1) = ½ (3·412 – 1) = 2521   выстрел.

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


Ответ

2521 выстрел.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2014/2015
этап
Вариант 5
класс
Класс 9
задача
Номер 9.6

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .