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

[maximkoo.livejournal.com]

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

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

БЧ
БЧ

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

БЧ
ЧБ

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

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

Comments

[langsamer.livejournal.com]

Возможно, тот уникум, который "решил только ее", на самом деле доказал, что задача решения не имеет, а не только сказал "не знаю как решить".

[svoloch-nk.livejournal.com]

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

[your-new-world.livejournal.com]

Например, тот мальчик был сыном директора Самой Престижной Школы :)

а задача решения не имеет. От перестановки мест слагаемых сумма не меняется :) как не меняй местами Б и Ч, Б и Б по диагонали не получится.

[wheyayeman.livejournal.com]

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

Поскольку операции явно обратимы, то задача сводится к тому, можно ли, меняя бутылки только по диагонали получить из пары (которая меняется между собой местами) БЧ (ЧБ) пару ББ (ЧЧ). Очевидно, нет, т.к. используя обратимость из пары ББ (ЧЧ) можно получить только её же.

[koza-nostra.livejournal.com]

Не имеет. Если только замок крутить нельзя)) там об этом ничего не сказано.

[e-will.livejournal.com]

училка дура, однозначно.
а задача, в таком виде, решения не имеет, и не может иметь

[edelveis8.livejournal.com]

училка бы сама показала решение.
да и зачем орать-то на школьников? :)

[rizjaya.livejournal.com]

мдя, разве что крест-накрест имелось ввиду не только по диагонали квадрата а еще и по горизонтали например. Ну и сходите же в конце концов в школу - узнайте! :)

[quaest.livejournal.com]

"И с тех пор он так и бегает в каске и смеется"

[full-dec.livejournal.com]

И да, в таком случае задача вполне засчитывается)

[honeyman.livejournal.com]

Обозначим белую бутылку за 0, а чёрную — за 1.

Исходное положение:
01
01

Целевое положение:
01
10

Свойством любого из разрешённых преобразований является то, что сумма цифр по диагонали сохраняется. К примеру, если бы у нас было положение, допустим,
23
58
, то у неё сумма одной диагонали — 2+8=10, а другой — 3+5=8.
Если мы меняем местами верхную правую цифру с нижней левой, то получается
25
38
, и сумма соответствующих диагоналей составляет 2+8=10 (не изменилась) и 5+3=8 (изменился порядок цифр, но цифры остались прежними, и сумма сохранилась).

А что с нашими условиями?

Изначальное условие:
01
01
, суммы каждой диагонали равны единице.
Целевое положение:
01
10
, суммы диагоналей равны 0 и 2. Что невозможно.

[lily-13.livejournal.com]

> что сумма цифр по диагонали сохраняется
эта штука называется умным словом "инвариант"

[lily-13.livejournal.com]

Она орёт, потому что сама не знает правильного решения.

[edelveis8.livejournal.com]

да ну. неврастеничка просто.

[honeyman.livejournal.com]

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

[mr-shmellbass.livejournal.com]

Сдаётся мне, что здесь важно то, как был поставлен вопрос, дословная формулировка...

[mr-shmellbass.livejournal.com]

И кстати, как сформулирована задача тоже очень важно, если вы привели именно ту формулировку, это одно, а если постарались отразить смысл - совершенно иной коленкор.

[drpancraft.livejournal.com]

ну это же шахматы, не может черный слон встать на белую клетку и наоборот

[wordsmsdnua.livejournal.com]

Ну переставить один раз, и повернуть на 90 градусов - получим то что надо, не?

[skvoznik.livejournal.com]

+

[lidenskap.livejournal.com]

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

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

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

[wordsmsdnua.livejournal.com]

Ну тогда решения нет при существующих условиях.

[your-new-world.livejournal.com]

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

[wordsmsdnua.livejournal.com]

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

[wordsmsdnua.livejournal.com]

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