Сейчас мозголомку загадали...

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

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

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

Хак в виде стрельбы в торец ряда — запрещён.

По простреленным коробкам мышь не бегает?

Здравствуйте, Кодт, Вы писали:

Для N=3 палить два раза в среднюю. Дальше — надо подумать...

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, Кодт, Вы писали:

D>Для N=3 палить два раза в среднюю. Дальше — надо подумать...

для N = 1 и N = 2 решения тоже несложны

VC>для N = 1 и N = 2 решения тоже несложны

для 4 тоже просто,
стреляем 2 раза в 3 затем 2 раза в 2.

Здравствуйте, tlamer, Вы писали:

VC>>для N = 1 и N = 2 решения тоже несложны

T>для 4 тоже просто,
T>стреляем 2 раза в 3 затем 2 раза в 2.

Не. Выживет, которая сидела в 1, потом перебежала во 2, потом в 3, потом в 4.

Здравствуйте, Кодт, Вы писали:
К>Сейчас мозголомку загадали...
К>N коробок стоят вплотную, в ряд.
К>В одной из коробок сидит мышь.
К>Между коробками прогрызены переходы.
К>У человека есть ружьё, из которого он стреляет по коробкам.
К>После каждого выстрела мышь, если в неё не попали, перебегает в соседнюю коробку (какую именно — неизвестно).
К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.
К>Хак в виде стрельбы в торец ряда — запрещён.

Надо разделить все коробки и расстрелять по очереди

Х>По простреленным коробкам мышь не бегает?
Тоже хотелось бы это знать.

Пронумеруем коробки слева направо от 0 до N. Стреляем сначала в коробку 0, потом 1, потом 2 и т.д. Максимум потребуется N выстрелов.

Здравствуйте, Кодт, Вы писали:

К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.

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

Здравствуйте, Кодт, Вы писали:

К>Сейчас мозголомку загадали...

К>N коробок стоят вплотную, в ряд.
К>В одной из коробок сидит мышь.
К>Между коробками прогрызены переходы.

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

К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.

К>Хак в виде стрельбы в торец ряда — запрещён.

Стреляем с первой по последнюю, потом с последней по первую.

Здравствуйте, rpaskomid, Вы писали:

R>Пронумеруем коробки слева направо от 0 до N. Стреляем сначала в коробку 0, потом 1, потом 2 и т.д. Максимум потребуется N выстрелов.

После первого выстрела мышь перебегает из коробки 1 в коробку 0.

Здравствуйте, Хнык, Вы писали:

Х>Стреляем с первой по последнюю, потом с последней по первую.

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

Сформулируем решение, как клеточный автомат.

Пусть m(t,i) — Мышь может быть в i-том ящике в момент t.
M(t) = {i|m(t,i)}
i от 0 до N-1.

Тогда m(t+1,i) = (i > 0) && m(t,i-1) || (i<N-1) && m(t,i+1).
Такой вот клеточный автомат. "Жизнь" все помнят?

Как уничтожать такой автомат? Т.е. как изменяя на каждом нагу состояние одной клетки довести автомат до пустого состояния?

Мое решение: в два этапа.
На первом этапе создаем стабильную структуру с циклом в два шага.
На втором убиваем её.

Понеслась:
M(1) = {0,N-1}
Выстрел 1:
В ячейку 1. Если мышь жива, то она либо в ячейке 0, либо в [2,N-1];
Где она будет на шаге 2? Где угодно, но не в 0, т.к. в 1 её нет, а больше ей туда бежать не откуда.

Т.е. M(2) = {1,N-1}

Выстрел 2:
В ячейку 2. Если мышь жива, то в ячейке 1 её уже не будет.

M(3) = {0}|{2,N-1}

Выстрел 3:
В ячейку 3.
M(4) = {1}|{3,N-1}

Выстрел 4:
В ячейку 4.
M(5) = {0}|{2}|{4,N-1}

И т.д. после каждого шага у нас слева образуется пульсирующая структура. "Мыши Шредингера" носятся из четных в нечётные ячейки. Справа все ячейки ими заняты.

Как только у нас образовалась стабильная пульсирующая структура, мы просто уничтожаем её слева направо.
Перечитал, аж стало мышь жалко. Трагическая предопределённость.

Здравствуйте, sugarde, Вы писали:

Т.е. 2*N +- 1 на четность/нечётность N — должно хватить.
Два обстрела слева направо гарантировано убивают мыша.

S>Перечитал, аж стало мышь жалко. Трагическая предопределённость.
Сила!

и убивать никого не надо, сама убежит

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

S>Выстрел 1:
S>В ячейку 1. Если мышь жива, то она либо в ячейке 0, либо в [2,N-1];
S>Где она будет на шаге 2? Где угодно, но не в 0, т.к. в 1 её нет, а больше ей туда бежать не откуда.

S>Т.е. M(2) = {1,N-1}

S>Выстрел 2:
S>В ячейку 2. Если мышь жива, то в ячейке 1 её уже не будет.

Почему не может быть так (если всего 4 коробки — 0, 1, 2, 3, мышь пряталась в 0):

Шаг | Выстрел в | Мышь
1   | 1         | 0 -> 1
2   | 2         | 1 -> 2
3   | 3         | 2 -> 3
4   | 0         | 3 -> 2
5   | 1         | 2 -> 1
6   | 2         | 1 -> 2
7   | 3         | 2 -> 3

_>Почему не может быть так (если всего 4 коробки — 0, 1, 2, 3, мышь пряталась в 0):
Для четного количества коробок второй раунд надо начинать с четной коробки, то есть с первой. Мышь без шансов!