Семинар ДООМ Кружок 5-8, Текстовые задачи, решаемые с помощью теории графов
Коннова Елена
Руководитель команд ДООМ 2008 МОЗГИ ID 215 и Великие математики ID_214
Предлагаю ряд статей, обьединенных в цикл "олимпиадные задачи. Кружок 5-8." Все они вошли в состав сборников, один из которых вышел издательстве Легион (Е.Г. Коннова. Математика. Серия «Готовимся к олимпиаде». Ростов н/Д: Легион, 2008.), а второй готовится к печати.
Занятие 4. Свойства полного графа
В полном графе с вершинами число ребер равно N(N-1):2 .
В полном графе с N вершинами из каждой вершины выходит по N-1 ребер, Значит сумма степеней вершин равна N(N-1). Число ребер в 2 раза меньше.
Задача.
Дворовый хулиган Петя хочет отобрать у пятиклассника Леши МП3-плеер, но согласен и не отбирать, если Леша решит за него задачу. Задачу задали на дом, обещая поставить 3 за четверть по геометрии. Задача очень трудная - найти, сколько диагоналей в 17-угольнике. Помогите Леше.
Решение.
Вершины 17-угольника – вершины графа, диагонали и стороны – ребра графа. Всего 136 ребер. Из них 17 сторон, остальные диагонали. Значит, диагоналей 136-17=119.
Задача.
Ваня и Миша играют в такую игру. Они по очереди связывают 5 столбиков ленточками попарно. Кто свяжет последнюю пару столбиков, тот выиграл. Кто победит – тот, кто завяжет первую ленточку, или его соперник?
Решение.
После того, как все ленты будут завязаны, получится полный граф с 5 вершинами – столбиками и ребрами-ленточками. В этом графе 5(5-1):2=10 ребер. Значит, выиграет тот, кто завязывал ленту вторым.
Задача.
В сарае 10 корыт с едой и 20 поросят. Через некоторое время поросята перебегают от одного корыта к другому. Известно, что от каждого корыта к каждому пробегал какой-нибудь поросенок. Докажите, что хоть один поросенок перебегал не менее трех раз.
Решение.
Обозначим корыта точками – вершинами графа. Если между ними пробегал поросенок, то вершины соединим ребром. Если от каждого корыта к каждому пробегал какой-нибудь поросенок, то граф полный, и в нем проведено хотя бы 10*9:2=45 ребер. Если бы каждый поросенок перебежал от одного корыта к другому не более 2 раз, то ребер провели бы не более 10*2=40. Значит, хоть один поросенок перебегал не менее трех раз.
Задача.
Между 7 планетами звездной системы установлено ракетное сообщение. Министр рапортовал, что с каждой планеты существует прямой рейс ровно на 5 других планет системы. Докажите, что министр ошибся.
Решение.
Пусть планеты – вершины графа, а маршруты – ребра. Если министр прав, то сумма степеней вершин этого графа равна , а нечетной она быть не может. Значит, министр ошибся.
Задача.
Маша сказала своей подружке Лене: «У нас в классе двадцать пять человек. И представь, каждый из них дружит ровно с семью одноклассниками». «Не может этого быть» - ответила Лена. Почему она так решила?
Решение.
Представим себе, что между каждыми двумя друзьями протянута веревочка. Тогда каждый из 25 учеников будет привязан к 11 концам веревочек, и значит, всего у протянутых веревочек будет концов. Но их общее число не может быть нечётным, так как у каждой веревочки 2 конца.
Другие работы:
Семинар ДООМ 2008 "Формула текста"
Семинар ДООМ Кружок 5-8, Четность
Семинар ДООМ Кружок 5-8, Задачи на проценты
Семинар ДООМ Кружок 5-8, Игры (задачи на стратегию)
Семинар ДООМ Кружок 5-8, Принцип Дирихле
Семинар ДООМ Кружок 5-8, Текстовые задачи, решаемые с помощью теории графов
Семинар ДООМ 2007 "Графы"
Семинар ДООМ Задачи, решаемые с помощью деревьев
Элективный курс Графы 6-8 класс Программа курса 18 часов
Материалы для курса Графы - Материалы для оценивания усвоения содержания Элективного курса
