Сегодня решал задачку, которая мне показалась интересной. Условие задачи следующее:
В ряд вырыто семь разных окопов, есть враг, который сидит в одном из них. Мы делаем выстрел по одному из окопов. Если мы попали в окоп, в котором сидит враг, то мы его убиваем (выигрываем), а если же попадаем в иной окоп, то он (враг) обязательно перебегает в соседний окоп (вправо или влево). Если после первого выстрела враг остался жив, то мы производим второй выстрел, третий и т.д. пока не убьем врага. Надо придумать стратегию выстрелов, которая бы гарантировала смерть врага.

Для тех, кого пугает в задаче слово "убить", можно заменить его на "нейтрализовать".

P.s. я придумал одну стратегию, но говорят, что существуют и другие. Предлагаю всем порешать .

Окопы закольцованы или из крайних можно попасть только в один соседний?
Вероятности перемещения вправо и влево известны?

Навскидку я бы шмалял по центральному постоянно. Рано или поздно он в нем, вроде как, окажется

1) Окопы расположены в ряд (1 2 3 4 5 6 7), то есть из окоп с номерами 1 и 7 можно попасть в окопы с номерами 2 и 6 соответственно.
2) Из окопов 1 и 7 он перемещается однозначно, а из остальных он может с равной вероятностью перемещаться вправо и влево.
3) Пока Вы будете стрелять все время по центру, враг может бесконечно бегать: 1 2 1 2 1 2 1 2 1 2 ... Такая стратегия не гарантирует смерти врага

Примерно так: 76543211234567. Идём справа налево. Если он "проскочил", значит, с чётностью не угадали. Меняем чётность двукратным повторением первой ячейки и снова делаем "обход". Теперь уже не прогадаем.

Не может. Про пьяного матроса задачу знаете? Переходя с равной вероятностью либо вперед, либо назад, он удаляется от исходной точки, причем x(t) = A*sqrt(t). Здесь тоже самое, поэтому через достаточно большое время он побывает во всех окопах. Так что стрелять можно куда угодно, лишь бы постоянно.

Тут не написано, что он меняет место дислокации с равной вероятностью. Он может обладать каким-то интеллектом. Да и решение, я полагаю, требуется конечное.

А это что?

Да, не заметил. В принципе, справедливо. Но, думаю, решение нужно конечное.

Я гарантирую, что 50 выстрелов хватит

Гарантируете с почти 100%-ной вероятностью. А я гарантирую со 100%-ной вероятностью, что 14 хватит при моём решении.

Он может перемещаться в место предыдущего выстрела во всех случаях, кроме крайних.

По-моему, стопроцентно выигрышной стратегии для стрелка не существует.

Хорошо, не правильно выразился, при Вашей стратегии нельзя сказать что за N выстрелов мы 100% убьем врага. При такой пальбе по врагу, чисто теоритически, мы можем разориться на выстрелах, а враг останется жив. Это ведь не хорошо

Не понял. Предложите вариант перемещения врага, при котором он избежит гибели при моём алгоритме. То есть число длины 14, состоящее только из цифр от 1 до 7, такое, чтобы все цифры на соседних разрядах различались на единицу, при этом ни на одном разряде не стояло того же числа, что стоит на аналогичном разряде числа 12345677654321.

676543232345...

Да, Вы правы. Эта стратегия похожа на выигрыш темпа в шахматах.

Можно я сделаю "Ня-ня-ня-ня-ня-ня" в стиле Эрика Картмана?
Кстати, ТС такую же стратегию придумал, интересно?

Можно даже как Нельсон Манс.

Моя стратегия состояла из двух частей:
1) первая череда выстрелов 1234567 убивает врага, если он был изначально в нечетном окопе
2) вторая череда выстрелов 11234567 убивает врага, если он был изначально в четном окопе

Goger привел такую же стратегию, ну точнее почти такую же

Пусть враг бегает так: 4321212121212... Своей стратегией Вы его не убьете

Вообще существует бесконечное множество таких стратегий.
Есть две подсетки движения по окопам, определяемых чётностью начального положения, как тут уже указали. Можно вначале одну нейтрализовать (на картинке показаны красным выстрелы), потом другую, а можно сразу обе - тоже правильно...

Вот какой подлый враг...

Во второй раз не надо два раза стрелять в первый окоп.
234567654321234

Точно я просто когда решал задачу, то сначала делал вторую очередь, потом первую. Та стратегия верна, так как 8 выстрелов не меняют четности окопа, перед второй очередью.. Если стрелять как я написал, то во второй очереди надо в 1-ку стрелять только один раз

Только последний выстрел в этой серии 100% лишний, т.к. изначально чётный враг и будет убит в чётном окопе. А так, похоже, вы-таки правы.

Согласен.

6,6,5,4,3,2,2,3,4,5,6
кажется так быстрее?
66 и 22 позволяет убить врага в 7 и 1й ячейке без лишней траты боезапаса

Теперь следующий шаг - анализ.
10 выстрелов - это минимальная стратегия? Доказать.
Обобщения. А если враг прыгает ровно через два окопа? А через к? А если несколько вариантов? Один - вправо, два - влево?
Интерпретация. Графики. Непрерывность.

шмаляем по два выстрела начиная с первого окопа
1ый окоп БАХ-БАХ
2ой БУХ-БУХ
3ий бац-бац
и так давим гада до последнего окопа
помоему 13 залпов хватает завалить самого хитрого ренегата

Неверная стратегия, так как при перемещении врага 6-5-4-3-2-1-2-1-2-... Вы его не убиваете => Ваша стратегия не гарантирует 100% смерть врага!

Стрелять нужно дважды в первый, дважды в третий, дважды в пятый и дважды в седьмой, потом в 6й, 5й, 4й, 3й, 2й и 1й. Тогда точно противник будет убит!)

Неверная стратегия, так как при перемещении врага 5-4-5-4-3-2-3-2-3-4-5-6-5-6-5. Вы его не убиваете => Ваша стратегия не гарантирует 100% смерть врага!

Стрелять сразу во все окопы!

Goger сразу правильно сказал
у меня с ним решение совпало
1..77..1

да ведь уже не впервый раз говорят так и в ответ получают, что решение не верно.
первый шаг должен начинаться с 2-2, либо 6-6, и после чего поочередно стрелять по окопам, если я конечно не ошибаюсь

1..77..2
действительно, он будет в чётном окопе если чо

По крайним не нужно вообще стрелять.
2345665432 либо 6543223456 это самые короткие стратегии.

это действительно так, хорошая задачка

Не согласен. Решение верно, но не оптимально.

1..77..1 - это неправильный ответ. Стреляйте постоянно в один и тот же 1 окоп. и вы его уничтожите, он сам нарвется на пулю он ведь передвигается, а вам зачем?

Данная стратегия приводит к 100%-ой смерти врага за конечное число выстрелов.

Если в данной задаче врагу еще добавить интеллект и возможность получения какой-нибудь информации о предыдущем выстреле (слева или справа, близко или далеко произошел выстрел..), то ваша стратегия сразу станет 100% неверной. А вышеприведенная останется применимой..