Рассмотрим граф, вершины которого обозначают дедов, чьи внуки учатся в этой школе, а ребра – внуков (всего 20 ребер). Пусть а А и В- деды одного из внуков. Выделим также остальных внуков этих дедов (кратные ребра, соединяющие вершины А и В). По условию любые два ребра имеют общий конец, следовательно, каждое из остальных ребер выходит либо из вершины А, либо из В. Если все они выходят из одной вершины, то утверждение задачи очевидно, т.к. у деда 20 внуков. Иначе существует третья вершина С, где сходятся эти ребра. Значит, что всего имеется ровно три деда. Следовательно, найдутся две вершины из этих трех, соединенные ребром кратности не более шести (в противном случае граф должен иметь по крайней мере 3*7=21 ребро). Тогда у оставшегося деда по крайней мере 20-6=14 внуков.

 В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

Если в государстве100 городов (вершин графа), то сумма степеней всех вершин равна 4*100 = 400, и равна удвоенному произведению числа ребер – 2r. Отсюда число ребер (дорог): 400/2=200.

Ответ: 200 дорог.

Нет, не может. В противном случае получился бы граф соседства баронств с нечетным количеством нечетных вершин.

Ответ: не может.

               Всего есть три пути, которые могут оказаться кратчайшими:

1. A –  – D;
2. A –  – B –  – D;
3. A –  – B –  – C –  – D;

Из того, что на маршруте A –  – B –  – D находятся 22 колдобины, следует, что на тропинке B –  – D никак не больше 22 колдобин, стало быть из 45 колобин маршрута A –  – D –  – B хотя бы 23 на тропинке A –  – D, то есть второй путь выгоднее первого.

Аналогично, поскольку на маршруте A –  – B –  – C 10 колдобин, то на тропинке AB не более 10 колдобин. Значит из 22 колдобин пути ABD не менее 12 приходится на тропинку B –  – D. Но на пути B –  – C –  – D всего 10 колдобин, поэтому третий путь выгоднее второго, а, значит, и первого.

Ответ: Им надо идти по маршруту A–B–C–D.

 Можно ли фигуры на рисунке начертить одним росчерком пера?

Ответ: Все вершины данного графа - четные. Значит, начертить одним росчерком пера эту фигуру можно, причем обход можно начинать с любой вершины.

Ответ: граф содержит две нечетные вершины.  Значит, начертить одним росчерком пера эту фигуру можно, причем обход необходимо начинать с одной из нечетных  вершин, а закончить – в другой нечетной вершине.(Нечетные вершины у основания молотка).

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

Всего возможно три варианта:  соединить A с B и C с D; соединить A с C и B с D; соединить A с D и B с C. Тогда с каждого участка суши выходит четное количество мостов, а как раз в этом случае в связном графе существует эйлеров цикл, т.е. описанный обход возможен Например, в первом случае возможен такой обход:

A-B-A-B-D-B-C-D-C-A.

Ответ: три варианта:                 

соединить A с B и C с D; соединить A с C и B с D; соединить A с D и B с C.

В составе экспедиции должно быть 6 специалистов: биолог, врач, синоптик, гидролог, механик и радист. Имеется 8 кандидатов, из которых и нужно выбрать участников экспедиции; условные имена претендентов: A, B, C, D, E, F, G и  H. Обязанности биолога могут исполнять E и G, врача A и D, синоптика F и G, гидролога B и F, радиста С и D, механика C и H. Предусмотрено, что в экспедиции каждый из них будет выполнять только одну обязанность. Кого и в какой должности следует включить в состав экспедицию, если F не может ехать без B, D без  H и C, C не может ехать вместе с G, A вместе с B?  

             Используя представление данных в виде дерева, решите следующую логическую задачу:

           Всего женщин 42-(9+18)=15. Мужчин-ростовчан-артистов 18-13=5. Не было артистами 16 мужчин, значит, не были артистами 16-13=3 мужчины-москвича. Тогда артистами было 9-3=6 мужчин-москвичей. 6 москвичей не было артистами, значит,  6-3 =3 женщины–москвички не были артистами. 11 женщин не являлись артистками, значит, 11-3=8 женщин - ростовчан не были артистками. Артистов-женщин-ростовчан не было. Всего женщин-ростовчан 8.

Итак, ростовчан 8+18=26, москвичей- 42-26= 16, женщин-москвичей 16-9=7, артистки-женщины-москвички 7-3=4.

Ответ: в самолете количество москвичей 16, ростовчан – 26, женщин-артистов-москвичей 4, мужчин-артистов-москвичей 6 и не артистов - женщин-москвичей 3, мужчин- не артистов-москвичей 3;

женщин-артистов-ростовчан 0, мужчин-артистов - ростовчан 5, не артистов- женщин- ростовчан 8, мужчин - не артистов- ростовчан 13.

 Путешествие Пятачка

