Решение с помощью графов

Задача 1. На соревнованиях по легкой атлетике Андрей, Боря, Сережа и Володя заняли первые четыре места. Но когда девочки стали вспоминать, как эти места распределились между победителями, то мнения разошлись:

Даша: Андрей был первым, а Володя — вторым.

Галя: Андрей был вторым, а Борис — третьим.

Лена: Боря был четвертым, а Сережа — вторым.

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

Кто из мальчиков какое место занял?

Решение с помощью графов:

Вершины графа — имена мальчиков и занятые ими места. Ребра графа — высказывания девочек:

мнение Даши — жирные линии (ребра А-1 и В-2);

мнение Гали — пунктирные линии (ребра А-2 и Б-3);

мнение Лены — тонкие линии (ребра С-2 и Б-4).

Ася сказала, что каждая девочка сделала только одно правильное заявление. Значит, надо оставить только по одной линии каждого типа. Всего в графе должно остаться 3 линии разных типов.

Предположим, что истинно высказывание, обозначенное реб­ром В-2, тогда нам следует удалить из графа ребра А-1 (Даша права только в одном предположении), А-2 и С-2 (только кто-то один может занять второе место). В графе останется по одной линии каждого вида, а именно ребра В-2, Б-3 и Б-4. Но это невозможно, так как Борис не мог одновременно занять третье и четвертое места. Значит, предположение об истинности высказывания, обозначен­ного ребром В-2, было неверным.

Одно предположение Даши (ребро В-2) неверно, значит, верно ее другое предположение (ребро А-1). Следовательно, ребро А-2 следует удалить, а из этого следует, что высказывание, обозначен­ное ребром Б-3, должно быть истинным. Тогда ребро Б-4 надо удалить. Отсюда следует, что вторую тонкую линию (С-2) надо оставить.

В результате получим следующий граф, который и дает ответ задачи:

Ответ: первое место занял Андрей, второе — Сережа, третье — Боря, четвертое — Володя.

Задача 2. В начале лета школьники организовали сельскохозяйствен­ную бригаду и избрали бригадира, заместителя бригадира и звеньевых первого, второго и третьего звеньев. Их имена: Аня, Боря, Вася, Гриша и Дина. Звеньевая первого звена решила по­дружиться со звеньевой второго звена. Дина удивилась, узнав, что бригадир и звеньевая второго звена — брат и сестра. Гриша дружит с бригадиром и его заместителем. У Васи нет сестер. На­зовите должности каждого из ребят.

Решите с ис­пользованием графа.

Задания для самостоятельного выполнения

1. В кафе встретились три друга: скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что один из нас име­ет белые, один черные и один рыжие волосы, но ни у одного нет волос того цвета, на которые указывает его фамилия»,— заметил черноволосый. «Ты прав»,— сказал Белов. Какой цвет волос у художника?

2. Брауну, Джонсу и Смиту предъявлено обвинение в ограблении банка.
Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал, что преступники скрылись на синем “Бьюике”, Джонс сказал, что это был “Форд Мустанг” и ни в коем случае не синий. Стало известно, что, желая запутать следствие, каждый из них указал правильно либо только марку машины, либо только ее цвет.
Какого цвета, и какой марки был автомобиль?

3. Три девочки — Роза, Маргарита и Анюта представили на конкурс цвето­водов корзины выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов. Какие цветы вырастила каждая из девочек?

4. Виновник ночного дорожно-транспортного происшествия скрылся с ме­ста аварии. Первый из опрошенных свидетелей сказал работникам ГИБДД, что это были «Жигули», первая цифра номера машины — единица. Вто­рой свидетель сказал, что машина была марки «Москвич», а номер начи­нался с семерки. Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы. При дальнейшем расследовании вы­яснилось, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера. Какой марки была машина и с какой цифры начинался номер?

5. Пятеро одноклассников — Ирена, Тимур, Камилла, Эльдар и Залим ста­ли победителями олимпиад школьников по физике, математике, инфор­матике, литературе и географии. Известно, что: победитель олимпиады по информатике учит Ирену и Тимура работе на компьютере; Камилла и Эльдар тоже заинтересовались информатикой; Тимур всегда побаивался физики; Камилла, Тимур и победитель олимпиады по литературе занима­ются плаванием; Тимур и Камилла поздравили победителя олимпиады по математике; Ирена сожалеет о том, что у нее остается мало времени на литературу. Победителем какой олимпиады стал каждый из этих ребят?

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

