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

[12d3]

zZoMROT в сообщении #366172 писал(а):

расскажите ситуацию, когда расстояние меняется на 1, не понимаю

когда второй раз стреляют в 60-й окоп

[zZoMROT]

Точно Там же дважды в 60 стреляют. Спасибо

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

А каково минимальное количество снарядов, которое должен потратить артиллерист, чтобы наверняка поразить пехотинца?

(Оффтоп)

А артиллерист наш или немецко-фашистский?
А если пушку на бок поставить, она из-за угла стрелять сможет?

[warpod]

zZoMROT в сообщении #365777 писал(а):

Докажите, что артиллерист рано или поздно сможет попасть в окоп пехотинца.

Каждую минуту артиллерист стреляет в случайный окоп (распределение равномерное).
Если кол-во выстрелов -> бесконечность, то вероятность попадания -> 1, иными словами, рано или поздно артиллерист попадет в окоп пехотинца.

[ewert]

warpod в сообщении #367318 писал(а):

вероятность попадания -> 1, иными словами, рано или поздно артиллерист попадет в окоп пехотинца.

Неверно. Помимо того, что единичность вероятности ничем не обоснована: нулевая вероятность непопадания за бесконечное время -- вовсе не означает, что это событие (никогданепопадание) не случится.

-- Чт окт 28, 2010 20:15:14 --

(Оффтоп)

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

А каково минимальное количество снарядов, которое должен потратить артиллерист, чтобы наверняка поразить пехотинца?

119. Но в военное время это количество может достигать 384-х.

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

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

119. Но в военное время это количество может достигать 384-х.

А как доказывать, что именно 119? Почему для любой последовательности $a_1, \ldots, a_{118}$, составленной из натуральных чисел от $1$ до $60$, всегда найдётся последовательность $b_1, \ldots, b_{118}$ натуральных чисел из того же промежутка, такая что $|b_i - b_{i+1}| = 1$ и $b_j \neq a_j$ для всех $i \in \{ 1, \ldots, 117 \}$, $j \in \{1, \ldots, 118 \}$?

-- Чт окт 28, 2010 23:31:36 --

Кстати, про $119$ не было озвучено решение. Было про $120$ ($1,2,\ldots, 59,60,60,59, \ldots, 2,1$).

[ewert]

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

А как доказывать, что именно 119?

Предъявлением явного алгоритма действий пехотинца, на котором достигается именно 119 (а больше точно не понадобится).

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

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

Хотя вроде последний выстрел лишний

-- Чт окт 28, 2010 23:34:05 --

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

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

Мне не очевидно

Неочевидно в первую очередь то, что стрельба должна вестись "подряд" (то есть что $|a_i - a_{i+1}| \leqslant 1$).

-- Чт окт 28, 2010 23:34:54 --

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

Предъявлением явного алгоритма действий пехотинца, на котором достигается именно 119 (а больше точно не понадобится).

То есть разбор $60^{118}$ вариантов стрельбы?

[ewert]

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

Хотя вроде последний выстрел лишний

Последний был бы 120-тым, и он действительно лишний.

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

Вот, допустим, у нас всего $3$ окопа, а не $60$. Ясно, что достаточно два раза подряд выстрелить во второй окоп...

[EtCetera]

(Оффтоп)

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

допустим, у нас всего $3$ окопа

Допустим, у нас всего $1$ окоп...

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

EtCetera в сообщении #367361 писал(а):

Допустим, у нас всего 1 окоп...

Это Вы к чему?

Я про три окопа написал, чтобы продемонстрировать ewert'у, что стрельба "подряд, начиная с края" не всегда оптимальна.

[ewert]

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

Вот, допустим, у нас всего $3$ окопа, а не $60$. Ясно, что достаточно два раза подряд выстрелить во второй окоп...

Поправка принята. Действительно, достаточно 116-ти (т.е. начинать достаточно со 2-го, а приостанавливаться -- на 59-м). Но уж меньше-то, по-моему -- точно никак.

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

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

Но уж меньше-то, по-моему -- точно никак.

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

-- Пт окт 29, 2010 00:04:00 --

Хочется начать городить что-то типа следующего...

Предположим, что $\bar{a} = (a_1, \ldots, a_k)$ --- конечная последовательность из $k$ выстрелов. Тогда пусть $B_\bar{a}$ --- множество окопов, в которых может находиться пехотинец, при условии, что он не был убит этими выстрелами. Как $B_\bar{a}$ зависит от $\bar{a}$, какие тут закономерности?..

Интересно, что по поводу этой задачи думает "высокая теория игр"? Есть ли на форуме знатоки?

[EtCetera]

(Профессор Снэйп)

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

Я про три окопа написал, чтобы продемонстрировать ewert'у, что стрельба "подряд, начиная с края" не всегда оптимальна.

Я понял, что Вы хотели показать. Просто свою демонстрацию провели весьма негуманными (Комитет солдатских матерей протестует) методами, о чем я и попытался Вам намекнуть. Видимо, несколько неудачно, за что прошу меня извинить.