Задачи о рыцарях и лжецах

Задачи о рыцарях и лжецах — разновидность олимпиадных математических задач, в которых фигурируют персонажи:

• Лжец — человек (или иное существо), всегда говорящий ложь.

и его антагонист

• Рыцарь, всегда говорящий правду.

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

Существуют задачи с тремя типами персонажей — рыцари, лжецы и нормальные люди (вариант — шпионы). Последние могут как лгать, так и говорить правду (например: самая сложная логическая задача).

Также существуют целые классы задач того же типа, но с другими персонажами — задачи о пациентах и врачах, задачи об упырях, собранные в частности в книгах математика Рэймонда М. Смаллиана.

Примеры

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

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

Двое людей A и B, о которых известно, что каждый из них либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения:
A: B — рыцарь.
B: A — не рыцарь.
Доказать, что по крайней мере один из них говорит правду, но это не рыцарь.

На острове, население которого составляют только рыцари, всегда говорящие правду, и лжецы, которые всегда лгут, находится НИИ. Каждый из его сотрудников однажды сделал два заявления:
а) В институте нет и десяти человек, которые работают больше меня.
б) По крайней мере сто человек в институте получают зарплату большую, чем моя.
Известно, что нагрузка у всех работников разная, как и зарплата. Сколько человек работает в НИИ?

Один из вариантов задачи о рыцарях и лжецах упоминается в испанском триллере «Западня Ферма».

Примечания

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

См. также

Ссылки

Рэймонд М. Смаллиан — «Как же называется эта книга?»

А. ОСТРОВ РЫЦАРЕЙ И ЛЖЕЦОВ

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

26.

Итак, начнем с давно известной задачи. Трое жителей острова (А, В и С) разговаривали между собой в саду. Проходивший мимо незнакомец спросил у А: «Вы рыцарь или лжец?» Тот ответил, но так неразборчиво, что незнакомец не смог ничего понять. Тогда незнакомец спросил у В: «Что сказал А?». «А сказал, что Oн лжец»,-ответил В. «Не верьте В! Он лжет! — вмешался в разговор островитянин С.

Кто из островитян В и С рыцарь и кто лжец?

27.

Когда я впервые встретил предыдущую задачу, мне сразу же бросилось в глаза, что С по существу бездействует, исполняя роль своего рода «бесплатного приложения». Действительно, когда В высказался, то ложность его утверждения можно было бы установить и без вмешательства С. Следующий вариант задачи позволяет избавиться от «излишеств» в условиях.

Предположим, что незнакомец задал А другой вопрос: «Сколько рыцарей среди вас?» И на этот вопрос А ответил неразборчиво. Поэтому незнакомцу пришлось спросить у В: «Что сказал А?». В ответил: «А сказал, что среди нас один рыцарь». И тогда С закричал: «Не верьте В! Он лжет!»

Кто из двух персонажей В и С рыцарь и кто лжец

28.

В этой задаче два персонажа: А и В. Каждый из них либо рыцарь, либо лжец. А высказывает следующее утверждение: «По крайней мере один из нас лжец».

Кто из двух персонажей А и В рыцарь и кто лжец?

29.

Предположим, что А говорит: «Или я лжец, или В рыцарь».

Кто из двух персонажей А и В рыцарь и кто лжец?

30.

Предположим, что А говорит: «Или я лжец, или два плюс два — пять». К какому заключению можно прийти на основании этого утверждения?

31.

Перед нами снова три островитянина А, В и С, о каждом из которых известно, что он либо рыцарь, либо лжец. Двое из них (А и В) высказывают следующие утверждения:

А: Мы все лжецы.
В: Один из нас рыцарь.

Кто из трех островитян А, В и С рыцарь и кто лжец?

32.

Предположим, что А и В высказывают следующие утверждения:

А: Мы все лжецы.
В: Ровно один из нас лжец.

Можно ли определить, кто такой В: рыцарь или лжец?

Можно ли определить, кто такой С?

33.

Предположим, что А высказывает утверждение: «Я лжец, а В не лжец».

Кто из островитян А и В рыцарь и кто лжец?

34.

Перед нами в очередной раз три островитянина А, В и С, о каждом из которых известно, что он либо рыцарь, либо лжец. Условимся называть двух островитян однотипными, если они оба рыцари или оба лжецы. Пусть А и В высказывают следующие утверждения:

А: В — лжец.
В: А и С однотипны.

Кто такой С: рыцарь или лжец?

35.

