Questão 17 (Nível 1) da OBMEP 2024

Question

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?

Desenho em um quadro com oito círculos conectados por segmentos: quatro círculos formam um quadrado central com suas arestas conectadas, e quatro círculos externos posicionados acima, abaixo, à esquerda e à direita, cada um conectado aos dois círculos adjacentes do quadrado central.

A
27
B
8
C
24
D
18
E
12

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 17 (Nível 1) da OBMEP 2024

Nível 1 · Matemática: Princípio fundamental da contagem

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?

Desenho em um quadro com oito círculos conectados por segmentos: quatro círculos formam um quadrado central com suas arestas conectadas, e quatro círculos externos posicionados acima, abaixo, à esquerda e à direita, cada um conectado aos dois círculos adjacentes do quadrado central.

A
27
B
8
C
24
D
18
E
12

Escolha uma alternativa para conferir o gabarito.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

Perceba que ao escolhermos as cores dos círculos dos vértices do quadrado, as cores dos outros círculos ficam completamente determinadas, pois só podem assumir a terceira cor que não aparece nos círculos ligados a elas. Temos 3 escolhas possíveis para a cor do círculo A e sobram 2 para a escolha da cor do círculo B.

[Figura: Esquema com quatro círculos formando um quadrado central com vértices rotulados A, B, C e D, e quatro círculos externos conectados a cada par de vértices adjacentes.]

Temos agora dois casos a considerar:

A e C possuem a mesma cor e assim podemos escolher a cor de D com como qualquer cor diferente de A. O total de pinturas com essa configuração é 3 \times 2 \times 2 = 12.

[Figura: 12 esquemas ilustrando todas as possíveis pinturas dos círculos no caso em que A e C possuem a mesma cor.]

A e C possuem cores diferentes. Como C não pode ter a cor de A, então só resta uma escolha para C. Uma vez que A e C possuem cores diferentes, resta apenas uma cor para D. Nesse caso, temos 3 \times 2 \times 1 = 6 escolhas.

[Figura: 6 esquemas ilustrando todas as possíveis pinturas dos círculos no caso em que A e C possuem cores diferentes.]

Portanto, há 12 + 6 = 18 colorações possíveis.

Ver como a OBMEP publicou

Publicada pela banca.

Gabarito nas outras versões da prova: versão 2, E; versão 3, A; versão 4, B; versão 5, C.

Resolução comentada

A figura tem um quadrado central com 4 círculos (vértices) e 4 círculos externos, cada um ligado aos dois vértices vizinhos do quadrado, formando um triângulo com a aresta do quadrado.

A ideia é contar primeiro as cores do quadrado central e depois, para cada círculo externo, ver quantas cores sobram.

Quadrado central. Chamando os vértices de P_1, P_2, P_3, P_4 em ordem, vértices vizinhos precisam ter cores diferentes, e há 3 cores.

P_1: 3 escolhas.
P_2: 2 escolhas (diferente de P_1).
P_3: diferente de P_2, 2 escolhas, podendo ser igual a P_1 ou não.

É mais fácil dividir em casos:

Se P_3 = P_1 (2 escolhas para P_3 restritas a 1): P_4 só precisa ser diferente de P_1, então tem 2 escolhas. Total: 3\cdot 2\cdot 1\cdot 2 = 12.
Se P_3 \neq P_1 (P_3 é a terceira cor, 1 escolha): P_4 deve ser diferente de P_3 e de P_1, então 1 escolha. Total: 3\cdot 2\cdot 1\cdot 1 = 6.

O quadrado pode ser pintado de 12+6=18 maneiras (confere: o número de colorações de um ciclo de 4 com 3 cores é (3-1)^4+(3-1)=18).

Círculos externos. Cada um está ligado a dois vértices vizinhos do quadrado, que têm cores diferentes. Logo, o círculo externo não pode usar essas duas cores e sobra exatamente 1 cor. São 4 círculos externos, cada um com 1 escolha.

Total: 18\cdot 1\cdot1\cdot1\cdot1 = 18.

Alternativa D.

Pegadinha: A alternativa C (24) engana quem faz 3\cdot2\cdot2\cdot2 no quadrado, esquecendo que o quarto vértice também é vizinho do primeiro.

Por que as outras alternativas estão erradas

AUsa 3^3 ou ignora a restrição de cores diferentes entre os vizinhos.
BNúmero pequeno demais, sem base na contagem do quadrado central.
CErra a contagem do quadrado, como 3\cdot2\cdot2\cdot2=24, sem exigir que o último vértice seja diferente do primeiro.
EConta só o caso em que P_3=P_1 (12 maneiras) e esquece o caso em que são diferentes.

Assuntos: Princípio fundamental da contagem, Lógica e raciocínio lógico.

Reportar erro na resolução

Ver como caiu na prova

Questão 17 no caderno Nível 1 da OBMEP 2024

Fonte: OBMEP 2024 · Nível 1. Prova oficial ↗

Numeração da versão 1. Nas outras versões: versão 2, questão 18versão 3, questão 15versão 4, questão 16versão 5, questão 17