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

[maximkoo.livejournal.com]

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

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

БЧ
БЧ

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

БЧ
ЧБ

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

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

Comments

[paha-han.livejournal.com]

не знаю правильное ли у Вас решение, но у меня есть правильное =) притом, я уложился в пять подходов.

[vnarod.livejournal.com]

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

[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]

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

[paha-han.livejournal.com]

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

[paha-han.livejournal.com]

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

[vnarod.livejournal.com]

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

[paha-han.livejournal.com]

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

[vnarod.livejournal.com]

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

[paha-han.livejournal.com]

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

[vnarod.livejournal.com]

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

[paha-han.livejournal.com]

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

[vnarod.livejournal.com]

эта задача с олимпиады для 5 класса советской школы. Нет там никакой сложности, просто рассмотрите три возможных варианта начала и всё.

[paha-han.livejournal.com]

мне, почему-то, кажется, что оригинальные условия - те которые решил я. Плюс, ЕМНИП, олимпиады были с 7-8 классов, а если Вы в 89ом были в пятом классе, то разница у нас всего-то год или два (или два-три, если у Вы отучились в четвёртом). Впрочем, это не важно, завтра порешаю.

[vnarod.livejournal.com]

Олимпиады в моё время были с 4го класса. С годом я опечатался, я в 5м классе был в 79м, так что разница у нас побольше.

Про оригинальные условия - не понял. Это просто две разные задачи. У меня была с цилиндром, в котором было 4 двухцветных стержня, которые нужно было переворачивать в темноте и который вращался.

[paha-han.livejournal.com]

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

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

[brutus-cynicus.livejournal.com]

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

[paha-han.livejournal.com]

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

[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 по диагонали. Как уже писал выше, могу скинуть наглядное решение в экселёвском файле.

[brutus-cynicus.livejournal.com]

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