Олимпиада имени Леонарда Эйлера 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.