Перед нами снова трое островитян А, В и С. А высказывает утверждение: «В и С однотипны». Кто-то спрашивает у С: «А и В однотипны?»

Что ответит островитянин С?

36. Небольшое происшествие.

Эта говоломка необычна. Кроме того, в основу ее положено подлинное происшествие. Однажды, когда я гостил на острове рыцарей и лжецов, мне встретились два местных жителя. Я спросил у одного из них: «Кто-нибудь из вас рыцарь?» Мой вопрос не остался без ответа, и я узнал то, что хотел узнать.

Кем был островитянин, к которому я обратился с вопросом: рыцарем или лжецом? Кем был другой островитянин? Смею заверить вас, что я предоставил в ваше распоряжение информацию, достаточную для решения задачи.

37.

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

Должны ли оба ответа быть одинаковыми?

38. Эдуард или Эдвин?

На этот раз, прогуливаясь по острову, вы случайно на бредете на островитянина, безнадежно увязшего у берега пруда, но сколько ни бьетесь, вам так и не удается извлечь его из тины. Вы помните, что его зовут то ли Эдвин, то ли Эдуард, но не можете вспомнить, как именно. Поэтому вы спрашиваете у островитянина, как его зовут, и слышите в ответ: «Эдуард».

Как зовут островитянина?

Головоломки про рыцарей и лжецов

На неведомом острове живут рыцари и лжецы. Рыцари всегда говорят правду, лжецы всегда лгут. На этом условии построены все головоломки, которые вы здесь найдёте. Свои ответы выкладывайте в комментариях.

Про рыцарей и лжецов I

Трое жителей острова (А, Б и В) ссорились на рынке. Мимо проходил иноземец и спросил жителя А: «Ты рыцарь или лжец?» Иностранец не понял, что ответил А, поэтому задал другой вполне логичный вопрос жителю Б: «Что сказал А?» Б ответил: «А сказал, что он лжец» Но тут вмешался житель В: «Не верьте Б, он лжёт!»

Кто такие Б и В?

Про рыцарей и лжецов II

Иноземец встречает двух местных жителей. Один из них говорит: «Я лжец или мой друг рыцарь». Кто они такие?

Про рыцарей и лжецов III

По пути к бару иноземец встретил трёх местных жителей. Один из них сказал: «Все мы лжецы». Второй добавил: «Только один из нас – честный человек». Кто они все?

Про рыцарей и лжецов IV

В баре иноземец встретил забавного парня, который сказал: «Если моя жена – рыцарь, то я – лжец».

Кто же эта пара?

Про рыцарей и лжецов V

Когда иноземец решил расплатиться и покинуть бар, бармен огласил ему счёт. Стоимость оказалась достаточно высокой, тогда иноземец спросил бармена, говорит ли тот правду. Но бармен ответил слишком тихо, поэтому иноземцу пришлось переспрашивать у сидящего рядом посетителя. Посетитель ответил: «Бармен сказал «да», но он большой лжец».

Кем является каждый из них?

Про рыцарей и лжецов VI

Выходя из бара, иноземец услышал о зарытых на острове сокровищах. Он захотел убедиться, что понял всё правильно, поэтому спросил другого человека, который ответил: «На этом острове есть сокровища, только если я честный человек». Есть ли смысл искать клад на этом острове?

Про рыцарей и лжецов VII

В раздумьях о сокровищах, иноземец позабыл, какой был день недели. Он спросил об этом четырёх местных жителей и получил такие ответы: А: Вчера была среда. Б: Завтра будет воскресенье. В: Сегодня – пятница. Г: Позавчера был четверг. Поскольку всё, что вам надо знать – это сколько людей солгало, этого мы не скажем. Какой же был день недели?

источник

Если вам понравился пост, пожалуйста, поделитесь им со своими друзьями!

Мой мир

Facebook

Вконтакте

Twitter

Одноклассники

Презентация «Задачи о рыцарях и лжецах»

Презентация на тему: Задачи о рыцарях и лжецах

Скачать эту презентацию

Скачать эту презентацию

№ слайда 1 Описание слайда:

АОУ лицей № 11 «Физтех» Учитель информатики Зарецкая Марина Витальевна Презентация к урокам информатики в 5-6 классах по теме: «Задачи о рыцарях и лжецах»

№ слайда 2 Описание слайда:

