Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/vmsh/vmsh_6_1112/krug-2011-610-graf.pdf Дата изменения: Thu Dec 15 14:29:22 2011 Дата индексирования: Tue Feb 5 03:08:29 2013 Кодировка: Windows-1251 Поисковые слова: http astrokuban.info astrokuban

Гимназия 1543. Математический кружок для 6 класса.

В купе поезда ехали 4 человека. Среди них не было троих, попарно знакомых друг с другом, но один был знаком с тремя остальными. Докажите, что никакие двое из этих трех пассажиров не были знакомы. В Тридевятом царстве 27 городов. Между некоторыми проложены дороги. Известно, что для любых двух городов существует единственный соединяющий их маршрут. а) Обязательно ли найдется город, из которого ведет только одна дорога? б) Сколько дорог в Тридевятом царстве? 1. В классе 14 девочек. Если одна из них узнает новость, то обязательно передает ее всем подружкам. Аня дружит с пятью одноклассницами, а Лиза с восемью. Докажите, что если Аня узнает новость, то и Лиза тоже. 2. В пруд запустили 30 щук, которые постепенно поедают друг друга. Щука считается сытой, если она съела трех щук (сытых или голодных). Какое наибольшее число щук может насытиться? 3. В некотором королевстве было 32 рыцаря. Некоторые из них были вассалами других (вассал может иметь только одного сюзерена, прич?м сюзерен всегда богаче своего вассала). Рыцарь, имевший не менее четыр?х вассалов, носил титул барона. Какое наибольшее число баронов могло быть при этих условиях? (В королевстве действовал закон: "вассал моего вассала - не мой вассал"). 4. В Разноцветной стране 6 городов. Любые два соединены дорогой либо из желтого кирпича, либо из красного булыжника. Докажите, что найдутся три города, соединенных одинаковыми дорогами. 5. Докажите, что в группе из 6 человек всегда найдутся либо трое попарно знакомых, либо трое попарно незнакомых. 6. 17 ученых из разных стран мира переписываются на одном из трех языков. Докажите, что среди них найдутся трое, которые переписываются на одном языке. 7. Граф де Планар повелел построить для своих сыновей 6 замков и соединить их дорогами так, чтобы из каждого вели ровно 3 дороги, причем дороги эти не должны пересекаться. Можно ли исполнить повеление? 8. Узнав об этом, графиня попросила расположить 6 замков так, чтобы из каждого вели 4 дороги, и чтобы они по-прежнему не пересекались. Выполнима ли просьба? 9. В Тридесятом государстве 30 городов, и каждые два соединены дорогой. Какое наибольшее количество дорог можно закрыть на ремонт так, чтобы из любого города можно было добраться в любой другой? 10. Волейбольная сетка прямоугольник 20 Ч 300 клеточек. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась?
Пример 1. Пример 2.

Графы

Занятие 10

15 декабря 2011г.

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