Две задачи с интервью

Brat Levon · Post by **Brat Levon** » 25 Oct 2001 15:14

Еще в Москве, при собеседовании на аналитическую (не программистскую) позицию, мне попались такие вот классические задачи:

1. Два друга гуляли по улице, и один сказал: "Произведение возрастов моих трех сыновей равно 36, а сумма их возрастов равна номеру дома, мимо которого мы сейчас проходим". Друг ответил: "Я не могу определить, сколько твоим сыновьям лет". Тогда первый сказал: "Старший вчера получил двойку". "А, тогда я знаю", - сказал друг. Сколько лет детям?

2. Заключенный находится в камере, в которой два выхода, один из которых ведет на свободу, а другой - в логово тигра. Каждый вход охраняется стражником, один из которых всегда говорит правду, а другой всегда лжет (неизвестно, какой из них). Заключенному позволено задать только один вопрос одному из стражников, и потом выйти из камеры в один из выходов. Какой вопрос он должен задать, чтобы определить, какой выход ведет на свободу?

Melkor · Post by **Melkor** » 25 Oct 2001 15:35

<BLOCKQUOTE>quote:<HR>Originally posted by Brat Levon:
Еще в Москве, при собеседовании на аналитическую (не программистскую) позицию, мне попались такие вот классические задачи:

1. Два друга гуляли по улице, и один сказал: "Произведение возрастов моих трех сыновей равно 36, а сумма их возрастов равна номеру дома, мимо которого мы сейчас проходим". Друг ответил: "Я не могу определить, сколько твоим сыновьям лет". Тогда первый сказал: "Старший вчера получил двойку". "А, тогда я знаю", - сказал друг. Сколько лет детям?

Хм. Для очного интервью немножко громоздковата, по-моему. Варианты перебирать надо. Найти 2 (или более) варианта по три числа, так чтобы сумма была одинаковая, и только один из вариантов не имел двух старших сыновей одного возраста (возраст и старшинство считаем с погрешностью до года). Получается 2,2,9 (отбрасываем 1,6,6).

2. Заключенный находится в камере, в которой два выхода, один из которых ведет на свободу, а другой - в логово тигра. Каждый вход охраняется стражником, один из которых всегда говорит правду, а другой всегда лжет (неизвестно, какой из них). Заключенному позволено задать только один вопрос одному из стражников, и потом выйти из камеры в один из выходов. Какой вопрос он должен задать, чтобы определить, какой выход ведет на свободу?

Ну, это слишком известная. "Если я спрошу у другого стражника, куда ведет эта дверь, то что он ответит?", например, и проинвертировать ответ. Главное, чтобы две логические операции были, и результат не изменился, если их изменить на противоположные.
<HR></BLOCKQUOTE>

[ 25-10-2001: Message edited by: Melkor ]

Stonehange · Post by **Stonehange** » 25 Oct 2001 17:01

1) Возраст детей не может быть 9,2,2 => 9,4,1

А почему - загадка Вам

2) Ну, вопроос может быть : "Ты лжешь?"

[ 25-10-2001: Message edited by: Stonehange ]

Птичка · Post by **Птичка** » 25 Oct 2001 18:00

<BLOCKQUOTE>quote:<HR>Originally posted by Stonehange:
1) Возраст детей не может быть 9,2,2 => 9,4,1

А почему - загадка Вам
]<HR></BLOCKQUOTE>

Да нет уж, огласите решение Вашей загадки, пожалуйтса, а то ведь действительно 9, 2, 2 получается. Типа такой задачи есть про учителя, который на уроке задает задачу ученикам, что у мамы было три дочери и произведение их возрастов было равно 40, а сумма количеству учеников в классе, те быстро посчитались, но призадумались, на что учитель сказал "О, забыл сказать, что у младшенькой голубые глазки". Ему ученики ответили "Семен Семеныч" и назвали возраст дочерей.

А по поводу 9, 4, 1 - мужик ЗНАЛ номер дома, задача целочисленная, так почему же он не смог без знания того, что есть старший ответить на вопрос?????

Мыша · Post by **Мыша** » 25 Oct 2001 18:01

<BLOCKQUOTE>quote:<HR>Originally posted by Stonehange:
1) Возраст детей не может быть 9,2,2 => 9,4,1

А почему - загадка Вам

2) Ну, вопроос может быть : "Ты лжешь?"

[ 25-10-2001: Message edited by: Stonehange ]<HR></BLOCKQUOTE>

1)Почему не может? И, если 9,4,1, то есть, номер дома 14, почему он не мог сказать сразу?

Stonehange · Post by **Stonehange** » 25 Oct 2001 18:12

В америке нет дома с номером 13 [img:087b547769]images/smiles/icon_smile.gif[/img:087b547769]

А иначе зачем говориьт про номер дома?

Но вот я заметил, почему не может быть 12,3,1 ??

Пусть уж автор объявит ответ!!

Stonehange · Post by **Stonehange** » 25 Oct 2001 18:30

