Олимпиада имени Леонарда Эйлера 2022-2023 учебный год, II тур заключительного этапа

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

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

Ответ $150$

Очевидно что белых дорог должно быть как минимум $100$. Т.к мы должны начинать путь с белой дороги.

Допустим возможно сделать это использовав меньше 150 дорог $149$. Тогда т.к меньше $100$ белых дорог быть не может. Значит найдётся как минимум $2$ города у которых не будет черных дорог. Значит даже если мы попытаемся выполнить условия, мы с какого то города не сможем попасть в другой город выполнив условие с чередованием цветов дорог.

Т.к с 2 городов не выходит чёрных дорог.

Nebayan почему вы решаете только баян задачи

Сорри

Why if we start with white ,white road will be 100 as to me its not obviously can u explain

сори перепутал матол с аопсом

Вы не доказали что если 2 города не имеют чёрных дорог то условие чередования дорог не выполняеться.

Да полностью согласен с вами Мимимишка, а вы Баянище не расмотрели случай где как мимимишка сказал не обосновали одну часть решение.

Ответ: 150

Заметим что, дорог как минимум 100. Также, заметим что если бы у нас было 100 дорог, этого не хватило, так как у нас есть те города, которые начинаются с черных дорог.

Таким образом, мы понимаем что нужно еще 100/2=50 дорог так как нужно провести дороги от черных до белых, отсюда и ответ 100+50=150.