ВСОШ 2025, 10 класс, задача 2

Очень сложная
Комбинаторика
Источник:
Всероссийская олимпиада школьников, Региональный (9–11 классы), 2025, 10 класс, Первый тур

( баллов) В стране городов и двусторонних авиалиний, соединяющих города по циклу. Можно ли добавить дополнительно ещё авиалиний так, чтобы после этого из любого города можно было добраться до любого другого не более чем за перелёта?

(П. Кожевников)

Верно или неверно?

Войдите, чтобы проверять ответы
Ответ

Ответ. Можно.

Решение. Занумеруем города числами , , , , так, чтобы изначально у нас был цикл . Добавим авиалиний , , , , (а -ю авиалинию добавим какую угодно).

Покажем, что условие выполняется. Возьмём любые два города и . От можно не более чем за перелёт добраться до города с номером, кратным . Аналогично, от можно не более чем за перелёт добраться до города с номером, кратным . А между городами и либо есть путь не более чем из двух перелётов, так как все города с номерами, кратными , соединены с городом номер .

1

Приведён верный пример, но отсутствует обоснование его правильности.

6
2

Приведён верный пример, в котором добавлено менее авиалиний.

−0
Максимум: 7

Похожие задачи

ВСОШ 2025, 10 класс, задача 8

(7 баллов) В клетчатом прямоугольнике 2 × 100 каждую клетку красят в белый или чёрный цвет. Доминошкой будем называть клетчатый прямоугольник 1 × 2 или 2 × 1. Оказалось, что существует единственный способ разбить данный прямоугольник 2 × 100 на доминошки так, чтобы каждая доминошка покрывала хотя бы
Очень сложная
Комбинаторика

ВСОШ 2025, 11 класс, задача 6

(7 баллов) Изначально на табло горит число 0. При нажатии на кнопку число на табло изменяется на 50 или 51. На кнопку нажали 2025 раз. Могло ли после этого на табло гореть число 25, если известно, что на табло не появлялись более чем двузначные числа, а также не появлялись отрицательные числа? (А. К
Очень сложная
Комбинаторика

ВСОШ 2025, 10 класс, задача 4

(7 баллов) Можно ли на бесконечной клетчатой плоскости отметить конечное число узлов сетки так, чтобы было отмечено не менее двух точек, и для любой пары отмеченных точек нашлась бы отмеченная точка, равноудалённая от них? (И. Ефремов)
Очень сложная
Комбинаторика

ВСОШ 2026, 11 класс, задача 3

(7 баллов) Петя и Вася играют в игру. В начале игры на столе лежат 1000 куч, состоящих из 1, 2, 3, 4, ldots, 999, 1000 спичек соответственно. Ребята ходят по очереди, начинает Петя. Каждый из мальчиков своим ходом может взять любое ненулевое количество спичек из кучи с наибольшим количеством спичек
Очень сложная
Комбинаторика