Математикадан облыстық олимпиада, 2016-2017 оқу жылы, 10 сынып

Компьютер желісінде 2017 компьютер. Кез келген екі компьютер кабельмен жалғанған. Желіде компьютерлердің шамадан тыс жұмыс істеуінен, қайта-қайта желінің бір бөлігінде жұп компьютерлерден құралған циклдің бір кабелі күйіп кетеді. Егер күйіп кеткен кабельдердің ешқайсысы жөнделмейтін болса, онда бірнеше уақыттан кейін тура 2016 бүтін кабель қалуы мүмкін бе?

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

Решение. Предположим это возможно. Так как разрывы происходят только внутри некоторых циклов, то связность графа при каждом перегорании не нарушается. Это означает, что в конце мы получим дерево на 2017 вершинах, любое дерево является двудольным графом.

Запустим процесс в обратную сторону. Если добавлять по одному ребру к двудольному графу так, что возникает некоторый четный цикл, то ребром соединяются только вершины из разных долей, значит двудольность графа сохраняется. Если таким образом можно вернуться к первоначальному полному графу, то он также должен быть двудольным, что очевидно не верно. Противоречие.