завещание калибана (задачка)

[avva]

Изумительная логическая задачка, которая мне сегодня случайно попалась. Эту задачу придумал в 1930-х годах британский математик Макс Ньюман.

ЗАВЕЩАНИЕ КАЛИБАНА

Когда вскрыли завещание Калибана, в нем было написано следующее:

"Я завещаю моим друзьям A, B и C по десять книг из моей библиотеки. Пусть они выбирают книги в следующем порядке.

1) Видевшие меня в зеленом галстуке не могут выбрать раньше A.

2) Если B не был в Оксфорде в марте 1920 года, то тот, кто выбирает первый, никогда не одалживал мне зонтик.

3) Если B или C выбирает вторым, то C выбирает раньше того, кто первым влюбился."

К сожалению, оказалось, что A, B и C не помнят ни одного из нужных фактов; но тут семейный адвокат заметил, что если учесть, что головоломка составлена правильно - то есть в ней нет лишних утверждений - то можно выяснить, в каком порядке они должны выбирать.

В каком порядке должны выбирать A, B и C? Кто из них влюбился первым?

(какое-то время буду скрывать комментарии с правильными ответами)

Update: любопытно получается. Есть много правильных ответов, но судя по всему, они почти всегда получены путем неправильных аргументов. Многие просто дают ответ без подробностей, но там, где люди пишут аргументы, они чаще всего неверны. Я раскрыл несколько таких, чтобы подчеркнуть, что не работает. Одна из типичных ошибок: "лишнее условие" не означает, что если конечный ответ такой-то, то окажется, что это условие не дает о нем информации. "Лишнее условие" означает, что если бы его вообще не было, на основании остальных гипотетические A,B,C, у которых была хорошая память, пришли бы к правильному ответу и без него. Это очень разные вещи.

Пока что полностью аргументированное правильное решение дала только sthinks. Завтра днем открою все комментарии, напишу свой вариант решения в отдельной записи и еще немного о том, где я нашел эту задачу.

Update: все комментарии раскрыты. Подробное решение и обсуждение задачи в следующей записи.

Comments

[koshchey.livejournal.com]

ACB

[norian.livejournal.com]

a,c,b

[mathclimber.livejournal.com]

Ну A,C,B, вроде как.

[sleeping-death.livejournal.com]

ACB, В первый влюбился.

кстати, второе условие лишнее.

[sergushenkov.livejournal.com]

ИМХО, первые два пункта никак не влияют на порядок выбора. Из третьего пункта следует, что А последний. А вот кто первый-второй - не знаю

Апдейт от 16 января - перечитал на свежую голову, вроде дошло.
Как рассуждал Каллибан - в зелёном галстуке видел только один, поэтому после п.1 все поймут, что А либо первый, либо второй.
В п. 2 - т.к. В не был в Оксфорде, а А не одалживал зонтик, то А всё-таки первый.
П.3 пояснит, что С раньше, чем В (который первым влюбился)
По своему красивая, но не люблю такие задачи :)

[mudasobwa.livejournal.com]

2 ⇒ B ≠ 1
1 ⇒ A ≠ 3
3 ⇒ B|C = 2 ⇒ A≠ 2

А первый.
C второй.
B третий ⇐ влюбился.

[morfing.livejournal.com]

а с в

[angerona.livejournal.com]

Отличная задачка. Сейчас буду решать и записывать прямо здесь.

Значит варианты такие:

ABC
ACB

BAC
BCA

CAB
CBA

По условию 2, только один из вариантов из каждой пары может быть потенциальным решением (потому что условие 2 должно что-то менять в том, кто выбирает первый).

По условию 3, вариант ABC не работает (потому что должен быть кто-то после C)

По условию 1, вариант CBA не работает (потому что A не может быть последним)

Вычеркнем еще и BAC, а то иначе условие 3 будет лишним.

Так, пока что у нас осталось:

ACB

BCA

CAB

Гм, тогда и ACB надо вычеркнуть, а то условие 1 будет лишним.

BCA
CAB

Ой, CAB тоже не может быть, если считать, что условие 3 звучит как "Если B или C выбирает вторым, то C выбирает раньше того, кто первым влюбился, а если B или C не выбирает вторым, то C выбирает позже того, кто первым влюбился".

Значит остается только

BCA

Влюбился первым А.

Красиво (если я правильно решила :))) )

Redaktiruyu. Ya, konechno, genii. Snachala napisala "вариант CBA не работает (потому что A не может быть последним)", a potom reshila imenno s "A" poslednim. Na tom zhe shage nado bylo i BCA vycherknut'.

Ostalos' by
ACB
i
CAB

i vycherknut' CAB iz-za "Если B или C выбирает вторым, то C выбирает раньше того, кто первым влюбился, а если B или C не выбирает вторым, то C выбирает позже того, кто первым влюбился".

ostaetsya

ACB

[vakhitov.livejournal.com]

"...тот, кто выбирает первый, никогда не одалживал мне зонтик" - точно верный перевод? Там не должно быть наоборот - типа "первым выбирает тот, кто не одалживал мне зонтик"?

[avva.livejournal.com]

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

