Mostrando postagens com marcador Análise combinatória. Mostrar todas as postagens
Mostrando postagens com marcador Análise combinatória. Mostrar todas as postagens

Exercício Resolvido - Caminhos: Análise combinatória: Vestibular UERJ 2011

Cálculo do número de caminhos mínimos entre dois pontos

Uma rede é formada de triângulos equiláteros congruentes, conforme a representação abaixo.
Uma formiga se desloca do ponto A para o ponto B sobre os lados dos triângulos, percorrendo
X caminhos distintos, cujos comprimentos totais são todos iguais a d.

Sabendo que d corresponde ao menor valor possível para os comprimentos desses caminhos, X
equivale a:
(A) 20
(B) 15
(C) 12
(D) 10

Solução:
Para saber quantos caminhos de menor comprimento são possíveis, devemos percorrer, inicialmente, um dos menores caminhos. Seja ele o caminho partindo de A, andando 4 linhas na horizontal e 2 na diagonal até chegar em B:
Número de caminhos
Neste caso, podemos dizer que a formiga percorreu o caminho HHHHDD, já que foi quatro vezes para a esquerda na horizontal, e duas vezes para cima na direção diagonal.
Assim, para saber quantos caminho de comprimento igual a esse basta calcular o número de formas de combinar as quatro letras H e as duas D para formar "palavras" diferentes, ou seja, devemos calcular o número de anagramas possíveis de serem formados com HHHHDD.
Supondo que todas as seis letras sejam diferentes, podemos dizer que é possível "embaralhá-las" de K formas distintas, onde:

K = 6*5*4*3*2*1 = 6! = 720

Porém, temos quatro letras H e duas D. Com isso num mesmo anagrama ao trocarmos dois H's de lugar, o anagrama segue o mesmo. Por exemplo, seja a palavra HDHDHH. Ao trocar o último H com o primeiro H, a palavra continua sendo exatamente a mesma e como são quatro letras H's que temos, existem 4*3*2*1 = 4! combinações de H's possíveis para cada palavra. O mesmo com a letra D, que possui duas iguais, neste caso teremos 2*1 = 2! combinações. Assim, o número de caminhos diferentes será:

Neste caso são 15 caminhos de comprimento mínimo possíveis. Resposta (B)


Exercício resolvido - Análise combinatória

Uma livraria vai doar 15 livros iguais a 4 bibliotecas. Cada uma deve receber ao menos 2 livros. O número de modos que esses livros podem ser repartidos nessa doação é?

Solução:
Temos 4 bibliotecas.
Cada uma deve receber no mínimo 2 livros.
Mas a soma dos livros recebidos deve ser 15, assim:

Sejam as bibliotecas A, B, C e D
A quantidade de livros recebidos por cada uma delas, chamarei de A, B, C e D também.
Assim;
A + B + C + D = 15

Digamos que a gente tenha 15 bolinhas:

o o o o o o o o o o o o o o o

Assim, vou separá-las utilizando três barras, de forma aleatória:

o o | o o o o o o | o o o o o o | o

Como pode ser observado, são 18 símbolos, 3 "|" e 15 "o". Desta forma, basta fazer quantas combinações podemos fazer com estes símbolos:

$$ \frac{18!}{ (15! \times 3!) } \,  = \,  \frac{ 18 \times 17 \times 16 }{ 3 \times 2 \times 1 } \,  = \, 816 $$

Esta seria a resposta se não existisse a condição de que cada biblioteca deve receber pelo menos 2 livros.
Neste caso o exercício pode ser feito considerando-se que cada biblioteca já recebeu seus 2 livros mínimos, assim, restam 7 para serem distribuídos.

Portanto, temos agora:
o o | o o | o o o |

Esta combinação será:
$$ \frac{ 10! }{ (7! \times 3!) } \, = \, \frac{ 10 \times 9 \times 8}{ 3 \times 2 } \, = \, 120 $$

Para provar a resposta, vou colocar abaixo todas as formas de soma possíveis:
2 + 2 + 2 + 9 $ \rightarrow $ 4 formas (Perceba que poderia ser 9 + 2 + 2 + 2 ou, 2 + 9 + 2 + 2 ou, 2 + 2+ 9 + 2, ou seja, são 4 formas de combinar esses números)

2 + 2 + 3 + 8 $ \rightarrow $ 12 formas
2 + 2 + 4 + 7 $ \rightarrow $ 12 formas
2 + 2 + 5 + 6 $ \rightarrow $ 12 formas
2 + 3 + 3 + 7 $ \rightarrow $ 12 formas
2 + 3 + 4 + 6 $ \rightarrow $ 24 formas
2 + 3 + 5 + 5 $ \rightarrow $ 12 formas
2 + 4 + 4 + 5 $ \rightarrow $ 12 formas
3 + 3 + 3 + 6 $ \rightarrow $ 4 formas
3 + 3 + 4 + 5 $ \rightarrow $ 12 formas
3 + 4 + 4 + 4 $ \rightarrow $ 4 formas

Assim, 4 + 12 + 12 + 12 + 12 + 24 + 12 + 12 + 4 + 12 + 4 = 120