Али-баба. например

[maximkoo.livejournal.com]

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

Вот вопрос, на который, я не знаю ответа. В восьмом классе на уроке информатики учительница задала нам задачу: Али-Баба подходит к пещере. У пещеры замок в виде четырёх бутылок, вставленных в четыре гнезда. Две бутылки белые, две чёрные, и расставлены они в квадрат вот в таком порядке:

БЧ
БЧ

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

БЧ
ЧБ

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

С тех пор я прямо даже не знаю, что и думать.

Comments

[lidenskap.livejournal.com]

Вот правильная формулировка:
"У входа в пещеру Али-Бабы
Опубликовано 27.05.2011
Категория:
Взвешивания и проверки
Сложность:
Средние задачи

У входа в пещеру, где хранятся сокровища Али-Бабы, стоит устройство, не позволяющее проникнуть в пещеру непосвящённому. Снаружи это устройство похоже на диск, в котором проделаны в виде квадрата четыре отверстия. Внутри каждого отверстия есть невидимый снаружи выключатель. Каждый выключатель имеет два положения: «вверх» и «вниз», причём легко определить на ощупь, в каком положении находится выключатель. Человек имеет право опустить руки в любые два отверстия и придать выключателям желаемое положение. После этого диск начинает быстро вращаться и останавливается в некотором положении. (При этом нельзя установить, как новое положение диска связано с предыдущим.) После этого вновь можно манипулировать любыми двумя выключателями. Дверь в пещеру откроется лишь в том случае, если все четыре выключателя окажутся в одном положении. Указанные манипуляции можно проделать не более шести раз. В противном случае на неудачника обрушится тяжёлая плита.

Смогли бы вы попасть в пещеру Али-Бабы?"

[wordsmsdnua.livejournal.com]

Ага и каждый раз отрезает по пальцу!

[wordsmsdnua.livejournal.com]

Далеко парень пойдет

[your-new-world.livejournal.com]

это совсем другая задача

[wordsmsdnua.livejournal.com]

Ну шансы есть, но я не силен в теории вероятности.

[brutus-cynicus.livejournal.com]

Чё то как то это тоже не решить. Сколько руки не суй, нет никакой гарантии что не суёшь в одни и те же отверстия.

[ezdakimak.livejournal.com]

На шизофрению? :) Можно прислушаться, а вдруг одна из дырок издает какой-то особенный звук? :)

[brutus-cynicus.livejournal.com]

Хотя нет, решение конечно есть... Туплю.

[brutus-cynicus.livejournal.com]

Не, не решаемо вроде.

[vnarod.livejournal.com]

12
34

переворачиваем:

1. 14
2. 12
3. 14
4. 1
5. 14
6. 12

[blackyblack.livejournal.com]

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

[mr-shmellbass.livejournal.com]

Хм... А вот это уже совершенно другие условия (см ниже.).

[vnarod.livejournal.com]

Именно эта задача была у меня пятой на олимпиаде, кажется, в пятом классе, ещё в 89 году. Только там был цилиндр с 4 стержнями, которые надо было переворачивать. По-моему, очень легко решается.

[blackyblack.livejournal.com]

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

[vnarod.livejournal.com]

Я описал ниже. Неправильного положения там не существует, все выключатели должны оказаться в одинаковом положении, неважно в каком - или все включены или все выключены. В моём алгоритме, когда я пишу "14" это означает переключить выключатели, находящиеся по диагонали, 1-4 или 2-3 это не имеет никакого значения. "12" - выключатели рядом.

Теперь понятно?

[mr-shmellbass.livejournal.com]

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

[blackyblack.livejournal.com]

В этом и вопрос. Можно ли потрогав переключатели не переключать их, а трогать следующий и чтобы диск не вращался. Тогда можно решить задачу за 1 заход. :)

[mr-shmellbass.livejournal.com]

Ну тогда сбутылками всё таки интереснее, там нужно сдлать допущение, а здесь всё уже разжёвано.

[mr-shmellbass.livejournal.com]

Можно, ибо это не противоречит условиям.

[maximkoo.livejournal.com]

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

Кстати, да

[ermiak.livejournal.com]

Дополнительный вопрос по "инженерному" подходу: "Сколько рабов потребуется Али-Бабе для взлома защиты брутфорсом?". Вариант инженерного решения "тротил" исключаем по причине того, что пещера находится под защитой ЮНЕСКО.