Разделы 
Дополнительно
Задача по математике - 1585
2019-01-19 
В стране 2000 городов. Каждый город связан беспосадочными двусторонними авиалиниями с некоторыми другими городами, причем для каждого города число исходящих из него авиалиний есть степень двойки (т. е. 1, 2, 4, 8,\cdots). Для каждого города $A$ статистик подсчитал количество маршрутов, имеющих не более одной пересадки, связывающих $A$ с другими городами, а затем просуммировал полученные результаты по всем 2000 городам. У него получилось 100000. Докажите, что статистик ошибся.
Решение:
Назовем беспосадочный перелет из одного города в другой «коротким маршрутом», а перелет из одного города в другой с одной пересадкой в пути длинным маршрутом . Перенумеруем города и обозначим через $2^{n_i} (i = 1,\cdots, 2000)$ число рейсов, выходящих из $i$-го города. Будем учитывать короткие маршруты в их конечных пунктах, а длинные - в пунктах пересадки. Тогда, если из города выходит $x$ авиалиний, то в нем будет учтено x коротких маршрутов и $x(x - 1)$ длинных (так как из каждого смежного города через данный проходит $x - 1$ длинных маршрутов), а всего - $x + x(x - 1) = x^2$ маршрутов. Таким образом, общее число маршрутов равно $2^{2n_1} + \cdots + 2^{2n_2000} = 4^{n_i} + \cdots + 4^{n_2000}$. Поскольку четверка в любой степени при делении на 3 дает остаток 1, то остаток от деления на 3 у общего числа маршрутов такой же, как у числа 2000, т. е. 2, а у числа 100000 этот остаток равен 1.
В стране 2000 городов. Каждый город связан беспосадочными двусторонними авиалиниями с некоторыми другими городами, причем для каждого города число исходящих из него авиалиний есть степень двойки (т. е. 1, 2, 4, 8,\cdots). Для каждого города $A$ статистик подсчитал количество маршрутов, имеющих не более одной пересадки, связывающих $A$ с другими городами, а затем просуммировал полученные результаты по всем 2000 городам. У него получилось 100000. Докажите, что статистик ошибся.
Решение:
Назовем беспосадочный перелет из одного города в другой «коротким маршрутом», а перелет из одного города в другой с одной пересадкой в пути длинным маршрутом . Перенумеруем города и обозначим через $2^{n_i} (i = 1,\cdots, 2000)$ число рейсов, выходящих из $i$-го города. Будем учитывать короткие маршруты в их конечных пунктах, а длинные - в пунктах пересадки. Тогда, если из города выходит $x$ авиалиний, то в нем будет учтено x коротких маршрутов и $x(x - 1)$ длинных (так как из каждого смежного города через данный проходит $x - 1$ длинных маршрутов), а всего - $x + x(x - 1) = x^2$ маршрутов. Таким образом, общее число маршрутов равно $2^{2n_1} + \cdots + 2^{2n_2000} = 4^{n_i} + \cdots + 4^{n_2000}$. Поскольку четверка в любой степени при делении на 3 дает остаток 1, то остаток от деления на 3 у общего числа маршрутов такой же, как у числа 2000, т. е. 2, а у числа 100000 этот остаток равен 1.
