Страница:
<< 4 5 6 7
8 9 10 >> [Всего задач: 180]
Задача
31070
(#02)
|
|
Сложность: 3+
Классы: 6,7,8
|
В кружке у каждого члена имеется один друг и один враг. Доказать, что
а) число членов чётно.
б) кружок можно разделить на два нейтральных кружка.
Решение
а) Весь кружок разбивается на пары друзей.
б) Поскольку степень каждой вершины соответствующего графа равна 2, то он разбивается на циклы. В каждом цикле рёбра "дружбы" и "вражды" чередуются, значит, тех и других поровну. Поместив в один кружок членов каждого цикла, взятых через одного, мы получим кружок, где нет ни друзей, ни врагов. Оставшиеся члены образуют второй нейтральный кружок.
Задача
35089
(#03)
|
|
Сложность: 3+
Классы: 9,10,11
|
В стране n городов. Между каждыми двумя городами установлено воздушное сообщение одной из двух авиакомпаний. Докажите, из этих двух авиакомпаний хотя бы одна такова, что что из любого города можно попасть в любой другой рейсами только этой авиакомпании.
Решение
См. задачу 30814 а).
Задача
31072
(#04)
|
|
Сложность: 3
Классы: 6,7,8
|
В некоторой стране из столицы выходит 89 дорог, из города Дальний – одна дорога, из остальных 1988 городов – по 20 дорог.
Доказать, что из столицы можно проехать в Дальний.
Решение
См. задачу 30429.
Задача
77930
(#05)
|
|
Сложность: 3
Классы: 8,9
|
На консультации было 20 школьников и разбиралось 20 задач. Оказалось, что
каждый из школьников решил две задачи и каждую задачу решили два школьника. Докажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были разобраны.
Решение
Дадим каждому школьнику карточку, на которой он напишет номера решённых им задач. Теперь задача свелась к задаче 31079.
Задача
31074
(#06)
|
|
Сложность: 3+
Классы: 6,7,8
|
Из полного 100-вершинного графа выкинули 98 рёбер. Доказать, что он остался связным.
Решение
Предположим, что полученный граф оказался несвязным, и в одной из компонент связности n вершин. Тогда было выкинуто по крайней мере
n(100 – n) рёбер, соединявших вершины этой компоненты с вершинами других компонент. Но n(100 – n) = 50² – (n – 50)² ≥ 50² – 49² = 1·99 > 98. Противоречие.
Страница:
<< 4 5 6 7
8 9 10 >> [Всего задач: 180]
Фильтр
