Задача на логику. Помогите разобраться с формулировками.

А что надо? Зажечь свет?

т.е. отсюда следует что «орел» покрашен всегда в один цвет, а решка в другой, или нет?

Тут абстрактные монеты, без орла и решки. Но окраску они не меняют.

т.е. когда берешь монету можно определить в какую сторону ты её переворачиваешь или нет?

Что значит «переоврачивать в сторону»? Либо переворачиваешь монету, либо нет.

т.е. отсюда следует что «орел» покрашен всегда в один цвет, а решка в другой, или нет?

А какая разница? Название сторон для задачи значения не имеет, кроме цвета ничего не важно, это указано в условии.

отсюда следует что «орел» покрашен всегда в один цвет, а решка в другой, или нет?

Отсюда следует, что мы имеем четыре бита информации, свет загорается, когда все биты принимают значение 1, но конкретное состояние любого бита мы узнать не можем.

т.е. когда берешь монету можно определить в какую сторону ты её переворачиваешь или нет?

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

Ага, а самое простое решение - сбрутфорсить ответ.

А задача-то где?

На все вопросы, думаю ответ положительный.

По поводу стратегии.
Очевидно, что переворачивать монеты по 4 или по 3 не имеет смысла, так как переворачивание 4-х не изменяет состояния, 3-х - равносильно переворачиванию 1-ой.
Стратегия с переворачиванием по 2 монеты на каждом шагу неверная, так как возможна начальная ситуация с нечётным числом перевёрнутых монет.
Посему оптимальной стратегией будет либо переворачивание случайно выбранной монеты на каждом шагу, либо чередование с переворачиванием то одной монеты, то двух.

// либо спички...

когда берешь монету можно определить в какую сторону ты её переворачиваешь или нет?

Нет конечно. Окна замурованы, света нет. Орел и решку ты бы еще мог различить без света, а вот цвета уже точно нет. Да и задача теряет всякий смысл.

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

О каком решении идет речь, если нет задачи?

О каком решении идет речь, если нет задачи?

Как нет? Вы в замкнутом тёмном пространстве, не помните, кто Вы и как зовут. Зловещий голос из темноты повелевает Вам зажечь свечу. Задача как и в любой игре «Выжить»... Ну и понять - что за хрень случилась, так в любой игре жанра «survival horror»...

Может надо переворачивать одну и ту же монету. Перевнул нижнию справа, стол повернули опять ту же перевернул и т.д.?

Вас привязали к горящей машине сверхпрочной цепочкой, дали пилу и возможность перепилить цепочку. Пила перепилит её за 15 минут, но Вы можете вместо этого отпилить себе лодыжку за 10 минут. Что Вы сделаете?

Если я не напортачил с построениями, существует стратегия из 5 шагов, гарантировано включающая свет. Более коротких стратегий скорее всего нет.

Если машина не деревянная, то буду пилить цепочку, так как, чтобы решиться перепилить лодыжку, потребуется минимум 5 минут самоконцентрации.

Решение?

Решение?

Раз это задача от HR'ов, то публиковать решение здесь неуместно.

Раз это задача от HR'ов, то публиковать решение здесь неуместно.

А тебе и нечего публиковать. Нет тут алгоритма, который бы гарантированно сходился за 5 шагов. Даже если бы стол поворачивался на фиксированный угол, то только 14 шагов гарантированно включало бы свет — всевозможные сочетания поворотов по 1, 2 и 3 монеты.

А тебе и нечего публиковать

Давай мыло — скину решение. Или подумай еще.

Если я не напортачил с построениями, существует стратегия из 5 шагов, гарантировано включающая свет. Более коротких стратегий скорее всего нет.

Таки напортачил. Перепроверил: оказалось 7.

на какую должность такие задачи дают? и как их решать?

если бы стол не крутился на рандомный угол то всё относительно просто, можно было бы придумать кучу алгоритмов.
Самый глупый это, после каждого переворота монет делать обратный переворот, таким образом возвращая первоначальное состояние и там 7 вариантов получается, а вместе с обратными переворотами 14 ходов.

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

