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

[maximkoo.livejournal.com]

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

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

БЧ
БЧ

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

БЧ
ЧБ

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

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

Comments

[paha-han.livejournal.com]

0. смотрим, делаем умное лицо, скрипим мозгом =)
1. суём шаловливые ручки в позиции 1 и 2 и делаем так, что б оба были допустим "вверх"
2. суём ручки в 2, 3 и если попадётся не в верх, то поднимаем его, теперь у нас 3 вверх, 1 вниз.
3. опять суём в 2, 3 - нащупали опущенный? да мы фортожопые! не нащупали, но зато мы умные, переводим 2 на позицию "вниз", трёшку не трогаем, теперь у нас есть ряд поднятых, и ряд опущенных.
4. суём руки в 1, 2 и переключаем оба, что б мы там не нашли. Мы или, таки, фортожопые, или у нас выключатели "шашечкой".
5. Суём руки в 2,3 и переключаем. Идём грабить награбленное, покупаем лучших наложниц, пьём холодное пиво, попутно дав взятку мулле, что б он объявил его не алкоголем и т.д. и т.п.

З.Ы. могу прислать экселёвский файл с наглядной агитацией, если скажете куда.

[vnarod.livejournal.com]

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

[brutus-cynicus.livejournal.com]

не получится. допустим
00
01
1.
10
00
2.
01
00
3.
11
01
4.
01
01
5.
11
00
6.
00
00 вроде бы на шестом открыли, но если диск повернуть перед шестым на 90 градусов:
5.
01
01
6.
10
01 в итоге дверь так и не открылась.

[paha-han.livejournal.com]

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

[blackyblack.livejournal.com]

Берем навскидку первый вариант и изменяем его по вашим правилам (даже не вращая):

0. 00
10

1. 10
11

2. 01
11

3. 10
10

4. 00
10

5. 10
11

6. 01
11

[wordsmsdnua.livejournal.com]

Ну если папу не пожалел то думаю доживет)

[paha-han.livejournal.com]

хотя не знаю, говорит ли он еще эту фразу, но, думаю, еще говорит.

[brutus-cynicus.livejournal.com]

диск вращается на произвольное число градусов. как отличить 12 и 23 это одно и то же.

[paha-han.livejournal.com]

не совсем понял вопрос, если вы про то, что диск всякий раз занимает разные положения, то считаем номером 1 ту ячейку которая оказывается во втором квадранте или вертикально верхнюю - на решении не отразится.
если вы имеете ввиду, что выключатель меняет положение при повороте диска на 180 градусов, то переименовываем верх и низ на "к центру", "от центра" и возвращаемся к исходной задаче.

[roman-pro.livejournal.com]

Напомнило задачу про нерешаемые пятнашки (http://ipuzzles.ru/15s/sem-loyd-15s-puzzle/), правда тут неразрешимость видна с ходу.

[maximkoo.livejournal.com]

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

[maximkoo.livejournal.com]

Да, может быть, в этом как раз и есть разгадка.

[brutus-cynicus.livejournal.com]

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

[paha-han.livejournal.com]

невозможно, т.к. 1 и 2 рядом, а 2 и 3 по диагонали. Как уже писал выше, могу скинуть наглядное решение в экселёвском файле.

[vaf77.livejournal.com]

знает, но не в состоянии осознать?
пример:
- училка знает, что мальчик на олимпиаде сдал в качестве решения задачи "многабукаф", которые лично она не осилила, но по итогам обсуждения работы Комиссией - работа заслужила высший балл;
- училка видит, что "многабукаф" ей никто другой из "её" детей объяснить не может, поэтому негодуэ на них, шо они дюже "тупые";
- она тупо не осознаёт связи между "многанипанятныхс*кабукаф", и смыслом задачи...

[vnarod.livejournal.com]

значит нужен ещё шаг: 14. Тогда за 6 шагов это невозможно.

[vnarod.livejournal.com]

да, Вы правы, я написал решение более усложнённого варианта, требующего 7 шагов.

[vnarod.livejournal.com]

я ответил ниже

[paha-han.livejournal.com]

тогда хорошо, что я не вчитывался в Ваше решение, завтра порешаю Ваш вариант задачи, но, честно говоря, он мне кажется нерешаемым.

[vnarod.livejournal.com]

Я же уже написал решение

[paha-han.livejournal.com]

именно этот факт заставляет меня попробовать её решить =)
Кстати, на всякий случай, в Вашем варианте нет совсем никакой информации о положении выключателя, или же решение принимается до изменения положения выключателя, но после совершения действия становится известен результат?

[brutus-cynicus.livejournal.com]

ошибочка 3.
11
10

[vnarod.livejournal.com]

информации о положении нет совсем. Если все выключатели становятся в одно положение - пещера с музыкой открывается. Если нет - ничего не происходит.

[paha-han.livejournal.com]

ОМФГ, я уже передумал о нерешаемости даже в такой ситуации, но семь итераций выглядят очень уж смелым. Вы, в этих ваших Джерсях, случайно, не программированием/математикой/физикой балуетесь? Это завтра придало бы мне дополнительную веру, что уложиться можно.

[brutus-cynicus.livejournal.com]

Да, согласен. Все верно, пяти шагов достаточно.