Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

  2
1 года 7 месяца назад #

Ответ 150

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

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

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

  0
1 года 3 месяца назад #

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

пред. Правка 2   2
1 года 3 месяца назад #

Сорри

пред. Правка 2   1
1 года 3 месяца назад #

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

  0
1 года 3 месяца назад #

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

  1
1 года 2 месяца назад #

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

  0
1 года 2 месяца назад #

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

  1
1 года 1 месяца назад #

Ответ: 150

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

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