я не понял во второй загадке можно задать один вопрос на двомх или один каждому (т.е. 2)????

Dm.uk · Post by **Dm.uk** » 25 Oct 2001 19:10

переборы, переборы [img:c303e73350]images/smiles/icon_smile.gif[/img:c303e73350]
1 4 9
а самый прикольный - 1 2 18 - видимо старший-первокурсник банан на колоквиуме по вышке схлопотал [img:c303e73350]images/smiles/icon_biggrin.gif[/img:c303e73350]

Птичка · Post by **Птичка** » 25 Oct 2001 19:30

<BLOCKQUOTE>quote:<HR>Originally posted by Dm.ie:
переборы, переборы [img:c758fb4202]images/smiles/icon_smile.gif[/img:c758fb4202]
1 4 9
а самый прикольный - 1 2 18 - видимо старший-первокурсник банан на колоквиуме по вышке схлопотал [img:c758fb4202]images/smiles/icon_biggrin.gif[/img:c758fb4202]<HR></BLOCKQUOTE>

Самый интересный это 1, 1, 36 [img:c758fb4202]images/smiles/icon_smile.gif[/img:c758fb4202])))

Все варианты и сумма
1 1 36 38
1 2 18 21
1 3 12 16
1 4 9 14
1 6 6 13
2 2 9 13
2 3 6 11
3 3 4 10

итак, идут два мужика (про Америку нигде не сказано [img:c758fb4202]images/smiles/icon_smile.gif[/img:c758fb4202])) ), один говорит, что произведение равно 36 - вон все варианты вверху, а сумма - номер вон того дома, т.е. второй это видит и если бы, номер дома был бы не 13, то он сразу бы ответил на вопрос, а вот когда 13, он задумался, поскольку два варианта и какой выбрать - непонятно, а тут подсказка, что у старшенького голубые глазки [img:c758fb4202]images/smiles/icon_smile.gif[/img:c758fb4202]))))))))

RrM · Post by **RrM** » 25 Oct 2001 21:00

<BLOCKQUOTE>quote:<HR>Originally posted by Stonehange:


2) Ну, вопроос может быть : "Ты лжешь?"
<HR></BLOCKQUOTE>
Ну и какой вывод Вы сделаете из ответа "Да"?
[img:3670b8f78c]images/smiles/icon_biggrin.gif[/img:3670b8f78c]

Ptichka, браво, хорошо объяснили! Правда, некоторые придираются и заявляют, что одного из близнецов тоже можно назвать старшим... Но от этого можно отбрехаться, сформулировав поясняющую фразу как "у старшего вчера был день рождения"... Хотя и к этому можно придраться, если очень захотеть.
[img:3670b8f78c]images/smiles/icon_rolleyes.gif[/img:3670b8f78c]

Brat Levon · Post by **Brat Levon** » 25 Oct 2001 21:57

<BLOCKQUOTE>quote:<HR>Originally posted by Stonehange:
Пусть уж автор объявит ответ!!<HR></BLOCKQUOTE>

Да как-то и не знаю, что объявлять [img:7976c1a084]images/smiles/icon_smile.gif[/img:7976c1a084] Melkor уже все рассказал. В первой задаче, действительно, перебираешь все варианты (на это нужно совсем немного времени), находишь два расклада с одинаковой суммой (потому что второй участник не смог сразу дать ответ), берешь тот, где есть четко выраженный старший
сын [img:7976c1a084]images/smiles/icon_smile.gif[/img:7976c1a084]

Насчет дома №13 - я же говорил, что дело было в Москве [img:7976c1a084]images/smiles/icon_smile.gif[/img:7976c1a084]

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

WindJammer · Post by **WindJammer** » 26 Oct 2001 12:11

1) 9, 2, 2 /*Если я правильно оттрактовал условие*/

-ЭР- · Post by **-ЭР-** » 27 Oct 2001 00:27

<BLOCKQUOTE>quote:<HR>Originally posted by Brat Levon:

собственно, другого решения я не знаю <HR></BLOCKQUOTE>

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

Я обозначу А следующее утверждение "Эта дверь ведет на свободу", B - любое утверждение про, которое ни один из стражников не знает истинно оно или ложно. Например, "моя прабабушка любила есть яичницу по вторникам". Дальше я спрашиваю охранника: "истинно ли A | B?" (где | - логическое или). Так как оранник должен или врать или говорить правду, то А должно быть истинно. Иначе, охранник не может уверенно сказать истинно ли (A | B). Итак, если А - верно, то охранник отвечает (мне не важно что именно). Если же А - ложно, то охранник смущается, краснеет, но сказать ничего не может.

marinamo · Post by **marinamo** » 28 Oct 2001 00:36

