В стране из каждого города выходит ровно три дороги. Может ли в этой стране быть 2014 дорог?

Рассмотрим города как вершины графа, а дороги как рёбра. Условие «из каждого города выходит ровно три дороги» означает, что степень каждой вершины равна 3.

Теперь применим стандартный подсчёт “рукопожатий” для графов:

• Если сложить числа дорог, выходящих из каждого города, то получится сумма степеней всех вершин.

• Поскольку из каждого города выходит 3 дороги, при числе городов $n$ сумма степеней равна $3n$.

• Но при таком подсчёте каждая дорога учитывается дважды: один раз со стороны одного города и один раз со стороны другого. Значит,

  $$3n = 2m,$$

  где $m$ — число дорог.

Отсюда

Следовательно, число дорог $m$ обязательно должно быть кратно 3 (потому что $m = 3\cdot \frac{n}{2}$, а $\frac{n}{2}$ — целое число, так как $n$ должно быть чётным, иначе $\frac{3n}{2}$ не было бы целым).

Проверим $2014$:

• $2014$ не делится на 3 (потому что $2+0+1+4=7$, а 7 не кратно 3).

• Значит, $2014$ не может быть представлено в виде $\frac{3n}{2}$ для целого $n$.

Или напрямую:

а это не целое число, то есть «число городов» таким быть не может.

Ответ: нет, в такой стране не может быть 2014 дорог.