Есть квадратное поле.
На нём 1 ведьма(бабушка девочки Тани, наверное) и 3 охотника на ведьм
Охотники видят на 1 клетку по горизонтали, вертикали, диагонали, та что их область видимости квадрат 3х3
Охотник ловит ведьму если она попадает в поле его видимости
Ведьма всегда знат где охотники, охотники никогда не знают где ведьма, пока не увидят её
За единицу времени все охотники и ведьма сдвигаються на 1 соседнюю клетку по горизонтали, вертикали, диагонали или остаються на месте
Предположим, что изначально охотники в 3-х углах квадрата, а ведьма в 4-м
Есть ли стратегия для охотников позволяющая поймать ведьму?
Каков максимальный размер поля на котором можно поймать ведьму?
Можете ли вы найти стратегию позволяющую поймать ведьму так быстро, как это возможно?

10 на 10 ловится по-любому.

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

11 на 11 по этому же алгоритму — тоже.

Да что ж такое — 13 на 13 тоже.

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

FS>Да что ж такое — 13 на 13 тоже.
Думаю, что раз уже на ведьм, то 13х13 предел

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

A>Есть квадратное поле.
A>На нём 1 ведьма(бабушка девочки Тани, наверное) и 3 охотника на ведьм

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

Недостатки решения —
1) максимальное время поимки неограничено
2) не работает, если ведьма может предвидеть действия охотников

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

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

FS>>Да что ж такое — 13 на 13 тоже.
A>Думаю, что раз уже на ведьм, то 13х13 предел

решение 14x14 (за конечное время):

Привет, Chorkov.

C>решение 14x14 (за конечное время):

Увы, здесь ведьма пролезет:


Положение на 7 шаге показаны сплошными квадратиками. Когда центральный охотник шагает на поле с кружочком (согласно твоей стратегии), ведьма прыгает на поле со своим кружочком. Короче, положение на 8-м шаге показаны кружочками. И дальше уже ведьму не удержать...

Но идея несимметричной стратегии мне понравилась. Успехов в борьбе с ведьмами

A>>Есть ли стратегия для охотников позволяющая поймать ведьму?

Les>Пусть охотники двигаются по полю случайным образом. Рано или поздно, они совершенно случайно воспроизведут ту последовательность действий, которая приведет к поимке ведьмы.

И это правильно .

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


A>>>Есть ли стратегия для охотников позволяющая поймать ведьму?

Les>>Пусть охотники двигаются по полю случайным образом. Рано или поздно, они совершенно случайно воспроизведут ту последовательность действий, которая приведет к поимке ведьмы.

А>И это правильно .

К сожалению нет.
Дело в том, что ведьма всегда контролирует ситуацию. И она совершенно детерминированно не допустит воспроизведения последовательности о которой тут пишут.

Допустим, что я играю с Вами в следующую игру. Вы кидаете кубик. После чего я кладу другой как мне вздумается. Я проигрываю, если сумма чисел четная. Как вы думаете, выграете ли Вы когда-нибудь? Воспроизведется ли когда-нибудь случайная последовательность, приводящая к Вашему выигрышу?

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

A>Здесь противоречие возникает с тем, что у меня всегда есть стратегия не проиграть! И действую я не вслепую и обдуманно. На большом поле у ведьмы тоже всегда есть стратегия не проиграть.

Да действительно. Жаль, а в теории выглядело красиво.

A>Здесь противоречие возникает с тем, что у меня всегда есть стратегия не проиграть! И действую я не вслепую и обдуманно. На большом поле у ведьмы тоже всегда есть стратегия не проиграть.

Хотя если подумать, то еще можно зацепиться за этот метод. Задача сводится к нахождению способа поймать ведьму при любых начальных условиях. Более того даже не поймать но предложить метод по которому ведьма может спастить только угадав с определенной вероятностью следующие дейсвия охотников. Понятно что при случайном бесконечном варианте такой метод сработает, и сработает настолько много раз что ведьма однажды не угадает.

Так например. 11x11. Если охотники встанут в горизонтальный ряд в центре, заняв поле 9*3 — 2 вертикальные по бокам поля свободны, далее они начинают спускаться вниз(вверх) при этом смещаясь то влево то вправо — проскочить в полоску не удастся она закроется на следующий ход. При неудаче можно повторить. Способ не вероятностный, от начальных координат ведьмы не зависит, причем гадать не надо.

Потом одну полоску можно делать шире в 2клетки, тогда это поле уже 12x12 и делать также провести шатание потом спускаться на одну клетку, потом снова. Так ведьма может пролезть, при условии что она заранее знает что с этой стороны на этот раз будет проход, но если это случайно то однажды она не угадает.