Городская олимпиада по математике среди физ-мат школ г. Алматы

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

Комментарий/решение

Ответ: 1012.

Для начала давайте соединим все соседние города. То есть для каждого i-ного города будет i+1 (i<2024) город. Тогда можно заметить что их будет 2023. Но а каждого должно быть проведено по 3 дороги, а проведена 1, значит мы можем провести ккк можно ближе, то есть для каждого n-ного города проведем к n+1. Также провести n+2 дорогу, чтобы было как можно кратче. Мы проводим наикратчайшие, чтобы получить найбольшее кол-во дорог. Между ними будет разница на 2, то есть n+2-n=2. Тогда всего дорог 2024 => 2024/2=1012