Математикадан Эйлер олимпиадасы, 2013-2014 оқу жылы, Дистанциялық кезеңнің 2-ші туры


Думуляндия елінде әр қаладан дәл 10 жол шығатын және әр жол дәл екі қаланы қосатын. Сонымен қатар, жол торы бір бірімен байланысты болған, яғни әр қаладан жолмен жүріп басқа қалаға (мүмкін, басқа қала арқылы) жетуге болатын. Бірақ су тасқыны кезінде екі қаланы су басқаннан кейін, байланыс бұзылды (өйткені су басқан қала арқылы жүруге болмайды). Су тасқынына дейін, байланыс бұзылатындай етіп, 9 жолды жабуға болғанын дәлелде.
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Решение. В сумме из затопленных городов выходило 18 дорог в другие города (назовем эти дороги затопленными). После наводнения все города распались минимум на две части, и проехать из одной части в другие можно только через затопленные города. Хотя бы в одну из этих частей ведет не более 9 затопленных дорог. Если бы эти дороги закрыли до наводнения, то из этой части также нельзя бы было проехать в остальные города.