4
NIVEL
17. Cada um dos círculos desenhados no quadro deve ser pintado de azul, verde ou preto de modo que círculos ligados por um segmento tenham cores diferentes. De quantas maneiras podemos fazer essa pintura?
(A) 27
(B) 8
(C) 24
(D) 18
(E) 12

Question

Accepted Answer

**Resposta: (C) 24**

Para resolver o problema, podemos usar o conceito de coloração de grafos. O problema pode ser representado como um grafo onde cada círculo é um vértice e cada segmento que liga dois círculos é uma aresta. A condição é que vértices adjacentes (ligados por uma aresta) tenham cores diferentes.

Vamos considerar que temos $ n $ círculos (vértices) e $ m $ segmentos (arestas). No entanto, a quantidade exata de círculos e segmentos não foi dada, mas sabemos que queremos colorir cada círculo com uma das três cores disponíveis (azul, verde ou preto) de tal forma que círculos ligados por segmentos tenham cores diferentes.

Uma maneira de abordar isso é considerando que se tivermos um ciclo de comprimento par, podemos pintar alternadamente com duas cores. No entanto, como temos três cores disponíveis, podemos sempre garantir que há uma terceira cor disponível para evitar conflitos.

Para simplificar a explicação, suponha que os círculos formam um grafo bipartido (o que é comum em muitos problemas desse tipo). Em um grafo bipartido, podemos dividir os vértices em dois conjuntos disjuntos $ V_1 $ e $ V_2 $ de modo que todas as arestas conectem um vértice de $ V_1 $ a um vértice de $ V_2 $.

Para colorir:
1. Escolhemos uma cor para um vértice inicial.
2. O vértice adjacente deve ser de uma cor diferente.
3. Continuamos este processo garantindo que cada vértice tenha uma cor diferente dos seus vizinhos.

Como temos três cores e cada vértice tem duas opções de cores (diferentes da cor do vértice adjacente), a contagem final das maneiras de colorir depende da estrutura específica do grafo, mas uma solução geral para um grafo bipartido com três cores é dada por:

$$ 3 \times 2^{n-1} $$

No caso de quatro vértices, temos:

$$ 3 \times 2^{4-1} = 3 \times 8 = 24 $$

Portanto, o número total de maneiras de pintar os círculos de acordo com as regras dadas é **24**.

4 NIVEL 17. Cada um dos círculos desenhados no quadro deve s...

4 NIVEL 17. Cada um dos círculos desenhados no quadro deve ser pintado de azul, verde ou preto de modo que círculos ligados por um segmento tenham cores diferentes. De quantas maneiras podemos fazer essa pintura? (A) 27 (B) 8 (C) 24 (D) 18 (E) 12

Ask a question and receive an answer instantly