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

ВСОШ 2025, региональный этап, 10 класс, задача 2

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

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

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

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

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

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

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

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 класс, задача 10

(7 баллов) На графике функции y=x2 отметили 1000 различных точек, абсциссы которых — целые числа из отрезка [0;100000]. Докажите, что можно выбрать шесть различных отмеченных точек A, B, C, A', B', C' таких, что площади треугольников ABC и A'B'C' равны. (А. Терёшин)
Очень сложная
Алгебра
Комбинаторика

ВСОШ 2025, региональный этап, 10 класс, задача 4

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