Пехотинец и артилерист

[ewert]

Профессор Снэйп в сообщении #367371 писал(а):

Ах, если бы все теоремы доказывались так же!.. "Теорема верна, иначе, по-моему, точно никак"

А то ж.

Я привёл некоторые интуитивные соображения в пользу.

Уточню (ну или добавлю, или повторю, или конкретизирую). Убить мы его сможем, лишь если тем или иным способом зажмём. Поскольку информации о его положении у нас в каждый данный момент нет никакой -- кроме того, что чётность и нечётность его позиции чередуются.

А зажать можно, лишь двигаясь в одну какую-то сторону (ведь про абсолютную-то позицию информации у нас в любой конкретный момент точно нет). И тут все конфигурации различаются опять же одним -- чётностью или нечётностью расстояний между нами перед очередным выстрелом. И поскольку всё, что мы знаем -- это что та чётность сохраняется -- мы вынуждены сделать и обратный проход.

Всё это -- всего лишь интуитивные соображения, но они выглядят убедительными (во всяком случае, для меня). Думаю, что им можно придать и точный математический смысл. Только мне лень думать.

---------------------------------------------
Хотя не спорю -- это действительно хорошее усиление исходной задачки.

[Профессор Снэйп]

ewert в сообщении #367385 писал(а):

Всё это -- всего лишь интуитивные соображения, но они выглядят убедительными (во всяком случае, для меня)...

Увы. Человек, ни разу в жизни не видевший листа Мёбиуса, может быть убеждён, что таракан, не переползая через край листа, ни за что не перевернётся вверх ногами...

ewert в сообщении #367385 писал(а):

Думаю, что им можно придать и точный математический смысл.

Не только можно, но и нужно! Иначе, увы, никак!

-- Пт окт 29, 2010 00:52:49 --

Вот те же самые множества $B_\bar{a}$... К примеру, верно ли, что $B_{(1,60)} = B_{(60)}$. Если да, то "наименьшая убойная последовательность" не может начинаться с $1,60$.

Лень думать... увы, поздно уже. На досуге подумаем с утречка

[ewert]

Для тех, кому захочется-таки подумать (мне-то так и будет лень). Дополнительный фрагментик.

Допустим, мы двигаемся-таки вправо. Чем принципиально отличается наш удар по 59-й позиции -- от удара, допустим, на 58-й?...

Тем, что правее 59-й -- только одна позиция. Занимая или не занимая её (т.е. оказываясь справа или не оказываясь) -- пехотинец однозначно определяет свою чётность. Это и позволяет достаточно однозначно перебрать варианты.

А вот для любой более внутренней позиции -- вариантов существенно больше, что и сохраняет полную неопределённость прогноза.

[Lyosha]

Расстояние - разница между номером окопа в который попал артиллерист и номер окопа в котором находился пехотинец.Очевидно,что модуль расстояния не может возрастать до бесконечности и не является монотонной функцией времени.Расстояние может быть чётным или нечётным.Отсюда решение:пройтись подряд по разу с 2-го по 58-ой,дважды выстрелить в 59-ый и обратно с 58-го по 2-ой подряд по разу.

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