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

Пришел Али-Баба к пещере сокровищ. Подслушал слова, что разбойники говорили. Дождался, пока они уедут и только собрался экспроприировать экспроприаторов ... да не тут-то было. Оказывается, чтобы включить систему голосового распознавания надо было ввести следующий хитрый код:

У пещеры стояла бочка с четырьмя отверстиями в крышке. Отверстия были расположены по окружности, были достаточно узкие, так что в одно отверстие можно было просунуть только руку. А увидеть, что там находится, - совсем было невозможно.

А находились там 4 стрелы - каждая напротив своего отверстия. Согласно инструкции (начертанной на стене пещеры) - 2 остриями вверх и 2 остриями вниз. Но какие как - неизвестно. Можно было засунуть в бочку через отверстия обе руки, ощупать стрелы и поменять ориентацию одной или обеих. Но как только хоть одна рука была вынута из бочки, стрелы начинали перемещаться по кругу достаточно быстро. Поэтому надо было вынимать обе руки сразу (во избежание травмирования) и определить на сколько переместились по кругу стрелы было невозможно. Система голосового распознавания включалась только после того, как все стрелы были сориентированы одинаковым образом.

Подумал Али-Баба и решил эту задачу. Причем кратчайшим способом (за наименьшее число попыток). Набрал золота, камней драгоценных и вернулся в Бухару. Да решил с дороги заглянуть в чайхану отпраздновать успех. Но оказывается, перед входом в чайхану стоит еще одна бочка. В ней - 4 селедки. Только сколько из них как ориентированы - неизвестно. Чтобы открыть двери тоже надо сориентировать всех селедок одинаково.

Удалось ли сметливому Али-Бабе испить чайку и сыграть с приятелями в нарды?

Хватаемся за произвольные стрелы. Если они одинаково расположены (1/3), то переворачиваем обе и вуаля. Если по-разному, то переворачиваем одну. И ждём пока найдём вторую стрелу, которую надо перевернуть каждый раз имея вероятность 50%. Те же 50% получим и вертя обе стрелы, если у них одинаковое направление, так что для чуйки тоже место остаётся.

Ну чисто теоретически так можно бесконечно ждать вторую стрелу.

Тем не менее, существует четкое решение за конечное число ходов.

В пещеру от 1 до 3 ходов, в чайхану - от 1 до 5.

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

Честно говоря, я уже и сам не помню, можно ли решить вторую задачу за 4 попытки. Давно я ее узнал - около 30 лет назад. Рассказал нам ее один чернявенький и смуглый приятель, за что и получил прозвище "Али-Баба".

Ну а раз так, то раскажу, что дальше было с Али-Бабой. Из задачи который, а не с нашим знакомцем.

Испил Али-Баба чайку. Выкурил кальян лучших зелий. Отдохнул душой и телом и собрался идти домой. А на выходе еще одна бочка стоит. Тоже с четырьмя отверстиями. Только предметы, которые в нее помещены, еще и в футляры заключены. А футляры одинаковые с обоих концов. Можно переворачивать как угодно, но понять, как же ориентирован предмет в футляре наощупь - нельзя. Задача прежняя - сориентировать предметы одинаково. При этом тоже неизвестно - сколько из них как изначально повернуты. Все просто и понятно - только вот исполнимо ли?

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

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

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

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

Исходя из отмеченных красным условий не вполне ясно:
1. Стрелы вращались произвольно и автономно или все синхронно делали одинакове число оборотов на 180 градусов; предполагаю второе, иначе определенного решения нет.
2. Вращались стрелы, которых коснулись, или все сразу; предполагаю второе, на предмет первого еще не думал.

Если предположения верны, то, если не ошибаюсь, для стрел, селедок и футляров в худшем случае достаточно соответственно 3, 3 и 7 попыток.

ПО КРУГУ они вращались. ПО КРУГУ - русским по белому написано же.

Т.е., если пронумеровать предметы, допустим, по часовой стрелке №№ 1, 2, 3, 4. Тогда предмет № 1 оказывается на месте предмета № 2, предмет № 2 оказывается на месте предмета № 3, предмет № 3 на месте предмета № 4, а предмет № 4 на месте предмета № 1. И так некоторое неизвестное число раз.

Ну, да, стрелы вращались (перемещались), по кругу, вокруг собственного центра - меняли свою ориентацию. Можно и так понять... И прояснить условия задачи можно спокойно, без хамства. Всего доброго...