17. (IME/10 - adaptado) Cada um dos quatro quadrados menores da figura acima é pintado aleatoriamente de verde, azul, amarelo ou vermelho. De quant...

Podemos resolver esse problema utilizando o Princípio da Inclusão-Exclusão (PIE). Primeiro, vamos calcular o número total de maneiras de colorir os quadrados, que é 4^4 = 256, já que cada quadrado pode ser pintado de 4 maneiras diferentes. Agora, vamos calcular o número de maneiras em que nenhum par de quadrados adjacentes é pintado da mesma cor. Existem 2 pares de quadrados adjacentes na figura, então podemos pintá-los de 4x3 = 12 maneiras diferentes (4 opções para o primeiro quadrado e 3 opções para o segundo). Para os outros dois quadrados, temos 3 opções cada um (já que não podem ser da mesma cor que o quadrado adjacente), então o número total de maneiras de colorir os quadrados sem que nenhum par de quadrados adjacentes seja pintado da mesma cor é 12x3x3 = 108. No entanto, essa contagem inclui algumas configurações mais de uma vez. Se ambos os pares de quadrados adjacentes tiverem a mesma cor, então contamos essas configurações duas vezes. Existem 4 maneiras de escolher a cor que será repetida nos dois pares de quadrados adjacentes, e 3 maneiras de escolher a cor dos outros dois quadrados. Portanto, o número de configurações que contamos duas vezes é 4x3 = 12. Usando o PIE, podemos calcular o número de maneiras em que pelo menos um par de quadrados adjacentes é pintado da mesma cor como: 256 - 108 + 12 = 160 Portanto, há 160 maneiras de colorir os quadrados de modo que ao menos dois quadrados, que possuam um lado em comum, sejam pintados da mesma cor.