Задачи о рыцарях и лжецах — разновидность задач, в которых фигурируют персонажи: Задачи о рыцарях и лжецах — разновидность задач, в которых фигурируют персонажи: Лжец — человек (или иное существо), всегда говорящий ложь. Рыцарь, всегда говорящий правду. Решение подобных задач обычно сводится к перебору вариантов с исключением тех, которые приводят к противоречию.

№ слайда 3 Описание слайда:

На острове живут рыцари и лжецы. Путешественник, встретивший одного из местных жителей, спросил его, кем он является. На острове живут рыцари и лжецы. Путешественник, встретивший одного из местных жителей, спросил его, кем он является. Что ответит житель? Я — рыцарь !!!

№ слайда 4 Описание слайда:

Интересно отметить, что и рыцари и лжецы могут произносить фразу «Я — рыцарь». В устах рыцаря это истинное высказывания, лжеца — ложное. А высказывание «Я — лжец» не может принадлежать ни рыцарю, ни лжецу (т.н. парадокс лжеца).

№ слайда 5 Описание слайда:

Задача 2 На остров рыцарей и лжецов приехал путешественник и нанял себе проводника. Однажды, увидев вдали туземца, путешественник сказал проводнику: "Пойди и спроси у того человека: рыцарь он или лжец". Вскоре проводник вернулся и сказал: "Этот человек сказал, что он лжец". Кем был проводник, рыцарем или лжецом? Лжецом

№ слайда 6 Описание слайда:

Задача 3 Путешественник вышел на дорогу, соединяющую город лжецов и город рыцарей. Он хочет узнать, в какой стороне находится каждый из городов. Какой вопрос он должен задать прохожему (не зная, рыцарь он или лжец), чтобы определить это? Ты живешь в этом городе!!!

№ слайда 7 Описание слайда:

Задача 4 Предположим, что островитянин А высказывает утверждение: «Я лжец, а В не лжец». Кто из островитян А и В рыцарь и кто лжец? А и В — лжецы!

№ слайда 8 Описание слайда:

Задача Путник встретил троих островитян и спросил каждого: «Сколько рыцарей среди твоих спутников?» Первый ответил «Ни одного», второй ответил: «Один». Что сказал третий? один

№ слайда 9 Описание слайда:

задача 6 Путешественник, попавший на остров рыцарей и лжецов, встретил четырех людей и задал им вопрос: «Кто вы?». Он получил такие ответы:1-ый: «Все мы лжецы»2-ой: «Среди нас 1 лжец»3-ий: «Среди нас 2 лжеца»4-ый: «Я ни разу не соврал и сейчас не вру » Путешественник быстро сообразил, кем является четвертый житель. Как он это сделал? 4-ый — рыцарь

№ слайда 10 Описание слайда:

Задача 7 Однажды, когда я гостил на острове рыцарей и лжецов, мне встретились два местных жителя. Я спросил у одного из них: "Кто-нибудь из вас рыцарь?" Мой вопрос не остался без ответа, и я узнал то, что хотел узнать. Кем был островитянин, к которому я обратился с вопросом: рыцарем или лжецом? Кем был другой островитянин? Смею заверить вас, что я предоставил в ваше распоряжение информацию, достаточную для решения задачи.

№ слайда 11 Описание слайда:

Задача 8 Один из попугаев: A, B, C всегда врет, другой всегда говорит правду, а третий хитрец – иногда врет, а иногда говорит правду. На вопрос: «Кто вы?» они ответили: А: «Я лжец», В сказал: «Я хитрец» и С: «Я абсолютно честный попугай». Определите, кто есть кто.

№ слайда 12 Описание слайда:

Задача 9 Племя людоедов поймало Робинзона Крузо. Вождь сказал: «Мы рады бы отпустить тебя, но по нашему закону ты сначала должен произнести какое-нибудь утверждение. Если оно окажется истинным, мы съедим тебя. Если оно окажется ложным, тебя съест наш лев». Помогите Робинзону!

№ слайда 13 Описание слайда:

Задача 10 Малыш сделал надписи: на красной – «Здесь варенья нет»; на синей – «Варенье — здесь»; на зеленой – «Варенье в синей коробке». Только одна из надписей правдива. В какой коробке Малыш спрятал варенье? в зелёной

№ слайда 14 Описание слайда:

Задача 12 Трое жителей острова: (А, В и С) разговаривали между собой в саду. Проходивший мимо незнакомец спросил у А: "Вы рыцарь или лжец?" Тот ответил, но так неразборчиво, что незнакомец не смог ничего понять. Тогда незнакомец спросил у В: "Что сказал A?" "A сказал, что он лжец", — ответил В. "Не верьте В! Он лжет!" — вмешался в разговор островитянин С. Кто из островитян В и С рыцарь и кто лжец? В – лжец, С — рыцарь

