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

Белгілі бір елде 2024 қала бар, олардың кейбіреулері жолдармен байланысқан. Әр қала кем дегенде үш басқа қаламен байланысқан. Бұл жолдармен елдің кез келген қаласынан кез келген басқа қалаға жетуге болады (тура жолмен жету міндетті емес). Кез келген екі қала үшін екі қала арасындағы ең қысқа маршрут анықталды. Осы ең қысқа маршрутта ең көп дегенде неше жол болуы мүмкін?

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

Ответ: 1012.

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