Страница:
<< 4 5 6 7
8 9 10 >> [Всего задач: 67]
|
|
|
Сложность: 5-
Классы: 8,9,10,11
|
В некотором государстве было 2002 города, соединённых дорогами так, что если запретить проезд через любой из городов, то из каждого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002.
|
|
|
Сложность: 5-
Классы: 9,10,11
|
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими k авиакомпаниям. Известно, что каждые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на k + 2 группы так, что никакие два города из одной группы не соединены авиалинией.
|
|
|
Сложность: 5-
Классы: 9,10,11
|
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на 2N + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
|
|
|
Сложность: 5
Классы: 9,10,11
|
В стране N 1998 городов, и из каждого осуществляются беспосадочные
перелеты в три других города (все авиарейсы двусторонние). Известно, что
из каждого города, сделав несколько пересадок, можно долететь до любого
другого. Министерство Безопасности хочет объявить закрытыми 200 городов,
никакие два из которых не соединены авиалинией. Докажите, что это можно
сделать так, чтобы можно было долететь из каждого незакрытого города в
любой другой, не делая пересадок в закрытых городах.
|
|
|
Сложность: 5
Классы: 8,9,10
|
В некоторой группе из 12 человек среди каждых девяти найдутся пять попарно знакомых. Докажите, что в этой группе найдутся шесть попарно знакомых.
Страница:
<< 4 5 6 7
8 9 10 >> [Всего задач: 67]
Фильтр