Пятачок решил навестить своих друзей – Винни-Пуха ,Кролика и Иа-Иа. Ему надо побывать у каждого из своих друзей и вернуться домой. Помогите Пятачку выбрать кратчайший путь.

Расположение домиков:

       Построим граф, используя условие задачи, и расставим на нем расстояния.

           Тройка нападения             

Известно, что при составлении троек нападения в команде учитывается сыгранность и психологическая совместимость игроков. В команде по хоккею в основном три тройки нападения. Надо составить тройки нападения из кандидатов, состоящие из центрального нападающего, левого и правого крайнего. На место центрального нападающего имеются кандидаты: Ц1, Ц2, ЦЗ, на место левого крайнего кандидаты: Л1, Л2, ЛЗ, правого крайнего — П1, П2, ПЗ. Проверка показала, что Ц1 хорошо совместим с Л1, Л2, П2; Ц2 — с Л1, П1, ПЗ; ЦЗ — с ЛЗ, П2, ПЗ.

Построим граф- дерево по условию задачи.

Перечислим полученные тройки: Ц1-П2-Л2; Ц2-П1-Л1; Ц3-П3-Л3. Других вариантов нет.

          Каждая мышка за одну ночь может побывать на складе с тремя другими мышками. Чтобы побывать на складе с каждой из 23 других мышек по одному разу, ей необходимо 23:3 ночей. Но число 23 не делится нацело на три. Поэтому такая ситуация невозможна.

Ответ: нет, такого быть не может.

Для решения нужно построить граф, в котором вершины – номера комнат, а ребра – двери.

Дополнительные задачи:

«Дорогой друг!

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

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

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

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

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

Введем обозначения состояний и воздействий.

Состояния: А1 – нет ни Пения, ни Смеха; А2 – нет Пения, есть Смех; А3 –есть Пение, нет Смеха; Есть и Пение, и Смех.

Воздействия: В1 – нет ни ладана, ни органа, В2 – нет ладана, есть орган, В3 – есть ладан, нет органа, В4 – Есть ладан, есть орган.

По условию задачи построим ориентированный граф.

Ответ: 1-я минута – ничего не делать, 2-я минута – поиграть на органе, затем при молчащем органе постоянно жечь ладан.

Из состояния А4 можно перейти в состояние А3 (при воздействии В1 или В2). Из состояния А3 при воздействии В2 можно перейти в требуемое состояние А1. Остаться в А1 можно, оказывая постоянное воздействие В3. Итак, алгоритм поведения для установления и поддержки тишины в доме: 1-я минута – ничего не делать; 2-я минута – поиграть на органе; затем при молчащем органе постоянно жечь ладан.

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

1.                 Англичанин живет в красном доме.

2.                 У испанца есть собака.

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

4.                 Француз пьет чай.

5.                 У того, кто курит большие сигары, есть попугайчики.

6.                 Маленькие сигары курят в желтом доме.

7.                 Молоко пьют в среднем доме.

8.                 Швед живет в крайнем доме слева.

9.                 Тот, кто курит сигареты, живет в доме, соседнем с тем домом, где держат обезьяну.

10.             Тот, кто курит маленькие сигары, живет рядом с владельцем кошки.

11.             Тот,  кто курит трубку, пьет апельсиновый сок.

12.             Итальянец вообще не курит.

13.             Швед живет рядом с голубым домом.

Вопрос. Кому принадлежит зебра?

Проанализировав условие задачи, мы пришли к выводу:

1. Швед живет в желтом доме.

 Зеленый стоит справа от белого, а у шведа справа -  голубой, в красном доме живет англичанин.

2. В голубом доме живет француз

Француз пьет чай, значит, он не может жить в зеленом доме. Не может он жить и в красном доме, т. к. там – англичанин. Остается два варианта: в белом (если он не средний) или в голубом. Если француз живет в белом доме, то в голубом либо испанец, либо итальянец. Но в голубом доме кошка, значит испанец не может там жить (у него собака) и итальянец там жить не может, т.к. тогда он пьет апельсиновый сок, а значит курит трубку, что противоречит условию задачи (Швед курит маленькие сигары, значит не пьет апельсиновый сок; англичанин в красном среднем доме, значит пьет молоко; француз - в белом доме и он всегда пьет чай, а в зеленом – пьют кофе) Следовательно, француз – в голубом доме.

3. В среднем доме живет англичанин и этот дом красного цвета.

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

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

4. Итальянец живет в зеленом доме, а испанец – в белом.

испанец

итальянец

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

5. Итальянцу принадлежит зебра!

Итак, построим граф условия задачи, учитывая все предыдущие пункты.

Все условия выполняются, значит, Зебра принадлежит итальянцу. Ответ: зебра принадлежит итальянцу.