Questão 2 Unifesp 2º dia - Elite Colégio e Pré-Vestibular

Questão 2

Permutação Simples e com Reptição

A figura representa três ruas paralelas na vertical, cruzadas por quatro ruas paralelas na horizontal. Os veículos só podem percorrer essas ruas, e no sentido das setas.

Um taxista decide ir de $P$ para $Q$ por uma das duas regras a seguir:

I. menor caminho que liga os pontos $P$ e $Q$ ;

II. menor caminho que liga os pontos $P$ e $Q$ sem que percorra três quarteirões contíguos na mesma rua. Por exemplo, a situação a seguir não é permitida:

a) Calcule o total de caminhos possíveis pela regra I e o total de caminhos possíveis pela regra II.

b) Considere agora cinco ruas paralelas na vertical, cruzadas por seis ruas paralelas na horizontal, com o sentido de trânsito das ruas indicado pelas setas, conforme representado pela figura.

Calcule o total de caminhos possíveis para ir de $P$ até $Q$ pelo menor caminho em que haja, no percurso total, uma sequência de 4 quarteirões contíguos em uma mesma rua na vertical, mas não 5.

Resolução

a) Em qualquer caminho de menor comprimento possível de $P$ até $Q$ , o taxista terá que fazer três deslocamentos na vertical $(V)$ e dois deslocamentos na horizontal $(H)$ .

Então, o total de caminhos possíveis pela regra I corresponde ao total de permutações de $V V V H H$ :

$P_{5}^{3, 2} = \frac{5!}{3! \cdot 2!} = 10 caminhos$

Já os caminhos possíveis pela regra II são aqueles que satisfazem a regra I, porém, não apresentam três $V' s$ seguidos em sua codificação. Assim, das $10$ possibilidades da regra I, devemos excluir os casos

$V V V H H$ , $H V V V H$ e $H H V V V$ ,

totalizando assim $10 - 3 = 7$ caminhos possíveis pela regra II.

b) Mantendo a notação do item (a), as possibilidades de caminhos de $P$ até $Q$ são as permutações de $V V V V V H H H H$ (cinco verticais e 4 horizontais). Desejamos contabilizar aqueles caminhos que possuem quatro $V' s$ consecutivos, porém, não possuem cinco $V' s$ consecutivos.

Fixamos primeiramente quatro $V' s$ juntos em uma caixinha, e contabilizamos as possibilidades de permutar os elementos:

$\underset{P_{e x t}}{\underset{⏟}{V V V V V L L L L}} \to P_{e x t} = P_{6}^{4} = \frac{6!}{4!} = 30 possibilidades$

Dessas possibilidades devemos descontar aqueles nas quais a caixinha com os $V' s$ e o outro $V$ ficaram lado a lado:

$\underset{P_{e x t}}{\underset{⏟}{\overset{P_{i n t}}{\overset{⏞}{(V V V V V)}} L L L L}} \to P_{e x t} \cdot P_{i n t} = P_{5}^{4} \cdot P_{2} = \frac{5!}{4!} \cdot 2! = 10 possibilidades$

Portanto, o total de possibilidades havendo sequência de 4 quarteirões contíguos em uma mesma rua na vertical, mas não 5, é de

$30 - 10 = 20 possibilidades$