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

Проект МЦНМО
при участии
школы 57
Все авторы >> Иванов И.

Фильтр
Сложность с по   Класс с по  
Все задачи автора

Страница: 1 [Всего задач: 1]      



Задача 109778

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

Автор: Иванов И.

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

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

Страница: 1 [Всего задач: 1]      



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

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