UFPR 2014
A figura ao lado apresenta uma planificação do cubo que deverá ser pintada de acordo com as regras abaixo:
Os quadrados que possuem um lado em comum, nessa planificação, deverão ser pintados com cores diferentes. Além disso, ao se montar o cubo, as faces opostas deverão ter cores diferentes. De acordo com essas regras, qual o MENOR número de cores necessárias para se pintar o cubo, a partir da planificação
apresentada?
2.
3.
4.
5.
6.
Resolução
Conveniente nomear os seis quadrados da planificação (figura):
- formando uma fileira horizontal de quatro quadrados, da esquerda para a direita: A, B, C e D;
- o quadrado que fica sobre B: E;
- o quadrado que fica sob C: F.
1. Quais lados tocam-se na planificação?
A linha horizontal garante os contatos A-B, B-C e C-D; além disso, E toca B e F toca C.
2. Quais pares serão faces opostas quando o cubo for montado?
A montagem transforma:
- A e C em faces opostas,
- B e D em faces opostas,
- E e F em faces opostas.
Portanto, além dos contatos da planificação, os pares (A,C), (B,D) e (E,F) também não podem receber a mesma cor.
3. Tentativa com 2 cores
Se existissem apenas duas cores (digamos, Vermelha e Azul), os quadrados consecutivos A-B-C-D obrigatoriamente teriam de alternar as cores para satisfazer o primeiro critério (lados comuns diferentes):
A (V), B (A), C (V), D (A)
Nesse arranjo, A e C ficariam com a mesma cor, assim como B e D, violando a regra das faces opostas. Logo 2 cores são insuficientes.
4. Construindo uma coloração com 3 cores
Utilizemos três cores: 1, 2 e 3.
- Atribua 1 a A.
- Como A e B são vizinhas, B recebe 2.
- C é vizinha de B, então recebe 3.
- D é vizinha de C, portanto recebe 1 (diferente de C e de B). Note que B(2) e D(1) agora são opostas e já estão com cores distintas.
- E é vizinha apenas de B(2); pode receber 3.
- F é vizinha apenas de C(3); para ser diferente de C e também de sua oposta E(3), recebe 2.
Conferindo:
- Lados vizinhos na planificação têm cores diferentes.
- Pares opostos: A(1) ≠ C(3); B(2) ≠ D(1); E(3) ≠ F(2).
Todas as exigências são satisfeitas usando apenas 3 cores. Como já vimos que 2 cores não bastam, concluímos que 3 é o menor número possível.
Resposta: B (3 cores).
Dicas
Erros Comuns
Planificação do cubo: representação em 2D das seis faces de um cubo, onde arestas comuns indicam contato direto no sólido.
Faces opostas: pares de faces que não compartilham aresta alguma no cubo; no processo de montagem, duas faces de uma fileira de quatro formam um par oposto e o quadrado de cima fica oposto ao de baixo.
Coloração de grafos: problema de atribuir cores a vértices (faces) de tal forma que vértices ligados por uma aresta (faces que não podem repetir cor) recebam cores diferentes. O número mínimo de cores é denominado número cromático.
No exercício, cada restrição (lado comum na planificação ou par de faces opostas) equivale a uma aresta do grafo.
