Lazy Box Sorting

Question

Przed Louisem znajduje się 10 pudełek zawierających różne potrawy: pomidory, (czerwone) śledzie i banany.

Pudła są ułożone obok siebie w jednej linii. Tuż obok ostatniej skrzyni znajdują się trzy większe kontenery przedłużające tę linię. Jego zadaniem jest umieszczanie tych pudeł w pojemnikach posortowanych według żywności. Do jego dyspozycji: dźwig, który może poruszać się tylko w poziomie i może podnosić i odkładać pojedynczo pudełko na raz.

Louis chce trochę przesunąć pudełka, jak to możliwe. Zanim cokolwiek zrobi, tworzy uproszczony rysunek swojej sytuacji, aby znaleźć najlepszy sposób na przeniesienie ich na papier.

Używając uproszczonego obrazu, jaka jest najmniejsza całkowita odległość pokonana przez wszystkie pola, które może osiągnąć?

Answer 1

Całkowita minimalna odległość podróży to:

100

Dowód:

Dodawanie jest przemienne - @Punintended . Każdy przedmiot musi zostać przeniesiony z pierwotnej pozycji na pierwsze miejsce w pojemnikach. Następnie każdy przedmiot musi zostać przeniesiony z pierwszego miejsca w pojemnikach do właściwego miejsca. Z tego rozkładu widzimy, że nie ma znaczenia, który banan trafi do którego miejsca, itd. Aby przenieść wszystkie elementy do pierwszego miejsca, trzeba 1+2+3+4+...+10 = 10 * 11/2 = 55. Aby przenieść wszystkie elementy z pierwszego miejsca na właściwe miejsce, potrzeba 0+1+2+3+...+9 = 9*10/2 = 45. Całkowita przebyta odległość to 55+45 = 100.