Побег мегамозга — 2 Опции

[idler_]

Привет!

Предлагаю очень увлекательную задачку

Компьютерная игра. На уровне М=1,2,3... появляется колесо, на его ободе на одинаковом расстоянии друг от друга расположены М круглых дверей. Клик по двери открывает ее, и игрок видит, какой знак находится внутри: плюс или минус. Клик по знаку меняет его на противоположный. Если все знаки за дверями одинаковы – звучат фанфары и игра переходит на следующий уровень М=М+1.
Перед каждым ходом колесо вращается, после остановки невозможно установить, какие двери открывались на предыдущем ходу.
На каждом ходу игрок заказывает, сколько дверей будет открывать, например, N. С него списывается N! (N факториал) жизней. Открыв N дверей (возможно, последовательно, т. е. выбор каждой следующей двери может зависеть от увиденного ранее), игрок по своему усмотрению манипулирует со знаками и закрывает двери. Программа проверяет не закончен ли уровень. Если нет, то следует новый ход.

Цель: проходить уровни, теряя наименьшее число жизней.

Примеры игры.
Уровень 1. М=1. Звучат фанфары, игра переходит на уровень 2.
Уровень 2. М=2. Раз фанфары не звучат, то знаки за дверями разные, поэтому достаточно открыть одну дверь и поменять знак. Списывается 1!=1 жизнь. Игра переходит на уровень 3.

Предлагаю заинтересовавшимся попробовать свои силы. Рассматриваем уровни с 3-го по 10-й.

Как проверяться? Вы выбираете M от 3 до 10 и пробуете найти какой-нибудь ответ. Найденный способ высылаете мне личным сообщением. В ответ я вам говорю, верный ли у вас способ. Если способ верный, дополнительно я сообщаю, можно ли этот уровень можно пройти потеряв меньшее число жизней (по имеющейся у меня информации).

"Ответы", которые у меня есть, были предоставлены одним из участников соревнования, где была эта задача. Их оптимальность, конечно, не доказана. То есть мой ответ "у меня нет решения лучше" не означает, что решение нельзя улучшить.

[panda-pandus]

А минимизировать надо мат ожидание потерянных жизней или их потерю в худшем случае?

[alan]

А минимизировать надо мат ожидание потерянных жизней или их потерю в худшем случае?

В худшем, насколько я знаю из общения с idler_.

[idler_]

А минимизировать надо мат ожидание потерянных жизней или их потерю в худшем случае?

alan верно ответил, минимизируем потерянные жизни в худшем случае.

[SusAnna]

Расположение дверей на колесе остается неизменным?
т.е. если, к примеру, у меня 3 двери 123, на предыдущем ходе я открыла 12 и установила обе в +/-, если я открываю следующим ходом дверь 1, могу ли быть уверена что справа от нее дверь 2 с установленным мною +/-? это грубый пример) понятно, что у меня нет номеров дверей и я не знаю действительно ли я открыла дверь 1 или нет) важно понять двери не меняя орентира просто крутятся в неизвестном направлении и на неизвестный угол поворота? или же можно сказать что они перемешиваются между собой в случайном беспорядке?
и Традиционный вопрос, фанфары звучат после закрытия двери? или я могу открыть 2 двери поменять значение знака в одной из них, если не было фанфар поменять значение в другой?

[alan]

SusAnna, задача равносильна побегу мегамозга, со следующими отличиями:
1. Дырок-дверей, не 4, а M.
2. Рук не 2, а M.
3. Можно использовать любое число рук N: 1 <= N <= M
4. За одну попытку снимается N! жизней.

[Vokebizak]

SusAnna, задача равносильна побегу мегамозга, со следующими отличиями:
1. Дырок-дверей, не 4, а M.
2. Рук не 2, а M.
3. Можно использовать любое число рук 1 <= N <= M
4. За одну попытку снимается N! жизней.

Если рук М, то смысл в задаче? Мы ведь можем сразу проверит М дырок и установить нужный нам порядок

[idler_]

Расположение дверей на колесе остается неизменным?
т.е. если, к примеру, у меня 3 двери 123, на предыдущем ходе я открыла 12 и установила обе в +/-, если я открываю следующим ходом дверь 1, могу ли быть уверена что справа от нее дверь 2 с установленным мною +/-? это грубый пример) понятно, что у меня нет номеров дверей и я не знаю действительно ли я открыла дверь 1 или нет) важно понять двери не меняя орентира просто крутятся в неизвестном направлении и на неизвестный угол поворота? или же можно сказать что они перемешиваются между собой в случайном беспорядке?

Относительное расположение дверей неизменно, абсолютное меняется (иначе зачем крутить?).
То есть за дверью X по часовой стрелки всегда следует одна и та же дверь, но где будет располагаться дверь X после прокрутки колеса, неизвестно.

и Традиционный вопрос, фанфары звучат после закрытия двери? или я могу открыть 2 двери поменять значение знака в одной из них, если не было фанфар поменять значение в другой?

Фанфары звучат после закрытыя дверей.

Если рук М, то смысл в задаче? Мы ведь можем сразу проверит М дырок и установить нужный нам порядок

Вы действительно можете сразу проверить M дырок и установить нужный вам порядок, но потеряете при этом M! (M факториал) жизней. Наша же цель минимизировать число потерянных жизней на каждом уровне игры.

[idler_]

Для M=3 прислали оптимальный вариант.
Остальные уровни пока ждут своего Мегамозга

[alan]

Для M=3 прислали оптимальный вариант.
Остальные уровни пока ждут своего Мегамозга

Я тебе присылал для 3 и 4 оптимальный

[idler_]

Я тебе присылал для 3 и 4 оптимальный

По условиям, озвученным в первом посте, требуется отправлять решения в PM
Ладно, давай не будем засорять тему)

[0]

Выбор двери может основываться на увиденном?
К примеру я заказал 2 двери, открываю 1ую и если вижу + то вторую, в противном случае четвертую?

[idler_]

Выбор двери может основываться на увиденном?
К примеру я заказал 2 двери, открываю 1ую и если вижу + то вторую, в противном случае четвертую?

ответ в другом сообщении.

Сообщение было отредактировано alan: 12.6.2014, 11:31

[idler_]

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

Выбор двери может основываться на увиденном?
К примеру я заказал 2 двери, открываю 1ую и если вижу + то вторую, в противном случае четвертую?

Правильный ответ на этот вопрос: да, может. При этом количество открываемых дверей на каждом уровне вы определяете заранее, но открывать их можете последовательно.


Внёс это уточнение в исходное сообщение.