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

[maximkoo.livejournal.com]

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

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

БЧ
БЧ

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

БЧ
ЧБ

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

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

Comments

[vnarod.livejournal.com]

12
34

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

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

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

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

[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 в итоге дверь так и не открылась.

[vnarod.livejournal.com]

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