Теория графов в школьном курсе математики.
проект по алгебре (6 класс) по теме

ЗАДАЧИ КОНКУРСНОГО ТУРА

Задача 1. В Простоквашинской начальной школе учится всего 20 детей. У любых двух из них есть общий дед. Докажите, что у одного из дедов в этой школе учится не менее 14 внуков и внучек.

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

Задача 3. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

Задача 4. На карте обозначено 4 деревни: A, B, C и D, соединённые тропинками (см. рисунок). В справочнике написано, что на маршрутах B–C–D и A–D–C по 12 колдобин, на маршруте A–C–B – 25 колдобин, а на маршруте B–A–C – 52 колдобины. Туристы хотят добраться из A в B так, чтобы на их пути было как можно меньше колдобин. По какому маршруту им надо идти? Не забудьте доказать, что на указанном Вами маршруте действительно меньше всего колдобин.

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

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

Задача 7.  В составе экспедиции должно быть 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?  

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

В самолете летели 42 пассажира — москвичи и ростовчане. Среди москвичей было 9 мужчин. Некоторые из пассажиров были артистами, но ни одна из женщин-ростовчанок артисткой не была. Мужчин-ростовчан было 18. Из них 13 не были артистами. Среди пассажиров не артистов было 16 мужчин и 11 женщин. 6 москвичей не были артистами. Определите количество москвичей и ростовчан в самолете, сколько из них было  женщин и мужчин артистов и не артистов.

Задача 9. Путешествие Пятачка

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

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

Задача 10. Тройка нападения

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

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

Задача 12. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон- Венера,  Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса?

Задача 13. В квартирах № 1, № 2, № 3 живут три котенка – белый, черный, рыжий. В квартирах  № 1 и № 2 живут не черные котята. Белый котенок  живет не в квартире № 1. В какой квартире какой котенок живет?

Задача 14. В норке живет семья из 24 мышей. Каждую ночь ровно четыре из них отправляются на склад за сыром. Может ли так получиться, что в некоторый момент времени каждая мышка побывала на складе с каждой ровно по одному разу?

Задача 15. На рисунке план  подземелья, в одной из комнат которого скрыты богатства рыцаря. Чтобы безопасно проникнуть в эту комнату, надо, войти через определенные ворота в одну из крайних комнат подземелья, пройти последовательно через все 29 дверей, выключая сигнализацию тревоги. Проходить дважды через одни и те же двери нельзя. Определить номер комнаты, в которой скрыты сокровища и ворота, через которые нужно войти?

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

Задача 1. О доме с привидениями

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

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

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

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

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

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

Задача 2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 3. Изобразите в виде графа Солнечную систему, которая включает планеты и их спутники: Марс со спутниками Деймос и Фобос; Земля со спутником Луна; Меркурий; Венера; Юпитер со спутниками Ганимед, Каллисто, Европа, Ио; Плутон со спутником Харон; Уран со спутниками Оберон, Титания; Сатурн со спутником Титан; Нептун со спутником Тритон.