<BLOCKQUOTE>quote:<HR>Originally posted by Brat Levon:
 Заключенный находится в камере, в которой два выхода, один из которых ведет на свободу, а другой - в логово тигра. Каждый вход охраняется стражником, один из которых всегда говорит правду, а другой всегда лжет (неизвестно, какой из них). Заключенному позволено задать только один вопрос одному из стражников, и потом выйти из камеры в один из выходов. Какой вопрос он должен задать, чтобы определить, какой выход ведет на свободу?<HR></BLOCKQUOTE>

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

clinger · Post by **clinger** » 29 Oct 2001 00:44

<BLOCKQUOTE>quote:<HR>Originally posted by -ЭР-:


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

Я обозначу А следующее утверждение "Эта дверь ведет на свободу", B - любое утверждение про, которое ни один из стражников не знает истинно оно или ложно. Например, "моя прабабушка любила есть яичницу по вторникам". Дальше я спрашиваю охранника: "истинно ли A | B?" (где | - логическое или). Так как оранник должен или врать или говорить правду, то А должно быть истинно. Иначе, охранник не может уверенно сказать истинно ли (A | B). Итак, если А - верно, то охранник отвечает (мне не важно что именно). Если же А - ложно, то охранник смущается, краснеет, но сказать ничего не может.<HR></BLOCKQUOTE>

Ни вопрос про дверь, ни вопрос про честность сами по себе ответа не дают. Их нужно совместить. Например, "выход на свободу охраняет честный стражник"?

Ответ ДА (оба стражника охраняющие выход на свободу ответят одинаково) -- можно выходить.
Ответ НЕТ (оба охраняющие выход ко льву ответят опять одинаково) -- идти в другую дверь.

.pl

Brat Levon · Post by **Brat Levon** » 29 Oct 2001 02:48

<BLOCKQUOTE>quote:<HR>Originally posted by clinger:


Ни вопрос про дверь, ни вопрос про честность сами по себе ответа не дают. Их нужно совместить. Например, "выход на свободу охраняет честный стражник"?

Ответ ДА (оба стражника охраняющие выход на свободу ответят одинаково) -- можно выходить.
.<HR></BLOCKQUOTE>

Куда выходить-то? Вопрос не включает в себя ни одну из дверей [img:d4cb032414]images/smiles/icon_smile.gif[/img:d4cb032414]

clinger · Post by **clinger** » 29 Oct 2001 19:24

<BLOCKQUOTE>quote:<HR>Originally posted by Brat Levon:


Куда выходить-то? Вопрос не включает в себя ни одну из дверей [img:1270a6820e]images/smiles/icon_smile.gif[/img:1270a6820e]<HR></BLOCKQUOTE>

Выходить в дверь за стражником который ответил ДА. Если НЕТ, то в другую дверь. Вопрос и не должен содержать в себе дверь [img:1270a6820e]images/smiles/icon_wink.gif[/img:1270a6820e]). Если стражник ответил ДА, он либо честный охраняющий дверь на выход, любо врун, но тоже охранябщий дверь на выход. С НЕТ аналогично.

.pl

Mortira · Post by **Mortira** » 31 Oct 2001 04:17

Народы!
Давайте смотреть на вещи проще, то есть Глобально.
Задача явно имеет два пути решения.
1. Двери изолированы, стражники не проинструктированы, и по этому не прикаких условиях Стражники не знают кто какую дверь охраняет ваще. Тогда задача решается просто, не найдется такого вопроса, из которого можно было бы на сто проц заключить что то для себя. Парни просто не в курсе. Как в префе: 50 на 50. Нужно вызвать главного стражника и у..ать ему хорошенько за внесение элемента неопределенности.

2. Если стражники все таки Знают. Тогда Мелькору - 5 баллов.
У Эр подход прикольный, но:
Наскольно я понял из рассуждений, если урод вякнул Да или Нет, то утверждение "Эта дверь ведет на свободу" должно быть правдой, иначе он мычит и мнётся, т.е. утверждение "Эта дверь ведет на свободу"-ложь. Т.е. если урод ответил Да или Нет, то идем в дверь на которую показывали при вопросе, если мнётся, то в противоположную.
И это должно быть верно при любой ситуации.
Рассмотрим тогда, что на воротах, ведущих на свободу стоит врун. При ответе на вопрос он вяло шевелит своими мозгами и думает: утверждение "Эта дверь ведет на свободу" - правда, но заключает по своей природе, что это ложь, тогда при ответе на весь вопрос он замычит, так как А or В - неопределено. Эр смело заключает, что надо идти в противоположную дверь, к тигрятам. Поскольку такое может быть, то решение Эра не однозначное.
Да и вообще, в каждом из решений по сути задается два вопроса, обединенные в один. Чтобы ответить на весь, то нужно предварительно для себя ответить на еще один.
Короче, необходимо уточнить, стражник, который врет, себе врет или себе всегда говорит правду.

Так что вывод простой, глобального решения не существую ввиду неточности формулировки понятия вопрос [img:d616bb3725]images/smiles/icon_biggrin.gif[/img:d616bb3725]

[ 30-10-2001: Message edited by: Mortira ]