Ленивая сортировка ящиков

Question

Перед Луи есть 10 коробок с разными продуктами: помидоры, (красная) сельдь и бананы.

Ящики расположены бок о бок в линию. Рядом с последним ящиком находятся три больших контейнера, продолжающих эту линию. Его работа - складывать эти коробки в контейнеры, отсортированные по продуктам. В его распоряжении: подъемный кран, который может двигаться только горизонтально и может поднимать и опускать по одному ящику за раз.

Луи хочет немного сдвинуть коробки. Прежде чем что-либо сделать, он делает упрощенный рисунок своей ситуации, чтобы выяснить, как лучше всего переместить их на бумаге.

Используя упрощенную картинку, какое наименьшее общее расстояние, которое могут преодолеть все коробки,?

Answer 1

Общее минимальное расстояние перемещения составляет:

100

Доказательство:

Сложение коммутативное - @Punintended . Каждый предмет должен переместиться из исходного положения на первое место в контейнерах. Затем каждый предмет должен переместиться с первого места в контейнерах на правильное место. Из этого разложения мы видим, что не имеет значения, какой банан попадает в какое место банана и т. Д. Чтобы переместить все предметы на первое место, требуется 1+2+3+4+...+10 = 10 * 11/2 = 55. Чтобы переместить каждый предмет с первого места на правильное, требуется 0+1+2+3+...+9 = 9*10/2 = 45. Общее пройденное расстояние составляет 55+45 = 100.