Pedro deseja pintar quadradinhos de tabuleiros de modo que a quantidade de quadradinhos pintados em qualquer subtabuleiro 3 \times 3 seja sempre um número ímpar. Veja um exemplo em um tabuleiro 4 \times 4 na figura ao lado.
a) Pedro já pintou as duas primeiras linhas de um tabuleiro 3 \times 4. Indique as 4 maneiras diferentes de completar a pintura desse tabuleiro pintando somente casas da última linha.
b) De quantas maneiras ele pode pintar um tabuleiro 3 \times 4?
c) De quantas maneiras ele pode pintar um tabuleiro 4 \times 4?
d) De quantas maneiras ele pode pintar um tabuleiro 2023 \times 2023?
Reportar erro na questãoResolução comentada
Resolução comentada
a) Numerando as colunas de 1 a 4, as duas primeiras linhas têm 1, 2, 1 e 0 casas pintadas, respectivamente. Sejam x_1,\dots,x_4 iguais a 1 se a casa da última linha na coluna correspondente for pintada e 0 se não for.
Há dois subtabuleiros 3\times3:
colunas 1 a 3: 1+2+1+x_1+x_2+x_3 = 4 + x_1+x_2+x_3 deve ser ímpar, então x_1+x_2+x_3 é ímpar;
colunas 2 a 4: 2+1+0+x_2+x_3+x_4 = 3 + x_2+x_3+x_4 deve ser ímpar, então x_2+x_3+x_4 é par.
Escolhendo x_2 e x_3, as paridades fixam x_1 e x_4:
x_2=0,x_3=0: x_1=1 e x_4=0. Pinta-se só a coluna 1.
x_2=1,x_3=0: x_1=0 e x_4=1. Pintam-se as colunas 2 e 4.
x_2=0,x_3=1: x_1=0 e x_4=1. Pintam-se as colunas 3 e 4.
x_2=1,x_3=1: x_1=1 e x_4=0. Pintam-se as colunas 1, 2 e 3.
As 4 maneiras pintam, na última linha: só a casa 1; as casas 2 e 4; as casas 3 e 4; as casas 1, 2 e 3.
b) O raciocínio do item a vale para qualquer pintura das duas primeiras linhas. Existem 2^8=256 pinturas possíveis dessas linhas. Para cada uma, a última linha tem x_2 e x_3 livres e x_1 e x_4 determinados, ou seja, 4 possibilidades.
Total: 256\cdot 4 = 2^{10}.
1024 maneiras.
Outra forma de ver: são 12 casas e 2 condições de paridade, e cada condição divide o total por 2.
c) Num tabuleiro 4\times4 há 4 subtabuleiros 3\times3. Cada um tem uma casa de canto que também é canto do tabuleiro 4\times4 e que não pertence a nenhum outro subtabuleiro. Por isso, cada condição de paridade pode ser satisfeita ajustando essa casa, e as quatro condições não interferem entre si.
As outras 16-4=12 casas podem ser pintadas livremente. Depois, as 4 casas de canto ficam determinadas, cada uma de um único modo.
Total: 2^{12}.
4096 maneiras.
d) Um tabuleiro n\times n tem subtabuleiros 3\times3 cujos cantos inferiores direitos são exatamente as casas (a,b) com a\ge 3 e b\ge 3. São (n-2)^2 casas.
Pinte livremente as outras n^2-(n-2)^2=4n-4 casas, que são as das duas primeiras linhas e das duas primeiras colunas. Depois percorra as demais casas em ordem, linha por linha, da esquerda para a direita. Cada casa (a,b) é o canto inferior direito de um subtabuleiro, cujas outras 8 casas já estão definidas. A paridade ímpar obriga a pintar ou não a casa (a,b), de um único modo.
Assim, o número de pinturas é 2^{4n-4}. Isso confere com n=4, que dá 2^{12}.
