(ESPM) Analise combinatória

Página 2 de 2 Anterior  1, 2

Ir em baixo

(ESPM) Analise combinatória

Mensagem por guipenteado em Qua 29 Ago 2018, 17:50

Relembrando a primeira mensagem :

Os 7 países do mapa abaixo devem ser coloridos com 4 cores distintas, de modo que os fronteiriços devem ter cores diferentes, e os países A e D, a mesma cor. O número de maneiras distintas de se efetuar esse trabalho é igual a:


a)48
b)72
c)80
d)96
e)120


Alguém consegue me ajudar ?
avatar
guipenteado
Jedi
Jedi

Mensagens : 274
Data de inscrição : 02/03/2016
Idade : 21
Localização : paranavai

Voltar ao Topo Ir em baixo


Re: (ESPM) Analise combinatória

Mensagem por Emanoel Jorge em Ter 04 Set 2018, 15:05

Para E = B

A = 4
B = 3
C = 2
D = 1
E = 1
F = 1
G = 2 ---> Total = 48

agora so esqueceu que E=B e (F) so esta em fronteira com E,B,D
como E=B e D #B resta duas cores para F

Emanoel Jorge
Padawan
Padawan

Mensagens : 98
Data de inscrição : 28/06/2017
Idade : 19
Localização : Maranhão,Brasil

Voltar ao Topo Ir em baixo

Re: (ESPM) Analise combinatória

Mensagem por Elcioschin em Ter 04 Set 2018, 18:12

Correto

Neste caso, para E = B --> 96 possibilidades

Total Geral = 498 + 96 = 144
avatar
Elcioschin
Grande Mestre
Grande Mestre

Mensagens : 47181
Data de inscrição : 15/09/2009
Idade : 72
Localização : Santos/SP

Voltar ao Topo Ir em baixo

Re: (ESPM) Analise combinatória

Mensagem por pesadelocombinatorio em Ter 30 Out 2018, 20:11

É possível encontrar o valor que consta no gabarito (120), mas o enunciado está muito mal redigido. Existem dois problemas com ele:

Primeiro: é impossível usar uma cor diferente para cada vizinho porque só existem 4 cores disponíveis e 3 dos países (D, E e F) fazem fronteira com 4 outros. Assim, deve se considerar que E e/ou F podem ser da mesma cor de D.

Segundo: o examinador esqueceu de mencionar que ele queria o número de combinações utilizando o menor número possível de cores repetidas entre vizinhos. Voltando ao primeiro ponto, é inevitável que E ou F repitam a cor de D, mas é possível que F seja diferente de todos os seus vizinhos quando D e E são da mesma cor.

Com isso em mente, é possível começar a resolver o exercício.

A análise começa de forma simples: o País A pode ter qualquer uma das 4 cores; o País B pode ter qualquer uma das 3 restantes; o País C pode ter qualquer uma entre as 2 restantes; e o País D só pode ter a cor do País A. Até agora temos:

4*3*2*1

O caso do País E se divide em 2: E pode ter a mesma cor de B; ou E pode ter uma cor diferente de B.

No primeiro caso, a única possibilidade de cor para E é a mesma de B, enquanto que para F temos 2 possibilidades (lembrando que este deve ser diferente tanto de E (e B) quanto de D). O País G sempre poderá ser pintado de uma das duas cores não utilizadas por seus vizinhos. Dessa forma, temos:

4*3*2*1*1*2*2 = 96

No segundo caso, E tem cor diferente tanto de B (conforme estabelecemos) como de C, que é seu vizinho. Assim, o País E pode ter qualquer uma das duas cores restantes. Agora os 3 vizinhos a oeste de F possuirão cores diferentes. Logo, só existe uma possibilidade de cor para F. G continua tendo duas possibilidades. Em termos matemáticos, temos:

4*3*2*1*2*1*1 = 96

Se somarmos os valores obtidos em ambos os cenários, iremos obter o número total de combinações: 96+96 = 192

Agora precisamos calcular quantas dessas 192 combinações só utilizam 3 cores, já que o enunciado especifica que só quer combinações de 4 cores.

Utilizamos aqui o mesmo raciocínio empregado acima, mas removendo uma cor do nosso repertório. Primeiro removemos qualquer uma das 4 cores e teremos (de A até D):

3*2*1*1

Para o caso de B = E:

3*2*1*1*2*1*1 = 12

Lembrando que G só pode ter uma cor já que seus vizinhos tomaram as outras 2 disponíveis.

E para B diferente de E:

3*2*1*1*2*1*1 = 6

Novamente somamos os dois casos: 12+6 = 18

Por fim, falta permutar essas 18 combinações pelas cores que podemos remover. Por exemplo, se no caso acima removemos a cor H, ainda é possível repetir o procedimento removendo I,J e K. Então, o número total de combinações que utilizam apenas 3 cores é:

4*18 = 72

E finalmente conseguimos chegar ao nosso resultado subtraindo 72 do número total de combinações possíveis:

192 - 72 = 120

Espero que tenha sido claro o suficiente. Esse é um exercício bem chato de resolver.

pesadelocombinatorio
iniciante

Mensagens : 1
Data de inscrição : 30/10/2018
Idade : 28
Localização : brasil

Voltar ao Topo Ir em baixo

Re: (ESPM) Analise combinatória

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Voltar ao Topo Ir em baixo

Página 2 de 2 Anterior  1, 2

Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum