Olimpíadas ⇒ (OBM - 2007) Análise Combinatória Tópico resolvido

[Z-BosoN]

Um quadrado [tex3]4 \times 4[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]4 \times 4[/tex3]

é dividido em [tex3]16[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]16[/tex3]

quadrados unitários. Cada um dos [tex3]25[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]25[/tex3]

vértices desses quadrados deve ser colorido de vermelho ou azul. Ache o número de colorações diferentes tais que cada quadrado unitário possua exatamente dois vértices vermelhos.

[petras]

Z-BosoN,

Vamos começar colorindo a primeira linha de vértices. Cada coloração dessa
linha é uma seqüência de letras “A” e “V”, por exemplo, A V V A V. Observe
que, uma vez colorida a primeira linha, se aparecerem duas letras consecutivas
iguais, o restante dos vértices do tabuleiro já estão determinados. De fato, ao
aparecer dois V’s consecutivos, os dois vértices imediatamente abaixo deles
deverão ser coloridos com dois A’s, os que estão mais abaixo deverão ter dois
V’s, e assim por diante. Isto completa a coloração dessas duas colunas. Dessa
forma, cada coluna vizinha também estará determinada, pois em cada retângulo
teremos três vértices previamente coloridos, o que obriga o quarto vértice a ter
sua cor determinada. Então, para cada seqüência de A’s e V’s na primeira linha
que contém pelo menos duas letras iguais consecutivas, há exatamente uma
maneira de colorir o tabuleiro. Como há 2⁵ – 2 = 30 de tais seqüências, contamos
30 colorações possíveis.

fig1.jpg (3.23 KiB) Exibido 545 vezes

Falta-nos analisar um segundo caso, em que não há duas letras consecutivas
iguais na primeira linha. Há duas possibilidades de seqüências: começando com
A ou começando com V.

fig2.jpg (2.1 KiB) Exibido 545 vezes

Para cada uma dessas seqüências, há duas maneiras de escolhermos a primeira
letra da segunda linha. Uma vez escolhida esta letra, a segunda linha inteira
também estará determinada. Para a primeira letra da terceira linha também há 2
possibilidades. Com este raciocínio, cada vez que escolhemos a primeira letra de
uma linha, determinamos a coloração desta linha. Logo, como há duas maneiras
de escolhermos a primeira letra de cada linha, há 2⁵ = 32 maneiras de colorirmos
o tabuleiro, neste segundo caso. Logo, o total de colorações é igual a 30 + 32 =62.

Observação: Veja que, no caso geral, para um quadrado n x n, o raciocínio é
análogo. No primeiro caso, teremos 2^{n + 1}– 2 colorações; no segundo caso, mais
2^{n + 1}. Logo, teremos 2×2ⁿ⁺¹– 2 = 2^{n + 2}– 2 colorações
(Solução:SBM)