напиши мне как такое решать.
tdrive@tdf23.ru

Таки напортачил. Перепроверил: оказалось 7.

Число всевозможных расстановок 2^4=16, приводящих к верному решению 2 (все чёрные/белые), итого за 8-1 (-1, т.к. одно состояние уже рассмотрено - текущее, оно не включает свет) ходов мы можем гарантированно получить все монеты одного цвета, но при условии, что позиции монет не меняются.

Но тут после каждого хода производится рандомный сдвиг с сохранением бита, 7 ходов, имхо, не гарантирует...

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

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

всё не так плохо, нужно рассматривать диагонали, т.к. их состояние остаётся инвариантом относительно поворота итого сначала (1,0),(0,1),(0,0), где 0 - это цвета не совпадают, 1 совпадают.

Число всевозможных расстановок 2^4=16

с учётом неразличимости белого-чёрного 8, а с учётом неразличимости поворота 4

** *. *. *.
** ** *. .*

(1,0),(0,1),(0,0)

А если считать диагонали равноправными, получим вообще 2 состояния.

пока перерисую, но решения не вижу...

XX XO XO XO
XX XX XO OX

тогда необходимого состояния монет (все чёрные или белые) из любого другого состояния можно добиться переворотом любой одной монеты (4 варианта) или 3 варианта переворота по 2 монеты ( диагональ, высота, ширина) всего 7 вариантов.

получается шанс угадать 1/7

вижу почему 5 или даже 4, не вижу где проблема, сейчас попробую перепроверить.

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

при чём тут то что мы считаем? нас ведь интересует по факту, а по факту 16 возможный состояний.

Ты не учёл недетерминированность поворота стола.

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

Анализ показывает, что если у нас есть три возможных исходных конфигурации

ox ox ox
oo ox xo

С вероятностями (p_1, p_2, p_3), то после применения операции «повернуть одну» вероятности изменятся на (p_2 + p_3, 0.5 p_1, 0.25 p_1) и вероятность выиграть 0.25 p_1

после применения операции «повернуть две рядом» — (p_1, p_3, 0.5 p_2) и вероятность выиграть 0.5 p_2

после применения операции «повернуть две по диагонали» — (p_1, p_2, 0) и вероятность выиграть p_3

при определенной смене монеток возможен или выигрыш или переход в ограниченное подмножество, более узкое,

Таким образом можно диагонали исключить, но остальное исключить вряд ли получится.
изначально есть 7 вариантов приводящих к выигрышу, первым ходом меняем 2 монеты по диагонали, если не выиграли то диагональ больше вообще не трогаем, и для всех последующих попыток шанс угадать 1/6.

всё же 4.

1 0    1 1  1 0  1 1
0 0    0 0  0 1  1 0  

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

ты попробовал нарисовать, или так теоретизируешь?

как правильно указали выше состояния 1 и 4 эквивалентны. но для чистоты эксперимента я их оставил

3, первое и последнее эвивалентны.

ага, согласен.

в общем за 7 шагов решение гарантировано.

как и предложили выше, могу выслать на мыло.

а чё там рисовать?
Про поворот стола не понял. «всё остально это эти же состояния »
если у нас на столе например рандомно могут быть состояния
[code]
ox xo xx xx
xx xx xo ox
[/code]
и нужно сделать все «x», это решается с первого раза?? нет.
вот и в нашей задаче поворот стола говорит только о том, что мы не знаем какие монеты меняли предыдущим ходом => каждый новый ход = ходу при изначальных условиях.
Вот придумал только что диагонали можно исключить и увеличить шанс отгадать до 1/6

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

ну пришли мне tdrive@tdf23.ru

Есть похожая задача, но там можно чувствовать что куда переворачиваешь, задача про стаканы

ща в graphviz нарисую.

Уважаемый, свет зажечь нужно за конечное число шагов.

выcлал, думать есть ли более коротное решение, (при другом начале) леньь, но навреное невозможно

7 шагов это бесконечное число шагов?!