Questão 2
(ITA - 2024)
Quatro cidades A, B, C e D estão ligadas por seis pontes distintas da seguinte maneira:
– uma ponte liga A e B;
– uma ponte liga A e C;
– uma ponte liga B e C;
– duas pontes ligam B e D;
– uma ponte liga C e D.
Quantos caminhos são possíveis ligando todas as cidades e passando por todas as pontes uma única vez, sabendo que é permitido passar em uma mesma cidade mais de uma vez?
Gabarito:
Resolução:
Para facilitar a resolução, itemos desenhar as pontes conforme abaixo:
1, 2,3,4,5 e 6 são as pontes , e temos que os caminhos que passam pelas 6 pontes uma única vez é dada por:
Saindo de 1
123456
125436
125634
Saindo de 3
321456
354126
356412
Saindo de 4
412563
452136
453126
435621
Saindo de 5
521364
521463
531264
534621
564123
564321
Portanto, temos 16 caminhos. Mas veja que existem 2 pontes que ligam B e D, o número de caminhos será multiplicado por 2, referentes à escolha da ponte (6 e 5 ou 5 e 6). Logo:
O total de caminhos é igual a 16 . 2 = 32 caminhos.