Покори Воробьёвы горы! 2022, 9 класс, задача 6
К середине XXII века человечество освоило обитаемых планет в других звездных системах. От каждой планеты расходится гиперпространственных порталов, и к каждой планете ведёт порталов от других планет. Все порталы строго односторонние, т.е. если есть портал, ведущий из в , то нет портала, ведущего из в . Мистер Риггз хочет добраться с Галатеи-37 на Пандору за наименьшее число гиперпространственных прыжков. Сколько прыжков ему может потребоваться (укажите все варианты)?
Ответ: , или .
Решение. Докажем, что кратчайший маршрут потребует не более прыжков. Пусть нет прямого маршрута с Галатеи на Пандору. Тогда разобьем планеты на множества:
А - планеты, на которые ведут порталы с Галатеи ( штук);
Б - планеты, с которых ведут порталы на Пандору и сама Пандора ( штука);
В - все остальные.
Если множества А и Б имеют пересечение, то существует маршрут длины . Пусть не пересекаются, тогда В состоит из планет.
С планет множества А выходит порталов. На планеты множества А ведут не более из них. А на планеты множества В ведут не более . Всего получаем , следовательно, существуют порталы, ведущие на планеты из множества Б. Тогда найдется маршрут длины или .