Страница:
<< 4 5 6 7
8 9 10 >> [Всего задач: 80]
|
|
|
Сложность: 4+
Классы: 8,9,10,11
|
Раскраска вершин графа называется правильной, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в k цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех k цветов ровно по одному разу.
|
|
|
Сложность: 4+
Классы: 9,10,11
|
В стране несколько городов, соединённых дорогами с односторонним и
двусторонним движением. Известно, что из каждого города в любой другой можно
проехать ровно одним путём, не проходящим два раза через один и тот же город.
Докажите, что страну можно разделить на три губернии так, чтобы ни одна дорога
не соединяла два города из одной губернии.
|
|
|
Сложность: 4+
Классы: 8,9,10
|
В стране n городов. Между каждыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнет путешествие, и маршрут так, что ему придётся поменять вид транспорта не более
одного раза.
|
|
|
Сложность: 5-
Классы: 9,10,11
|
В королевстве N городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются соседними). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.
Однажды Король провел такую реформу: каждый из N мэров городов стал снова мэром одного из N городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара соседних городов, обменявшихся мэрами.
Оля и Максим оплатили путешествие по архипелагу из 2009 островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл.
Докажите, что Оля может выиграть.
Страница:
<< 4 5 6 7
8 9 10 >> [Всего задач: 80]
Фильтр
Решение
