Classificação Lazy Box

Question

Na frente de Louis, há 10 caixas contendo alimentos diferentes: tomates, arenques (vermelhos) e bananas.

As caixas são dispostas lado a lado em uma linha. Ao lado da última caixa estão três contêineres maiores estendendo esta linha. Seu trabalho é colocar essas caixas nos recipientes, classificadas por alimentos. À sua disposição: um guindaste que só pode se mover horizontalmente e pode pegar e colocar uma caixa de cada vez.

Louis quer mover as caixas o menos possível. Antes de qualquer coisa, ele faz um desenho simplificado de sua situação, para descobrir a melhor forma de movê-la no papel.

Usando a imagem simplificada, qual é a menor distância geral de viagem coberta por todas as caixas que ele pode alcançar?

Answer 1

A distância geral mínima de viagem é:

100

Prova:

A adição é comutativa - @Punintended . Cada item precisa se mover de sua posição original para o primeiro local nos recipientes. Então, cada item precisa ser movido do primeiro local nos recipientes para seu local correto. Desta decomposição, vemos que não importa qual banana vai para qual ponto de banana, etc. Para mover todos os itens para o primeiro ponto, é preciso 1+2+3+4+...+10 = 10 * 11/2 = 55. Para mover todos os itens a partir do primeiro ponto ao seu local correto, leva 0+1+2+3+...+9 = 9*10/2 = 45. A distância total percorrida é 55+45 = 100.