Lazy Box Sorting

Question

Vor Louis stehen 10 Kisten mit verschiedenen Lebensmitteln: Tomaten, (rote) Heringe und Bananen.

Die Boxen sind nebeneinander in einer Linie angeordnet. Direkt neben der letzten Box befinden sich drei größere Container, die diese Linie erweitern. Seine Aufgabe ist es, diese Kisten nach Lebensmitteln sortiert in die Behälter zu legen. Zu seiner Verfügung: ein Kran, der sich nur horizontal bewegen kann und jeweils eine Kiste aufnehmen und abstellen kann.

Louis will die Kisten so wenig wie möglich bewegen. Bevor er etwas unternimmt, zeichnet er seine Situation vereinfacht, um herauszufinden, wie man sie am besten auf Papier bringen kann.

Was ist mit dem vereinfachten Bild die kleinste Gesamtfahrstrecke, die alle Boxen zurücklegen, die er erreichen kann?

Answer 1

Die minimale Gesamtfahrstrecke beträgt:

100

Beweis:

Addition ist kommutativ - @Punintended . Jeder Gegenstand muss sich von seiner ursprünglichen Position zur ersten Stelle in den Behältern bewegen. Dann muss sich jeder Gegenstand von der ersten Stelle in den Behältern zur richtigen Stelle bewegen. Aus dieser Zerlegung geht hervor, dass es keine Rolle spielt, welche Banane zu welchem ​​Bananenfleck usw. geht. Um alle Gegenstände an den ersten Punkt zu bringen, ist es erforderlich 1+2+3+4+...+10 = 10 * 11/2 = 55. Um alle Gegenstände von der ersten Stelle an die richtige Stelle zu bringen, ist es nötig 0+1+2+3+...+9 = 9*10/2 = 45. Die zurückgelegte Gesamtstrecke beträgt 55+45 = 100.