ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 66]      



Задача 109762

Темы:   [ Связность и разложение на связные компоненты ]
[ Степень вершины ]
[ Наименьшее или наибольшее расстояние (длина) ]
Сложность: 5-
Классы: 8,9,10,11

Автор: Пастор А.

В некотором государстве было 2002 города, соединённых дорогами так, что если запретить проезд через любой из городов, то из каждого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002.

Прислать комментарий     Решение

Задача 109800

Темы:   [ Связность и разложение на связные компоненты ]
[ Принцип крайнего (прочее) ]
[ Перебор случаев ]
Сложность: 5-
Классы: 9,10,11

В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими k авиакомпаниям. Известно, что каждые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на  k + 2  группы так, что никакие два города из одной группы не соединены авиалинией.

Прислать комментарий     Решение

Задача 110038

Темы:   [ Связность и разложение на связные компоненты ]
[ Обход графов ]
[ Вспомогательная раскраска (прочее) ]
Сложность: 5-
Классы: 9,10,11

В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на  2N + 2  республики так, чтобы никакие два города из одной республики не были соединены дорогой.

Прислать комментарий     Решение

Задача 109663

Темы:   [ Связность и разложение на связные компоненты ]
[ Степень вершины ]
[ Метод спуска ]
Сложность: 5
Классы: 9,10,11

В стране N  1998 городов, и из каждого осуществляются беспосадочные перелеты в три других города (все авиарейсы двусторонние). Известно, что из каждого города, сделав несколько пересадок, можно долететь до любого другого. Министерство Безопасности хочет объявить закрытыми 200 городов, никакие два из которых не соединены авиалинией. Докажите, что это можно сделать так, чтобы можно было долететь из каждого незакрытого города в любой другой, не делая пересадок в закрытых городах.

Прислать комментарий     Решение

Задача 109698

Темы:   [ Связность и разложение на связные компоненты ]
[ Наименьшее или наибольшее расстояние (длина) ]
Сложность: 5
Классы: 8,9,10

В некоторой группе из 12 человек среди каждых девяти найдутся пять попарно знакомых. Докажите, что в этой группе найдутся шесть попарно знакомых.

Прислать комментарий     Решение

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 66]      



© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .