---

Показать решение

---

Скрыть решение

Решение

  Первый случай. Докажем сначала, что от перестановки порядка двух последовательных поездок стоимость перевозки не изменится. Иными словами, пусть автомобиль посетил некоторый населенный пункт M, а потом — населенный пункт N. Покажем, что если бы он сначала поехал в N, а потом — в M, то стоимость была бы той же самой.

Пусть расстояния до M и N равны m и n соответственно. Тогда веса соответствующих грузов — тоже m и n. Стоимость перевозки остальных грузов не меняется от перестановки поездок в M и N. Стоимость перевозок грузов m и n в города, отличные от M и N, тоже не изменится. Вычислим стоимость перевозки грузов m и n в города M и N. В первом случае эта стоимость равна (m + n)m + nm + n²: первое слагаемое соответствует поездке в пункт M, второе -- поездке обратно в город, третье — поездке в N.

Аналогично, стоимость перевозки грузов m и n во втором случае равна (m + n)n + mn + m². Нетрудно видеть, что эти стоимости равны. Утверждение доказано.

Пусть есть два разных порядка объезда населенных пунктов. Первый порядок можно превратить во второй, переставляя последовательные поездки. Это утверждение нетрудно доказать индукцией по числу городов. Заметим, что оно очень важно в теории перестановок, см. [#!____________!#], гл. 2. По доказанному, при каждой такой перестановке общая стоимость перевозки не меняется, значит, она не зависит от порядка объезда населенных пунктов.

Второй случай. Занумеруем грузы a₁, a₂,..., a_n в том порядке, в каком их развозят, тогда стоимость перевозки равна

Получилось выражение, которое не зависит от порядка нумерации грузов.