Matemática e suas Tecnologias Question #019e5c02

A logomarca é composta por $5$ regiões (mãos) que devem ser coloridas com $4$ cores (verde, amarelo, azul, branco), de modo que regiões vizinhas (que se tocam) tenham cores diferentes. A figura é um grafo planar: as $5$ regiões estão dispostas em um pentágono, onde cada região é vizinha de duas outras (exceto a central, que é vizinha de todas). Na verdade, a logomarca tem $5$ regiões: $4$ mãos laterais e $1$ central (a taça). As $4$ mãos laterais formam um ciclo, e a região central é vizinha de todas as laterais. Portanto, o problema é colorir um grafo com $5$ vértices, onde o vértice central é adjacente a todos os outros, e os vértices laterais formam um ciclo. Usando o princípio fundamental da contagem: primeiro, pinte a região central: $4$ opções. Em seguida, pinte as regiões laterais em ordem, cada uma não podendo usar a cor da central nem a cor da vizinha anterior. Para a primeira lateral: $3$ opções (qualquer cor exceto a central). Para a segunda lateral: não pode ser a cor da central nem a cor da primeira lateral, então $2$ opções. Para a terceira lateral: não pode ser a cor da central nem a cor da segunda lateral, então $2$ opções. Para a quarta lateral: não pode ser a cor da central nem a cor da terceira lateral, mas também não pode ser igual à primeira lateral (pois são vizinhas? Na verdade, a quarta lateral é vizinha da terceira e da primeira? No ciclo, a quarta lateral é vizinha da terceira e da primeira? Sim, em um ciclo de $4$ vértices, o quarto é vizinho do terceiro e do primeiro. Então, ao pintar a quarta lateral, ela não pode usar a cor da central, nem a cor da terceira lateral, e também não pode usar a cor da primeira lateral (se a primeira e a quarta forem vizinhas). Portanto, o número de opções para a quarta lateral depende das cores escolhidas. Vamos calcular corretamente: Após pintar a central ($4$ opções), pinte as laterais em ordem: $L_1,L_2,L_3,L_4$. $L_1$: $3$ opções. $L_2$: não pode ser cor central nem cor $L_1$, então $2$ opções. $L_3$: não pode ser cor central nem cor $L_2$, então $2$ opções. $L_4$: não pode ser cor central, nem cor $L_3$, e também não pode ser cor $L_1$ (pois $L_4$ é vizinha de $L_1$). Então, se $L_1$ e $L_3$ forem iguais, então $L_4$ não pode ser igual a duas cores (central e $L_1$/$L_3$), restando $2$ opções. Se $L_1$ e $L_3$ forem diferentes, $L_4$ não pode ser igual a três cores (central, $L_1$, $L_3$), restando $1$ opção. Precisamos contar os casos. Vamos usar o princípio da multiplicação com cuidado: Número total de colorações = $4\cdot (\text{nuˊmero de maneiras de colorir o ciclo de }4\text{ veˊrtices com }3\text{ cores (excluindo a central) de modo que veˊrtices adjacentes tenham cores diferentes})$. O número de colorações de um ciclo de $4$ vértices com $3$ cores é: $3\cdot 2\cdot 2\cdot (\text{nuˊmero de opc¸o˜es para o uˊltimo})$. Para um ciclo de $n$ vértices com $k$ cores, a fórmula é $(k-1{)}^n+(-1{)}^n\cdot (k-1)$. Para $n=4$, $k=3$: $2^4+(-1{)}^4\cdot 2=16+2=18$. Portanto, $\text{total}=4\cdot 18=72$? Mas o gabarito é $972$, que é $4\cdot 243$? $243=3^5$? Na verdade, $972=4\cdot 243=4\cdot 3^5$? $3^5=243$, então $4\cdot 243=972$. Isso sugere que cada uma das $5$ regiões tem $3$ opções? Mas a central tem $4$ opções, e as laterais têm $3$ opções cada? Isso daria $4\cdot 3^4=4\cdot 81=324$, não $972$. $972=4\cdot 3^5$? $3^5=243$, $4\cdot 243=972$, então parece que são $5$ regiões com $3$ opções cada? Isso não faz sentido. Outra possibilidade: $972=4\cdot 3^5$? $3^5=243$, $4\cdot 243=972$, mas $3^5$ significa $5$ regiões com $3$ opções, mas a central tem $4$. Talvez a interpretação seja que a logomarca tem $6$ regiões? Vamos revisar a imagem: a logomarca da Copa 2014 tem $5$ mãos? Na verdade, a logomarca é composta por $5$ mãos estilizadas que formam a taça. Mas há também o fundo? O enunciado diz: "regiões vizinhas tenham cores diferentes". A logomarca tem $5$ regiões (as mãos) e o fundo? Normalmente, a logomarca é uma figura plana com $5$ mãos coloridas, e o fundo é branco? Mas o branco é uma das cores. Então, talvez sejam $5$ regiões (as mãos) e o fundo também conta como região? Se o fundo for considerado, seriam $6$ regiões. Mas o enunciado diz "pintar a logomarca", e a logomarca é a figura, não o fundo. Provavelmente são $5$ regiões. Vamos calcular novamente: Se a logomarca tem $5$ regiões, todas vizinhas entre si? Não, as mãos laterais são vizinhas apenas das adjacentes e da central. O grafo é um pentágono com um vértice central conectado a todos. Esse grafo tem $5$ vértices. O número de colorações com $4$ cores, vértices adjacentes diferentes, é dado pelo polinômio cromático. Para um grafo com $5$ vértices onde um vértice central é adjacente a todos os outros e os outros formam um ciclo, o polinômio cromático é: $k\cdot (k-1)\cdot ((k-2{)}^3+(k-2{)}^2-(k-2))$? Vamos calcular diretamente: Escolha a cor do vértice central: $4$ opções. Restam $3$ cores para os $4$ vértices do ciclo. O número de colorações de um ciclo de $4$ vértices com $3$ cores é $18$, como calculado. $\text{Total}=4\cdot 18=72$. Mas $72$ não está entre as opções. As opções são $15$, $30$, $108$, $360$, $972$. $108=4\cdot 27$, $27=3^3$. $360=4\cdot 90$. $972=4\cdot 243$. Nenhum é $72$. Portanto, a logomarca deve ter mais regiões. Provavelmente, a logomarca tem $6$ regiões: $5$ mãos e o centro? Ou $5$ mãos e o fundo? Vamos supor que a logomarca seja composta por $5$ mãos que se tocam, formando uma estrela? Na verdade, a logomarca da Copa 2014 tem $5$ mãos que se unem, e cada mão é uma região, e há uma região central onde as mãos se encontram? Ou as mãos são apenas $5$, e cada uma é vizinha de duas outras? Se forem $5$ mãos em um ciclo, sem região central, então o grafo é um ciclo de $5$ vértices. O número de colorações de um ciclo de $5$ vértices com $4$ cores é: $(4-1{)}^5+(-1{)}^5\cdot (4-1)=3^5-3=243-3=240$. $240$ não está nas opções. Se forem $5$ mãos em um ciclo, mas com a restrição de que todas as cores devem ser usadas? O enunciado diz "utilizar todas as cores da bandeira nacional", ou seja, as $4$ cores devem ser usadas. Isso é uma restrição adicional. No ciclo de $5$ vértices com $4$ cores, o número de colorações que usam todas as $4$ cores é: total de colorações ($240$) menos aquelas que usam apenas $3$ cores, etc. Vamos calcular: Número de colorações de um ciclo de $5$ vértices com exatamente $4$ cores. Primeiro, escolha $4$ cores dentre $4$: $1$ maneira. Depois, colorir o ciclo com essas $4$ cores, usando todas. O número de colorações de um ciclo de $5$ vértices com $4$ cores, usando todas, é: $4!\cdot S(5,4)$ onde $S$ são números de Stirling? Ou podemos calcular: total de colorações com $4$ cores $=240$. Coloracoes com no máximo $3$ cores: escolha $3$ cores dentre $4$: $4$ maneiras. Coloracoes de ciclo de $5$ com $3$ cores: $(3-1{)}^5+(-1{)}^5\cdot (3-1)=2^5-2=32-2=30$. Então colorações com exatamente $3$ cores: $4\cdot 30=120$. Mas isso inclui colorações que usam apenas $2$ ou $1$ cor? Na verdade, $30$ é o número de colorações com $3$ cores específicas, mas pode incluir colorações que usam apenas $2$ cores? Sim, porque o ciclo de $5$ com $3$ cores pode usar apenas $2$ cores. Precisamos usar inclusão-exclusão. Melhor: número de colorações de ciclo de $5$ com $4$ cores que usam todas as $4$ cores = total - colorações que usam no máximo $3$ cores. Colorações que usam no máximo $3$ cores: escolha $3$ cores dentre $4$: $4$ maneiras. Para cada conjunto de $3