ENEM 2010 — Matemática — Combinatória
João mora na cidade A e precisa visitar cinco clientes, localizados em cidades diferentes da sua. Cada trajeto possível pode ser representado por uma sequência de 7 letras. Por exemplo, o trajeto ABCDEFA, informa que ele sairá da cidade A, visitando as cidades B, C, D, E e F nesta ordem, voltando para a cidade A. Além disso, o número indicado entre as letras informa o custo do deslocamento entre as cidades. A figura mostra o custo de deslocamento entre cada uma das cidades.
Como João quer economizar, ele precisa determinar qual o trajeto de menor custo para visitar os cinco clientes. Examinando a figura, percebe que precisa considerar somente parte das sequências, pois os trajetos ABCDEFA e AFEDCBA têm o mesmo custo. Ele gasta 1min30s para examinar uma sequência e descartar sua simétrica, conforme apresentado.
O tempo mínimo necessário para João verificar todas as sequências possíveis no problema é de
Questões relacionadas
Matemática · Combinatória · OBMEP 2005
Pedrinho escreveu todos os números inteiros compreendidos entre 100 e 999 cuja soma dos algarismos é 12. Por exemplo, os
Matemática · Combinatória · OBMEP 2005
Os bilhetes de uma rifa são numerados de 1 000 a 9 999. Marcelo comprou todos os bilhetes nos quais o algarismo sete apa
Matemática · Combinatória · ENEM 2022
Uma montadora de automóveis divulgou que oferta a seus clientes mais de 1 000 configurações diferentes de carro, variand