[http://users.livejournal.com/_hedning_/]

cba

[janez.livejournal.com]

B, C, A

A

[(Anonymous)]

Что такое лишние утверждения? Имеется в виду, что условие непротиворечиво?

[avva.livejournal.com]

Лишние утверждения - такие, что по замыслу составители задачи, A,B,C смогли бы установить порядок и без них.

[mme-n-b.livejournal.com]

A, C, B. Первым влюбился Б.

[irrelative.livejournal.com]

ACB

[definite.livejournal.com]

A, C, B. Влюбился B.

[nomen-nescio.livejournal.com]

Из условий следует:
1. А - не первый.
В этом случае из условия 3 следует, что С обязательно перед А.
2. В - не первый.
Значит, ответ - СВА. А влюбился первым.

[vakhitov.livejournal.com]

ACB, B - но в ответе не уверен, а если он правилен, то строго не обосную...

[sthinks.livejournal.com]

А не может быть последним (либо В, либо С, либо оба видели Калибана в зеленом галстуке, иначе было б лишним условием)

С не был первым влюбившимся, что оставляет варианты АСВ, ВАС, САВ

Если и В, и С видели Калибана в зеленом галстуке, тогда второе условие – лишнее. . Значит только один из них мог видеть Калибана в з.г. Если это В остаются варианты:
АСВ, САВ. Если это С: АСВ, ВАС

В не был в Оксфорде (иначе нет смысла во втором условии), значит кто-то одалживал зонтик.
Если это А, тогда А не может быть первым, т.е. должен быть вторым. И это делает третье условие лишним. Стало быть , А не одалживал зонтика.

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

Если В видел Калибана в зеленом галстуке, тогда С одалживал зонтик. И наоборот.

Порядок: А, С, В
В влюбился первым.

[nu57.livejournal.com]

Мне кажется, тут не совсем строго. То, что из-за галстука остаётся только два варианта (АСВ и САВ, если галстук видел В, и АСВ и ВАС, если галстук видел С), уже использует условие 3, которое отсекает варианты АВС и ВСА - иначе после применения условия 1 оставалось бы не по два, а по три варианта. Значит, дальнейшее рассуждение, что "это делает условие 3 лишним", не годится.

По-моему, правильнее так: http://avva.livejournal.com/2835081.html?thread=113299081#t113299081

[imenno.livejournal.com]

Сергей Бобров, "Волшебный двурог". Не упоминает Ньюмана, переносит действие в средневековую Испанию, меняет Оксфорд на Саламанку, а зонтик - на шпагу (прямо как Гелла). Но делает всё это гениально. Там и решение есть.

[avva.livejournal.com]

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

[giterleo.livejournal.com]

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

[xgrbml.livejournal.com]

Ага, теперь буду знать, откуда эта задача попала в эту (http://biblio.mccme.ru/node/1831/shop) книгу.

[avva.livejournal.com]

Увы, эта книга прошла мимо меня в детстве :(

[spamsink]

Из полезности 1) следует, что BCA и CBA невозможны.
Из 3) следует, что ABC невозможно.

Остаются ACB, BAC и CAB. Если считать, что 3) еще и "полезно", т.е. его антецедент истинен, то выходит ACB, но тогда нет пользы у 2).

Если же считать, что полезность 2) означает "B выбирает первым", то выходит BAC.

[avva.livejournal.com]

Ошибка начинается на словах "если считать". 3) уже оказалось полезным - ты с его помощью отверг ABC, и тебе совершенно не понадобилось при этом предполагать истинность антецендента.

[antontsau.livejournal.com]

Вариантов всего 6, проверяем все подряд

АВС

3 нет, так как В второй, а кто-то обязательно влюбился первым

ВСА и СВА

1 нет, так как предполагается, что кто-то все-таки видел в зеленом галстуке.

АСВ

возможно (если В влюбился первым, а А никогда не одалживал зонтик)

ВАС

возможно (если В не видел в галстуке и был в Оксфорде)

САВ

возможно (если С не одалживал зонтик и не видел в галстуке)

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

что-то не так с переводом или пониманием условия задачи.

[avva.livejournal.com]

Три варианта вы отбросили правильно, но надо продолжать думать.

ответ

[(Anonymous)]

как-то просто получается
Допустим, А выбирает вторым. Тогда 3-е условие не несёт информации. Значит, А выбирает либо первым, либо третьим.
>Видевшие меня в зеленом галстуке не могут выбрать раньше A.
Это условие должно нести информацию, значит, после А должен кто-то выбрать. Значит, А не третий. Значит, А - первый.

>Если B или C выбирает вторым, то C выбирает раньше того, кто первым влюбился."
Получается, С выбирает раньше кого-то
Значит, С выбирает раньше В.

Ответ: А С В

Re: ответ

[avva.livejournal.com]

На самом деле все действительно несколько сложнее. Я раскрыл ваш комментарий для примера, он довольно типичный: он приходит к правильному ответу, но неверным решением. Мне несколько человек написали что-то похожее, типа "второе условие не нужно", видимо, рассуждая так же, как вы (вы не пользуетесь вторым условием). Подозреваю, что и многие другие, кто просто дал правильный ответ без решения, на самом деле решили таким же неверным способом.

"Допустим, А выбирает вторым. Тогда 3-е условие не несёт информации. Значит, А выбирает либо первым, либо третьим."

Это неверно. Условие должно нести информацию для гипотетических A,B,C, которые помнят, что там было с галстуками итд., но не знают правильный порядок - они как раз пытаются его найти. 3-е условие гипотетически может нести для них информацию, которая поможет им заключить, что А выбирает вторым (например, если из других условий они решат, что C последний). В итоге в правильном ответе выходит как у вас, но это следует из взаимодействия всех трех условий.

[ikiussi.livejournal.com]

АСВ
Если B или C выбирает вторым, то C выбирает раньше того, кто первым влюбился
С выбирает раньше, следовательно, влюбиться первыми могли А В, но раньше - по условию, не раньше чем вторым, следовательно, он выбирает раньше В, автоматически А первым