Решение. Указав на одну из дверей, нужно спросить у любого из стражников:
“Подтвердит ли твой товарищ, что эта дверь ведет на свободу?” Если дверь,
на которую показал заключенный, ведет на свободу и стражник, к которому он
обратился, - лжец, то он ответит: “Нет”, так как его правдивый товарищ дал
бы на этот вопрос положительный ответ. Если дверь ведет к смерти, то
стражник-лжец ответит: “Да”. Рассуждая подобным образом, можно быть
уверенным, что правдивый стражник, видя, что указывают на дверь, ведущую
на свободу, даст отрицательный ответ, в противном же случае ответит: “Да”.
Все сказанное можно представить в форме дерева так:
Таким образом, кому бы из стражников ни задал вопрос заключенный, указав
на дверь, ведущую к свободе, он бы получил ответ: “Нет”. Если он получит
утвердительный ответ, то значит, на свободу ведет другая дверь.
Задача 3
Размещение гостей. Сколькими способами можно рассадить трех
гостей на трех стульях, поставленных рядом друг с другом? Показать все
возможные случаи в древовидной структуре.