Олимпиадные задачи по теме «Методы» для 7-11 класса - сложность 3 с решениями

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

Сто мудрецов хотят проехать на электричке из 12 вагонов от первой до 76-й станции. Они знают, что на первой станции в два вагона электрички сядут два контролёра. После четвёртой станции на каждом перегоне один из контролёров будет переходить в соседний вагон, причём они "ходят" по очереди. Мудрец видит контролёра, только если он в соседнем вагоне или через вагон. На каждой станции каждый мудрец может перебежать по платформе не далее чем на три вагона (например, из 7-го вагона мудрец может добежать до любого вагона с номером от 4 до 10 и сесть в него). Какое максимальное число мудрецов сможет ни разу не оказаться в одном вагоне с контролёром, как бы контролёры ни перемещались? (Никакой информации о контролёрах, кроме указанной в задаче, мудрец не получает. Мудрецы договариваются о...