Страна состоит из больших и малых городов. Каждый город (и малый, и большой) соединён дорогами с тремя малыми городами и с тремя большими городами. Докажите, что общее число городов в стране делится на 4.

Решение:

Обозначим количество малых городов как \( M \) и количество больших городов как \( B \). Общее число городов в стране равно \( N = M + B \).

Каждый малый город соединён дорогами с тремя малыми городами и тремя большими городами. Это означает, что степень вершины, соответствующей малому городу, равна \( 3 + 3 = 6 \).

Каждый большой город соединён дорогами с тремя малыми городами и тремя большими городами. Это означает, что степень вершины, соответствующей большому городу, также равна \( 3 + 3 = 6 \).

По лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному количеству рёбер (дорог). В нашем случае, каждая вершина имеет степень 6.

Сумма степеней всех городов равна \( 6M + 6B = 6(M+B) = 6N \).

Эта сумма равна удвоенному количеству дорог, то есть \( 2 \times \text{количество дорог} \).

Следовательно, \( 6N \) является чётным числом, что очевидно, так как \( N \) – целое число.

Теперь рассмотрим связи между малыми и большими городами. Каждый малый город соединён с тремя большими городами. Общее число дорог, исходящих из малых городов в большие, равно \( 3M \).

Каждый большой город соединён с тремя малыми городами. Общее число дорог, исходящих из больших городов в малые, равно \( 3B \).

Так как каждая дорога соединяет один малый и один большой город, количество дорог между малыми и большими городами должно быть одинаковым с обеих точек зрения. Поэтому \( 3M = 3B \), что означает \( M = B \).

Значит, количество малых городов равно количеству больших городов. Общее число городов \( N = M + B = M + M = 2M \).

Теперь вернёмся к условию, что каждый город соединён с тремя малыми и тремя большими городами. Это означает, что из любого города выходит ровно 6 дорог.

Рассмотрим число дорог, ведущих к малым городам. Каждый из \( M \) малых городов имеет степень 6, из которых 3 ведут к другим малым городам и 3 – к большим. Общее число дорог, выходящих из малых городов, равно \( 6M \). Из них \( 3M \) ведут к большим городам. Значит, \( 3M \) дорог ведут к малым городам.

Рассмотрим число дорог, ведущих к большим городам. Каждый из \( B \) больших городов имеет степень 6, из которых 3 ведут к другим большим городам и 3 – к малым. Общее число дорог, выходящих из больших городов, равно \( 6B \). Из них \( 3B \) ведут к малым городам. Значит, \( 3B \) дорог ведут к большим городам.

Мы уже установили, что \( M = B \). Пусть \( M = B = K \). Тогда общее число городов \( N = K + K = 2K \).

Число дорог, соединяющих два малых города, должно быть таким, чтобы при сложении степеней малых городов ( \( 3 \) от малых городов) получилось чётное число. \( 3M \) должно быть чётным. Это значит, что \( M \) должно быть чётным. Пусть \( M = 2k_1 \).

Аналогично, число дорог, соединяющих два больших города, должно быть таким, чтобы при сложении степеней больших городов ( \( 3 \) от больших городов) получилось чётное число. \( 3B \) должно быть чётным. Это значит, что \( B \) должно быть чётным. Пусть \( B = 2k_2 \).

Так как \( M = B \), то \( 2k_1 = 2k_2 \), что не даёт новой информации.

Однако, для того чтобы каждый малый город был соединён с тремя малыми городами, нужно, чтобы \( 3M \) было чётным, значит \( M \) должно быть чётным. Аналогично, \( 3B \) должно быть чётным, значит \( B \) должно быть чётным.

Итак, \( M \) – чётное число, и \( B \) – чётное число. Пусть \( M = 2a \) и \( B = 2b \).

Тогда общее число городов \( N = M + B = 2a + 2b = 2(a+b) \).

Мы знаем, что \( 3M \) дорог ведут к другим малым городам. Каждая из этих дорог соединяет два малых города. Это означает, что \( 3M \) должно быть равно удвоенному числу дорог между малыми городами, т.е. \( 3M \) чётно. Отсюда \( M \) – чётно.

Аналогично, \( 3B \) дорог ведут к другим большим городам. Это означает, что \( 3B \) должно быть равно удвоенному числу дорог между большими городами, т.е. \( 3B \) чётно. Отсюда \( B \) – чётно.

Поскольку \( M \) и \( B \) чётные, пусть \( M = 2k_m \) и \( B = 2k_b \).

Общее число городов \( N = M + B = 2k_m + 2k_b = 2(k_m + k_b) \).

Давайте используем другую логику. Предположим, что \( M \) – нечётное число. Тогда \( 3M \) – нечётное. Но \( 3M \) – это число дорог, исходящих из малых городов к другим малым городам. Это число должно быть чётным, так как дороги идут парами (если из города X в город Y идёт дорога, то из города Y в город X тоже идёт дорога, или одна дорога соединяет два города). Следовательно, \( M \) должно быть чётным.

Аналогично, \( 3B \) должно быть чётным, значит \( B \) должно быть чётным.

Итак, \( M \) и \( B \) – чётные числа.

Пусть \( M = 2a \) и \( B = 2b \). Тогда \( N = M + B = 2a + 2b = 2(a+b) \).

Однако, это не говорит о том, что \( N \) делится на 4.

Вернёмся к \( M = B \). Мы уже доказали это, рассматривая связи между малыми и большими городами.

Так как \( M = B \), и из каждого города выходит 6 дорог, то в сумме степеней всех городов: \( 6M + 6B = 6(M+B) = 6N \). Это удвоенное число дорог. \( 6N = 2 \times \text{дороги} \).

Рассмотрим дороги между малыми городами. Каждый малый город связан с 3 малыми городами. Общее число таких связей (сумма степеней по малым городам) равно \( 3M \). Это число должно быть чётным, потому что дороги считаются дважды (один раз для каждого города, который они соединяют). Следовательно, \( M \) должно быть чётно.

Аналогично, \( 3B \) – число дорог, связывающих большие города. Это число должно быть чётно. Следовательно, \( B \) должно быть чётно.

Итак, \( M \) и \( B \) – чётные числа. Пусть \( M = 2k \) и \( B = 2j \).

По условию \( M = B \), поэтому \( 2k = 2j \), то есть \( k = j \).

Общее число городов \( N = M + B = 2k + 2k = 4k \).

Таким образом, общее число городов \( N \) делится на 4.

Доказано.