Questão de quantas maneiras colorir..

De quantos modos podemos pintar (usando uma de quatro cores) as casas da
figura a baixo de modo que as casas vizinhas tenham cores diferentes?



Não entendi como essa solução funciona. A questão diz que devemos usar uma das quatro cores. Porém no primeiro caso há 2 cores iguais, possibilitando o uso de apenas mais 2 cores, e assim deixando uma de fora. Isso está certo?

Gabarito: 84 maneiras.

Caso I: casas opostas 1 e 3 tem a mesma cor

a) Existem 4 possibilidades para pintar a casa 1
b) Existe apenas 1 possibilidade para pintar a casa 3 (a mesma cor da casa 1)
c) Existem 3 possibilidades para pintar a casa 2 (não pode ser igual a das casas 1 e 3)
d) Existem 3 possibilidades para pintar a casa 4 (não pode ser igual a das casas 1 e 3

Subtotal ---> 4.1.3.3 = 36

Caso II ---> as casas 1 e 3 tem cores diferentes

a) Existem 4 possibilidades para pintar a casa 1
b) Existem 3 possibilidades para pintar a casa 2 (não pode ser igual a da casa 1)
c) Existem 2 possibilidades para pintar a casa 3 (não pode ser igual a das casas 1 e 2)
d) Existem 2 possibilidades para pintar a casa 4 (não pode ser igual a das casas 1 e 3)

Subtotal = 4.3.2.2 = 48

Total geral = 36 + 48 = 84

Olá, Luiz. Essa solução do Élcio é muito boa, mas vou deixar uma outra aqui.

Veja que há 4 modos de pintar a casa representada por 1,  3 modos de pintar a casa representada por 2  (não podemos usar a mesma cor que foi usada na primeira casa), 3 modos de pintar a casa representada por 3 (não podemos usar a mesma cor que foi usada na segunda casa) e 3 modos de pintar a casa representada por 4 (não podemos usar a mesma cor que foi usada na terceira, nem a mesma cor que foi usada na primeira, mas vamos ignorar esta última condição). A resposta, nesse caso, seria 4 \times 3^3 = 108, mas essa contagem considera, de forma errada, os casos em que casa 1 e a casa 4 possuem a mesma cor. Esses casos são em número de 4 \times  3 \times 2 = 24, uma vez que há 4 modos de pintar a casa 1 (que automaticamente possuirá a mesma cor que a casa 4), 3 modos de pintar a casa 2 e 2 modos de pintar a casa 3.

A resposta é 4 \times 3^3 - 4 \times  3 \times 2 = 84

Mateus. Não entendi a parte em que as casas 1 e 4 possuem a mesma cor. Tentei procurar alguns exemplos com as cores iguais nas casas 1 e 4 mas sem sucesso.
Poderia me demonstrar algum exemplo?

Grato pela ajuda!

Aí que tá. Essas duas casas não podem ter a mesma cor, e é por esse motivo que eu tenho que retirar alguns casos (24). Na minha primeira contagem, eu estabeleci que as casas 3 e 4 possuem obrigatoriamente cores diferentes, mas não garanti que as casas 1 e 4 também possuam cores diferentes, daí tive que retirar esses casos.

Muito obrigado pela ajuda, Mateus. Levei um tempo para entender que em algumas situações a casa 4 tem 3 possibilidades e outras situações ela tem 2. Quero agradecer também o Elcioschin, a parte  "b) Existe apenas 1 possibilidade para pintar a casa 3 (a mesma cor da casa 1)" me ajudou a entender a solução do material do print!