7. На очередном этапе автогонок «Формула-1» первые четыре места заня­ли Шумахер, Алези, Хилл и Кулхардт. Опоздавший к месту награждения телерепортер успел заснять пилотов, занявших второе и третье места, которые поливали друг друга шампанским. В это время Шумахер с четвертым гонщиком пожимали друг другу руки. Далее в кадр попал мок­рый Хилл, поздравляющий пилота, занявшего второе место. Напоследок оператор снял сцену, в которой Шумахер и Кулхардт пытались втащить на пьедестал почета пилота, занявшего четвертое место. Просматривая от­снятый материал, режиссер спортивного выпуска быстро разобрался, кто из пилотов какое место занял. Он знал, что в соответствии с цере­монией награждения победителей гонок пилоты, занявшие первые три места, поливают друг друга шампанским из огромных бутылок знамени­той фирмы — спонсора соревнований. Какое же место занял каждый пилот?

8. При составлении расписания на пятницу были высказаны пожелания, чтобы информатика была первым или вторым уроком, физика — первым или третьим, история — вторым или третьим. Можно ли удовлетворить одновременно все высказанные пожелания?

9. Обсуждая конструкцию нового трехмоторного самолета, трое конструкто­ров поочередно высказали следующие предположения:

1) при отказе второго двигателя надо приземляться, а при отказе третьего можно продолжать полет;

2) при отказе первого двигателя лететь можно или при отказе третьего двигателя лететь нельзя;

3) при отказе третьего двигателя лететь можно, но при отказе хотя бы одного из остальных надо садиться.

Летные испытания подтвердили правоту каждого из конструкторов.

Определите, при отказе какого из двигателей нельзя продолжать полет.

10. В соревнованиях по плаванию участвовали Андрей, Виктор, Саша и Дима. Их друзья высказали предположения о возможных победителях:

1) первым будет Саша, Виктор будет вторым;

2) вторым будет Саша, Дима будет третьим;

3) Андрей будет вторым, Дима будет четвертым.

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

11. Для длительной международной экспедиции на околоземной космической станции надо из восьми претендентов отобрать шесть специалистов: по аэронавтике, космонавигации, биомеханике, энергетике, медицине и аст­рофизике. Условия полета не позволяют совмещать работы по разным специальностям, хотя некоторые претенденты владеют двумя специально­стями. Обязанности аэронавта могут выполнять Геррети и Нам; космона-вигатора — Кларк и Фриш; биомеханика — Фриш и Нам; энергетика -Депардье и Леонов; врача - Депардье и Хорхес; астрофизика - Волков и Леонов. По особенностям психологической совместимости врачи рекомендуют совместные полеты Фриша и Кларка, а также Леонова с Хорхесом и Депардье. Напротив, нежелательно, чтобы Депардье оказал­ся в одной экспедиции с Намом, а Волков — с Кларком. Кого следует включить в состав экспедиции?

12. В соревнованиях по гимнастике участвуют Алла, Валя, Сима и Даша. Болельщики высказали предположения о возмож­ных победителях:

1) Сима будет первой, Валя — второй;

2) Сима будет второй, Даша — третьей;

3) Алла будет второй, Даша — четвертой.

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

Какое место на соревнованиях заняла каждая из девушек, ес­ли все они оказались на разных местах?

13. Виктор, Роман, Леонид и Сергей заняли на математиче­ской олимпиаде четыре первых места. Когда их спросили о рас­пределении мест, они дали три таких ответа:

1) Сергей — первый, Роман — второй;

2) Сергей — второй, Виктор — третий;

3) Леонид — второй, Виктор — четвертый.

Известно, что в каждом ответе только одно утверждение ис­тинно.

Как распределились места?

14. Алеша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:

Алеша: «Это сосуд греческий и изготовлен в V веке».

Боря: «Это сосуд финикийский и изготовлен в III веке».

Гриша: «Это сосуд не греческий и изготовлен в IV веке».

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

Где и в каком веке изготовлен сосуд?

15. Виновник ночного дорожно-транспортного происшест­вия скрылся с места аварии. Первый из опрошенных свидетелей сказал работникам ГАИ, что это были «Жигули», первая цифра номера машины — единица. Второй свидетель сказал, что маши­на была марки «Москвич», а номер начинался с семерки. Третий свидетель заявил, что машина была иностранная, номер начи­нался не с единицы. При дальнейшем расследовании выясни­лось, что каждый из свидетелей правильно указал либо марку машины, либо только первую цифру номера.

Какой марки машина и с какой цифры начинался номер?

16. В нарушении правил обмена валюты подозреваются че­тыре работника банка — Антипов (А), Борисов (В), Цветков (С) и Дмитриев (D). Известно, что:

1) если А нарушил, то и В нарушил правила обмена валюты;

2) если В нарушил, то и С нарушил или А не нарушил;

3) если D не нарушил, то А нарушил, а Сне нарушил;

