Страница:
<< 2 3 4 5 6 7 8 >> [Всего задач: 67]
В некоторой стране каждые два города соединены либо авиалинией, либо железной дорогой. Докажите, что
а) можно выбрать вид транспорта так, чтобы от каждого города можно было добраться до любого другого, пользуясь только этим видом транспорта;
б) из некоторого города, выбрав один из видов транспорта, можно добраться до любого другого города не более чем с одной пересадкой (пользоваться можно только выбранным видом транспорта);
в) каждый город обладает свойством из пункта б);
г) можно выбрать вид транспорта так, чтобы пользуясь только им, можно было добраться из каждого города до любого другого не более чем с двумя пересадками.
|
|
|
Сложность: 4
Классы: 9,10,11
|
В стране 64 города, некоторые пары из них соединены дорогой, но нам неизвестно, какие именно. Можно выбрать любую пару городов и получить ответ на вопрос “есть ли дорога между ними?”. Нужно узнать, можно ли в этой стране добраться от любого города до любого другого, двигаясь по дорогам. Докажите, что не существует алгоритма, позволяющего сделать это менее чем за 2016 вопросов.
|
|
|
Сложность: 4
Классы: 8,9,10
|
Между некоторыми из 2n городов установлено воздушное сообщение, причём каждый город связан (беспосадочными рейсами) не менее чем с n другими.
а) Докажите, что если отменить любые n – 1 рейсов, то всё равно из любого города можно добраться в любой другой на самолётах (с пересадками).
б) Укажите все случаи, когда связность нарушается при отмене n рейсов.
|
|
|
Сложность: 4
Классы: 8,9,10
|
В некотором государстве города соединены дорогами. Длина каждой дороги меньше 500 км, и из каждого города в любой другой можно попасть, проехав по дорогам меньше 500 км. Когда одна дорога оказалась закрытой на ремонт, выяснилось, что из каждого города можно проехать по оставшимся дорогам в любой другой. Доказать, что при этом можно проехать меньше 1500 км.
|
|
|
Сложность: 4
Классы: 8,9,10
|
В стране Нашии есть военные базы, соединённые дорогами. Набор дорог называется
важным, если после закрытия этих дорог найдутся две базы, не соединённые путем. Важный набор называется стратегическим, если он не содержит
меньшего важного набора. Докажите, что множество дорог, каждая из которых
принадлежит ровно одному из двух различных стратегических наборов, образует
важный набор.
Страница:
<< 2 3 4 5 6 7 8 >> [Всего задач: 67]
Фильтр
