Тип 11 № 7611 В Тридевятом царстве лишь один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов по 20. Можно ли из столицы долететь в Дальний (возможно, с пересадками). В ответе запишите 1, если это возможно, или 0, если невозможно.

Представим эту ситуацию в виде графа, где города - это вершины, а ковролинии - ребра. Всего городов, кроме столицы и Дальнего, пусть будет N. Тогда количество ребер в графе равно 21 (из столицы) + 1 (из Дальнего) + 20*N (из остальных городов). Общее количество ребер должно быть четным, так как каждое ребро соединяет 2 вершины. Таким образом, нужно проверить, может ли 21 + 1 + 20*N быть четным числом. 21 + 1 + 20*N = 22 + 20*N = 2*(11 + 10*N) Это всегда четное число, так как оно делится на 2. Из этого следует, что такая конфигурация городов и ковролиний возможна. Это не означает, что можно добраться из столицы в Дальний, а лишь то, что такая схема существует. Чтобы доказать или опровергнуть возможность добраться из столицы в Дальний, потребовалось бы больше информации о связности графа. Но в данной задаче нас интересует, возможна ли такая конфигурация в принципе, поэтому ответ – да. Ответ: 1