Страница:
<< 15 16 17 18
19 20 21 >> [Всего задач: 123]
|
|
|
Сложность: 4
Классы: 6,7,8
|
а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?
б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?
Имеется 20 бусинок десяти цветов, по две бусинки каждого цвета. Их как-то
разложили в 10 коробок. Известно, что можно выбрать по бусинке из каждой
коробки так, что все цвета будут представлены. Докажите, что число способов
такого выбора есть ненулевая степень двойки.
|
|
|
Сложность: 4
Классы: 7,8,9,10
|
В стране несколько городов, некоторые пары городов соединены беспосадочными
рейсами одной из N авиакомпаний, причём из каждого города есть ровно по
одному рейсу каждой из авиакомпаний. Известно, что из каждого города можно
долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт N – 1 рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по-прежнему из каждого города можно
долететь до любого другого.
|
|
|
Сложность: 4+
Классы: 9,10,11
|
В стране больше 101 города. Столица соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с десятью городами (если A соединён с B, то B соединён с A). Известно, что из каждого города можно попасть в любой другой (может быть, с пересадками). Доказать, что можно закрыть половину авиалиний, идущих из столицы, так, что возможность попасть из каждого города в любой другой сохранится.
|
|
|
Сложность: 5-
Классы: 8,9,10,11
|
В королевстве 16 городов. Король хочет построить такую систему дорог, чтобы
из каждого города можно было попасть в каждый, минуя не более одного
промежуточного города, и чтобы из каждого города выходило не более пяти дорог.
а) Докажите, что это возможно.
б) Докажите, что если в формулировке заменить число 5 на число 4,
то желание короля станет неосуществимым.
Страница:
<< 15 16 17 18
19 20 21 >> [Всего задач: 123]
Фильтр
Решение 