4) если D нарушил, то и А нарушил.

Кто из подозреваемых нарушил правила обмена валюты?

17. Перед сдачей вступительных экзаменов в институт Миша предполагал, что:

1) если он сдаст математику, то информатику он сдаст толь­ко при условии, что не завалит диктант;

2) не может быть, чтобы он завалил и диктант, и математику;

3) достаточное условие завала по информатике — это двойка по диктанту.

После сдачи экзаменов оказалось, что из трех высказанных предположений только одно было ложным. Как Миша сдал эк­замены?

18. В санатории на берегу моря отдыхают отец О, мать М, сын S две дочери D I и D 2. До завтрака члены семьи часто ку­паются в море, причем известно, что если отец утром отправля­ется купаться, то с ним обязательно идут мать и сын; если сын идет купаться, то его сестра D 1 отправляется вместе с ним; вто­рая дочь D 2 купается тогда и только тогда, когда купается мать; каждое утро купается по крайней мере один из родителей.

Если в воскресенье утром купалась в море лишь одна из до­черей, то кто из членов семьи в это утро ходил на море?

19. После зимних каникул классный руководитель спросил, кто из ребят ходил в театр, кино или цирк. Оказалось, что из 36 учеников класса двое не были ни в кино, ни в театре, ни в цирке. В кино побывало 25 человек, в театре - 11, в цирке - 17; и в кино, и в театре - 6; и в кино, и в цирке - 10; и в театре, и в цирке - 4.

Сколько человек побывало и в кино, и в театре, и в цирке?

20. В начале лета школьники организовали сельскохозяйствен­ную бригаду и избрали бригадира, заместителя бригадира и звеньевых первого, второго и третьего звеньев. Их имена: Аня, Боря, Вася, Гриша и Дина. Звеньевая первого звена решила по­дружиться со звеньевой второго звена. Дина удивилась, узнав, что бригадир и звеньевая второго звена — брат и сестра. Гриша дружит с бригадиром и его заместителем. У Васи нет сестер. На­зовите должности каждого из ребят.

21. В одном доме живут Воронов, Павлов, Журавлев, Синицын. Один из них — математик, другой — художник, третий — писа­тель, а четвертый — баянист. Известно, что:

1) ни Воронов, ни Журавлев не умеют играть на баяне;

2) Журавлев не знаком с Вороновым;

3) писатель и художник в воскресенье уезжают на дачу к Павлову;

4) писатель собирается написать очерк о Синицыне и Воронове.

Требуется определить, кто есть кто.

22. Однажды в туристическом лагере оказались вместе пять ребят. Их имена: Леонид, Сергей, Николай, Олег и Петр. Их фамилии: Антонов, Борисов, Васильев, Дроздов и Иванов. Кроме того, из­вестно, что Петр знаком со всеми, кроме одного. Борисов знаком только с двумя. Леонид знает только одного из всех. Дроздов и Сергей не знакомы. Николай и Иванов хорошо знают друг друга. Сергей, Николай и Олег давно знакомы между собой. Антонов знаком только с Петром.

Попробуйте по этим сведениям узнать имена и фамилии всех мальчиков.

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

А: Я — Мердок. В: А сказал правду. С: Я — Мердок.

Кто из них рыцарь, кто лжец и кто шпион?

Экзаменационные и олимпиадные логические задачи (ДВГУ, 1995 г.)

1. Четыре юных филателиста Митя, Толя, Саша и Петя купили почтовые марки. Каждый из них покупал марки только одной страны, причем двое из них купили российские марки, один болгарские, а один – словацкие. Известно, что Митя и Толя купили марки двух разных стран. Марки разных стран купили Митя с Сашей, Петя с Сашей, Петя с Митей и Толя с Сашей. Кроме того известно, что Митя купил не болгарские марки. Определить, марки каких стран купил каждый из них.

2. Пять красавиц ехали в Голливуд, каждая на своей автомашине.

Англичанка ехала в синей машине.

Итальянка была с собакой.

Египтянка была блондинкой.

Испанка жевала Wrigley`s.

Немка ехала первой. В зеленой машине сосали конфеты.

В голубой машине ехала шатенка.

За желтой машиной ехала зеленая.

Вторая машина была белая.

В третьей машине глотали таблетки.

Брюнетка была с котенком.

Во рту у рыжей торчала сигарета.

В соседней с голубоволосой машине ехала лиса.

Обезьяна ехала в машине соседней с шатенкой.

С кем ехал попугай и кто пил кока-колу?

Приложение 1

Задания для самостоятельных работ

(Задачи расположены по вариантам с возрастающим уровнем сложности)

Дата добавления: 2014-12-27