Questão 5 (Nível 3) da 2ª fase da OBMEP 2019

Question

Um tabuleiro preenchido com as letras A, B, C e D é bacana se essas quatro letras aparecem em qualquer quadriculado 2\times 2 do tabuleiro. Por exemplo, dos tabuleiros abaixo, o da esquerda é bacana e o da direita não é bacana.

C	D	C
A	B	A
C	D	C

C	B	C
C	D	A
A	C	B

a) Preencha os tabuleiros abaixo de modo que eles sejam bacanas e diferentes entre si.

A	B
C	D

A	B
C	D

A	B
C	D

b) Quantos tabuleiros bacanas 2\times 8 existem?

Grade retangular quadriculada com 2 linhas e 8 colunas vazias

c) Quantos tabuleiros bacanas 8\times 8 existem?

Grade quadrada quadriculada com 8 linhas e 8 colunas vazias

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 5 (Nível 3) da 2ª fase da OBMEP 2019

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

Um tabuleiro preenchido com as letras A, B, C e D é bacana se essas quatro letras aparecem em qualquer quadriculado 2\times 2 do tabuleiro. Por exemplo, dos tabuleiros abaixo, o da esquerda é bacana e o da direita não é bacana.

C	D	C
A	B	A
C	D	C

C	B	C
C	D	A
A	C	B

a) Preencha os tabuleiros abaixo de modo que eles sejam bacanas e diferentes entre si.

A	B
C	D

A	B
C	D

A	B
C	D

b) Quantos tabuleiros bacanas 2\times 8 existem?

Grade retangular quadriculada com 2 linhas e 8 colunas vazias

c) Quantos tabuleiros bacanas 8\times 8 existem?

Grade quadrada quadriculada com 8 linhas e 8 colunas vazias

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a)

A	B	A
C	D	C
A	B	A

A	B	C
C	D	A
A	B	C

A	B	A
C	D	C
B	A	B

b) No caso 2 \times 8, uma vez escritas as letras nas quatro casas do primeiro quadrado 2 \times 2 da esquerda, cada coluna seguinte pode ser preenchida de 2 modos; logo, há 4!\, 2^6 = 1536 modos de preenchimento.

c) Vamos ao tabuleiro 8 \times 8. Fixemos momentaneamente um preenchimento do quadrado 2 \times 2 superior esquerdo. Vimos em b) que há 2^6 = 64 maneiras diferentes de se preencherem as duas primeiras linhas do tabuleiro 2 \times 8, mantendo o preenchimento do quadrado superior esquerdo 2 \times 2 que fixamos.

Dentre essas 64 possibilidades, uma delas é tal que na primeira linha do tabuleiro aparecem apenas duas letras que se alternam. Nesse caso, a segunda linha também tem alternância de duas letras em seu preenchimento, e essa alternância está determinada de modo único devido ao preenchimento do quadrado superior esquerdo 2 \times 2 que fixamos inicialmente. Assim, nesse caso, nas demais 6 linhas também deve ocorrer alternância de duas letras e, portanto, há 2^6 = 64 possibilidades de preenchimento.

Nos outros 63 casos (em que não há alternância de duas letras na primeira linha), estando as duas primeiras linhas do tabuleiro corretamente preenchidas, há um único preenchimento para as demais linhas.

Logo, há 64 + 63 = 2^6 + 2^6 - 1 = 2^7 - 1 = 127 possibilidades de preenchimento, uma vez fixado o quadrado o preenchimento do quadrado superior esquerdo 2 \times 2. Como esse quadrado pode ser preenchido de 4! formas distintas, o tabuleiro 8 \times 8 pode ser preenchido de 4! \times 127 = 3048 maneiras diferentes.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Com o canto 2\times2 já preenchido (A B / C D), cada linha ou cada coluna nova precisa repetir um padrão de duas letras alternadas. Três preenchimentos diferentes que funcionam:

A	B	A
C	D	C
A	B	A

A	B	A
C	D	C
B	A	B

A	B	C
C	D	A
A	B	C

Confira os quatro quadrados 2\times2 de cada um: todos têm A, B, C e D. Os três são diferentes entre si. Os três tabuleiros acima (há outras possibilidades).

b) Preencha coluna por coluna.

A 1ª coluna tem duas letras distintas: 4\cdot 3=12 maneiras.
A coluna seguinte forma um 2\times2 com a anterior, então precisa conter as duas letras que faltam. Elas podem entrar em 2 ordens.
Isso vale para cada uma das 7 colunas restantes, e a escolha de uma coluna não limita a outra além disso.

12\cdot 2^{7}=12\cdot128=1536

1536 tabuleiros.

c) Vale este fato: em um tabuleiro bacana, ou todas as linhas são alternadas (do tipo x\,y\,x\,y\dots), ou todas as colunas são alternadas.

Por quê? Em duas linhas vizinhas, os conjuntos de letras das colunas se alternam entre S e o complementar de S. Suponha que alguma linha tenha três letras seguidas distintas a,b,c (e d a quarta letra). Abaixo de a,b estão c,d. Abaixo de b,c estão a,d. Logo, abaixo de a\,b\,c vem c\,d\,a, que de novo tem três letras distintas. Assim, nas colunas ímpares só aparecem a e c, e nas pares só b e d. Cada 2\times2 exige as duas letras, então cada coluna alterna. Se nenhuma linha tem três letras distintas seguidas, todas as linhas são alternadas.

Contagem.

Linhas alternadas: a 1ª linha é decidida pelas duas primeiras letras, com 12 maneiras. Cada uma das outras 7 linhas usa o par complementar, em 2 fases. Total: 12\cdot2^7=1536.
Colunas alternadas: por simetria, 1536.
Linhas e colunas ao mesmo tempo: o tabuleiro fica determinado pelo canto 2\times2, com 4!=24 maneiras. Elas foram contadas duas vezes.

1536+1536-24=3048

3048 tabuleiros.

Assunto: Princípio fundamental da contagem.

Reportar erro na resolução

Ver como caiu na prova

Questão 5 no caderno Nível 3 da 2ª fase da OBMEP 2019

Fonte: OBMEP 2ª fase 2019 · Nível 3. Prova oficial ↗