№ слайда 15 Описание слайда:

Задача 13 На острове живут 100 человек, причём некоторые из них всегда лгут, а остальные всегда говорят только правду. У каждого жителя острова есть одно любимое время года. Каждому островитянину было задано 4 вопроса: Любите ли Вы зиму? Любите ли Вы осень? Любите ли Вы лето? Любите ли Вы весну? На первый и второй вопрос утвердительно ответили по 25 человек, на третий — 45, на четвёртый — 55. Сколько лжецов на острове?

№ слайда 16 Описание слайда:

Задача 13 — решение Если бы все жители острова говорили правду, было бы дано 100 утвердительных ответов. Каждый лжец даёт три утвердительных ответа вместо одного, то есть он увеличивает общее число утвердительных ответов на два. Так как всего было дано 25 + 25 + 45 + 55=150 утвердительных ответов, то количество лжецов равно 50:2=25.

№ слайда 17 Описание слайда:

Задача 14 Однажды на лестнице была найдена странная тетрадь. В ней было записано сто утверждений: «В этой тетради ровно одно неверное утверждение » «В этой тетради ровно два неверных утверждения» «В этой тетради ровно три неверных утверждения» … «В этой тетради ровно сто неверных утверждений» Есть ли среди этих утверждений верные, и если да, то какие? В этой тетради 99 неверных утверждений

№ слайда 18 Описание слайда:

Задача 15 В компании из 12 аборигенов каждый заявил всем остальным: «Вы все лжецы!». В компании из 12 аборигенов каждый заявил всем остальным: «Вы все лжецы!». Сколько лжецов в этой компании? одиннадцат

№ слайда 19 Описание слайда:

Задача 16В стране три города — А, Б, В. Жители города А всегда говорят правду, а города Б — лгут. В городе В лгут и говорят правду в строгой очередности. Дежурному на каланче, увидевшему пожар, позвонили. Состоялся такой разговор: «У нас пожар!» — «Где горит?» — «В городе В!». Куда ехать пожарным? В город А

№ слайда 20 Описание слайда:

Задача 17В Стране Чудес проводилось следствие по делу об украденном бульоне. На суде Мартовский Заяц заявил, что бульон украл Болванщик. Соня и Болванщик тоже дали показания, но что они сказали, никто не запомнил, а запись смыло алисиными слезами. В ходе судебного заседания выяснилось, что бульон украл лишь один из подсудимых и что только он дал правдивые показания. Так кто украл бульон?

№ слайда 21 Описание слайда:

Задача 18 Возле огрызка Священного Яблока были задержаны 4 аборигена. Агр заявил, что Яблоко съел Бгр, который, в свою очередь, утверждал, что виноват Вгр. Вгр уверял, что Бгр лжёт, а Ггр твердил, что это сделал не он. Выяснилось, что только один из них был рыцарем. Кто рыцарь, и кто обглодал священный фрукт?

№ слайда 22 Описание слайда:

Задача 18 — решение Бгр и Вгр друг другу противоречат. Значит, один из них рыцарь. Так как рыцарь всего один, то Агр и Ггр лжецы, то есть они врут. Значит Ггр обглодал священное яблоко. Теперь разберемся кто рыцарь. Так как на виновника мог указать только рыцарь, а на Ггра никто не указал, то рыцарь никого не обвинял, значит рыцарь Вгр.

№ слайда 23 Описание слайда:

Источники материалов Малый мехмат МГУ http://mmmf.msu.ru/archive/20052006/z5/7.html, http://mmmf.msu.ru/archive/20082009/z7/8.html, http://mmmf.msu.ru/archive/19931994/zan12.html Математический кружок www.mccme.ru/circles/mccme/2009/7klass/03.doc Задачи о рыцарях и лжецах — Википедия ru.wikipedia.org/wiki/Задачи_о_рыцарях_и_лжецах Office Microsoft. Шаблон на конкурс. Книга http://office.microsoft.com/ru-ru/templates/TC030009628.aspx Иллюстрация «Рыцари» http://gorod.crimea.edu/librari/ist_cost/risari/004.jpg

№ слайда 24 Описание слайда:

Автор: Зарецкая Марина Витальевна Место работы: АОУ лицей № 11 «Физтех» Должность: учитель информатики