тугриков) Лемма "о рукопожатиях". Число нечетных вершин любого графа четно.
(5
тугриков) У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
(
5 тугриков) В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 по 5 друзей?
(
6 тугриков) Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 2000 дорог?
(10$)
В некоторой стране из столицы выходит 21 дорога, из города Дальнего одна дорога, а из остальных городов - по 20 дорог. Докажите, что из Дальнего можно проехать в столицу.
(6$)
Докажите, что нельзя нарисовать граф, степени вершин которого 4, 4, 4, 4, 2.
(5$)
Доказать, что дополнение несвязного графа - связно.
(4$)
Из полного 100-вершинного графа выкинули 98 ребер. Доказать, что он остался связным.
(12$)
В связном графе степени четырех вершин 3, степени остальных вершин - 4. Докажите, что нельзя из графа убрать одно ребро так, чтобы граф распался на две изоморфные компоненты связности.
(7$)
В стране из каждого города выходит 100 дорог и из каждого города страны можно добраться до любого другого. Одну дорогу закрыли на ремонт. Доказать, что и теперь из каждого города можно попасть в каждый.
(12$)
Докажите, что граф с n вершинами, степень каждой из которых не
менее (n-1)/2, - связен.
Призовые задачи:
(15$)
Доказать, что из любых шести человек можно выбрать трех попарно знакомых или трех попарно незнакомых.
(15$)
На конференции присутствует 50 ученых, каждый из которых знаком по крайней мере с 25 участниками конференции. Докажите, что найдутся четверо из них, которых можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ему людьми.
(15$) 20
участников воскресной математической школы получили листочки с 20-ю задачами. В конце урока обнаружилось, что каждый школьник решил две задачи, и каждую задачу решили два школьника. Докажите, что можно так устроить разбор задач, что каждый школьник расскажет по одной задаче.
(15$)
В кружке у любого члена имеется один друг и один враг. Доказать, что а) число членов кружка четно. б) кружок можно разделить на 2 нейтральных кружка (т.е. таких кружка, где ни у кого нет ни друзей, ни врагов).
(22$)
В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих ребер равно 40. Доказать, что из любой вершины можно попасть в любую, проходя не более чем по трем ребрам.
(26$)
Ребра полного 17-вершинного графа закрашены в три цвета. Доказать, что найдется одноцветный треугольник.
(20$)
Доказать, что из связного графа можно выкинуть вершину, оставив его связным.
Правила игры
"Миллион в кармане": Вначале игры все участники получают по 50 тугриков. Каждый ход игры состоит в следующем. Дается задача. Объявляется ее номинальная стоимость. Если через 5 минут задача не решена - стоимость увеличивается на 5 тугриков. Если за 15 минут задача не решена, у всех отнимается стоимость задачи. Кто первый решит задачу, рассказывает ее всем. Если решил неправильно, то у него отнимается стоимость задачи, а следующий имеет право рассказать задачу (стоимость задачи увеличивается на 5, и если в течении 5 минут желающего не находится, задача снимается с розыгрыша); если же решил правильно, то имеет право получить "призовую задачу". Призовые задачи стоят дороже. Если не решил "призовую", тебе дается номинальная стоимость решенной тобой задачи, если призовую решил, то полная стоимость задачи + стоимость "призовой". От призовой можно отказаться, чтобы не рисковать "надбавкой". В конце игры капитал участников переводится в баллы рейтинга по курсу 1:1 (даже отрицательные баллы). Плюс: занявший первое место получает (при условии, что наберет сумму >50 тугриков) 50 баллов, второй - 40 баллов, третий - 30 баллов. А просто набравшие >50 тугриков - 20 баллов.