М-да, облажался . Сам не пойму, как приход мыши справа упустил...

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

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

интересно еще обобщить задачу: после каждого выстрела мышь может перебежать на K коробок в одном направлении (K=0..число коробок от текущего положения до 1-й или N-й коробки).
Еще более общая постановка, при которой мышь на каждом шаге может перебежать на любое число из 0..K коробок, видимо существенно сложнее. Интересно, что в последнем случае ограничение про "одно направление" уже не имеет смысла

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

S>интересно еще обобщить задачу: после каждого выстрела мышь может перебежать на K коробок в одном направлении (K=0..число коробок от текущего положения до 1-й или N-й коробки).

Ну, это просто. Разбиваем наш зверинец на непересекающиеся {1,k+1,2k+1,...}, {2,k+2,2k+2,...}, ... и затем отстреливаем каждый из них.

S>Еще более общая постановка, при которой мышь на каждом шаге может перебежать на любое число из 0..K коробок, видимо существенно сложнее. Интересно, что в последнем случае ограничение про "одно направление" уже не имеет смысла

Я уже показал выше, что даже при выборе у мыши {-1,0,+1} она может выжить.
А если мышь бегает строго в одну сторону, то очевидная стратегия — отстрелять все коробки по очереди.

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

Кстати, вот интересная задачка от Конуэя.
Ангел и Демон

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

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

S>Кстати, вот интересная задачка от Конуэя.
S>Ангел и Демон

Супер! Читается на одном дыхании.
Хотя в целом задача не является обобщением. Основное отличие -- в нашем случае прострел коробки не означает, что в нее нельзя больше идти. Т.е. интерпретация задачи вроде такой: коробки выстроены на плоскости; есть ружье, из которого можно прибить мышь как только ее стало видно; за один ход можно сжечь одну коробку (нюанс, который обсуждается в статье, на счет того, что будет, если сжечь коробку с мышью, как там показано, не существенен); вопрос в том, можно ли за конечное число ходов уничтожить (т.е. либо обнаружить, либо сжечь) alpha-мышь?
На сколько я понял, задача решена только для alpha<2, а тому, кто решит ее для alpha=2, дадут $100.

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

S>Ангел и Демон

Нетопырь? А он мне говорил — ангел...

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

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

_>>Все-таки все математики чокнутые люди

Т>Это программисты чокнутые. Математик не стал бы с нуля нумеровать.
Выстрелы с еденицы пронумерованы

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

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

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

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

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

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



Пока тема не забылась... Как будем стерелять если 7 коробок стоят буевой Т

    K
    |
    K
    |
K-K-K-K-K

У меня получилось

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

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

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

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

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

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

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



_>Пока тема не забылась... Как будем стерелять если 7 коробок стоят буевой Т


_> K
_> |
_> K
_> |
_>K-K-K-K-K


_>У меня получилось


Что то с форматированием:

K
|
K
|
K-K-K
|
K
|
K

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

_>Пока тема не забылась... Как будем стерелять если 7 коробок стоят буевой Т

_>    K
_>    |
_>    K
_>    |
_>K-K-K-K-K

_>У меня получилось

m - мышь может быть
. - мыши заведомо нет
! - выстрел (в коробку, где мышь может быть; по заведомо пустым не стреляем)

m!mmm    .m!mm    m.m!m    .m!m.    m.m.m    .!.m.    ..!.m    ...!.    ..!..    .....
  m   ->   m   ->   m   ->   m   ->   !   ->   m   ->   .   ->   m   ->   .   ->   !
  m        m        m        m        m        .        m        .        m        .