Пехотинец в графе



жүктеу 20.39 Kb.
Дата11.08.2018
өлшемі20.39 Kb.

Пехотинец в графе

Система укреплений состоит из блиндажей. Некоторые из блиндажей связаны траншеями, причем из любого блиндажа можно перебежать в какой-нибудь другой. В одном из блиндажей спрятался робот-пехотинец. Пушка может одним выстрелом накрыть любой блиндаж. В каждом промежутке между выстрелами пехотинец обязательно перебегает по одной из траншей в соседний блиндаж (даже если по соседнему блиндажу только что стреляла пушка, пехотинец может туда перебежать). Оператор пушки хочет поразить робота выстрелом за конечное число выстрелов (не обязательно ограниченное). При уничтожении робота оператор об этом узнает.



  1. Система блиндажей представляет собой ряд из 1000 окопов. Можно ли поразить робота, если (а) известно только то, что он находится в окопе с чётным номером; (б) у оператора нет никакой информации о положении пехотинца?

  2. Пусть ряду из 1000 окопов от 999-го окопа в сторону были вырыты последовательно 2 окопа (т.е. из 999 можно теперь ещё в окоп 999а, а из того уже в окоп 999б). Может ли теперь поймать робота?

Назовём систему укреплений надёжной, если у оператора нет гарантированной стратегии поражения пехотинца (то есть такой последовательности выстрелов, благодаря которой пушка поразит робота независимо от его начального положения и последующих передвижений). Например, можно представить, что в укрепления запустили робота-телепата: он читает мысли оператора — и при возможности побежит в блиндаж, который не будет обстрелян следующим, а также может выбрать своё начальное положение. Очевидно, что в надёжной системе робота-телепата подстрелить не удастся.

  1. Докажите, что система укреплений, изображённая на рисунке (будем называть её трилистником), надёжна.

  2. Найдите все такие надёжные системы, которые перестают быть надёжными при выкидывании любой траншеи.

  3. Докажите, что любая система, которую можно «ухудшить», закопав некоторые траншеи, до надёжной — надёжна.

  4. Опишите все системы, в которых пушка может наверняка подстрелить робота.

Ещё задачи


  1. Заяц прячется от охотников в вершинах куба. Охотники могут одновременно выстрелить в три вершины. Если они попадут в вершину, где прячется заяц, то он будет подстрелен и охотники об этом сразу узнают, если он был другой вершине, то он после выстрела перепрячется в вершине, соседней по ребру с той, где он сидел. Могут ли охотники поймать зайца?

  2. Город Полосочный представляет собой клетчатую полоску , где каждая клетка — район: длина города с запада на восток 1000 районов, а ширина с севера на юг — 2 района. Комиссар знает, что где-то в городе скрывается Злодей. Каждый час силы полиции могут совершить облавы только в двух районах. Во время облавы злодей обязательно будет пойман. Если Злодей не был пойман, он случайным образом переходит в один из четырёх соседних районов: либо через сторону на запад или восток (но не на север или юг), либо по диагонали. Сможет ли Комиссар поймать злодея и, если сможет, через сколько часов?

Сириус, 7A класс, 7 сентября 2016 г, http://www.ashap.info/Uroki/Sirius/1609/index.html


Достарыңызбен бөлісу:


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет