Задача
№ 14220
Оценка + пример (экстремальные комбинаторные задачи)
Ур. 5
Всероссийская олимпиада школьников по математике, 11 класс, школьный этап 2021/22 уч. г. (Москва), задача 7
В стране 110 городов. Между каждыми двумя из них либо есть дорога, либо её нет.
Автомобилист находился в некотором городе, из которого вела ровно одна дорога. Проехав по дороге, он оказался во втором городе, из которого вели уже ровно две дороги. Проехав по одной из них, он оказался в третьем городе, из которого вели уже ровно три дороги, и так далее. В какой-то момент, проехав по одной из дорог, он оказался в $N$-м городе, из которого вели уже ровно $N$ дорог. На этом автомобилист своё путешествие прекратил. (Для каждого $2\leqslant k\leqslant N$ из $k$-го города выходило ровно $k$ дорог с учётом той, по которой автомобилист в этот город приехал.)
Какое наибольшее значение может принимать $N$?
Автомобилист находился в некотором городе, из которого вела ровно одна дорога. Проехав по дороге, он оказался во втором городе, из которого вели уже ровно две дороги. Проехав по одной из них, он оказался в третьем городе, из которого вели уже ровно три дороги, и так далее. В какой-то момент, проехав по одной из дорог, он оказался в $N$-м городе, из которого вели уже ровно $N$ дорог. На этом автомобилист своё путешествие прекратил. (Для каждого $2\leqslant k\leqslant N$ из $k$-го города выходило ровно $k$ дорог с учётом той, по которой автомобилист в этот город приехал.)
Какое наибольшее значение может принимать $N$?
Ответ:
Решение: