|
|
 |
Условие
В стране 2000 городов. Каждый город связан беспосадочными двусторонними авиалиниями с некоторыми другими городами, причём для каждого города число исходящих из него авиалиний есть степень двойки (то есть 1, 2, 4, 8, ...). Для каждого города A статистик подсчитал количество маршрутов, имеющих не более одной пересадки, связывающих A с другими городами, а затем просуммировал полученные результаты по всем 2000 городам. У него получилось 100000. Докажите, что статистик ошибся.
Решение
Назовём беспосадочный перелёт из одного города в другой коротким маршрутом, а перелёт из одного города в другой с одной пересадкой в пути длинным маршрутом.
Перенумеруем города и обозначим через 2ni (i = 1, ..., 2000) число рейсов, выходящих из i-го города.
Будем учитывать короткие маршруты в их конечных пунктах, а длинные – в пунктах пересадки. Тогда, если из города выходит x авиалиний, то в нём будет учтено x коротких маршрутов и x(x – 1) длинных (так как из каждого смежного города через данный проходит x – 1 длинных маршрутов), а всего – x + x(x – 1) = x² маршрутов. Таким образом, общее число маршрутов равно 22n1 + ... + 22n2000 = 4n1 + ... + 4n2000.
Поскольку 4 в любой степени при делении на 3 дает остаток 1, то остаток от деления на 3 у общего числа маршрутов такой же, как у числа 2000, то есть 2, а у числа 100000 этот остаток равен 1.
