★ Desafio: Uma grade de dimensões 2025 \times 2025, deve ser preenchida com os números 0 e 1 , de modo que em qualquer subgrade 2 \times 2 existam exatamente dois 0 's e dois 1 's. De quantas maneiras a grade pode ser preenchida? ( +5,0 pt.)

Passo 1

O enunciado pede: contar de quantas maneiras podemos preencher uma grade de dimensões 2025\times2025 com os números 0 e 1 de modo que, em qualquer subgrade 2\times2, existam exatamente dois 0's e dois 1's.\n
Informações relevantes dadas:
  • A grade tem 2025 linhas e 2025 colunas.
  • Cada célula contém 0 ou 1.
  • Para todo i,j com 1\le i\le 2024 e 1\le j\le 2024, a soma dos quatro elementos da subgrade formada por linhas i,i+1 e colunas j,j+1 é exatamente 2.
  • Precisamos contar todas as matrizes binárias 2025\times2025 que satisfazem essa condição.

Passo 2

Vamos introduzir notação e traduzir a condição matematicamente.\n
Denotemos por a_{i,j}\in\{0,1\} a entrada na linha i e coluna j, com índices 1\le i,j\le 2025. A condição do enunciado escreve-se como:
\text{para todo }1\le i\le 2024,\;1\le j\le 2024:\qquad a_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1}=2.
Uma consequência útil é olhar essa igualdade módulo 2. Reduzindo ambos os lados módulo 2 obtemos:
a_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1}\equiv 0\pmod{2}.
Reescrevendo, para cada i e para todos j,
\bigl(a_{i,j}+a_{i+1,j}\bigr)\equiv\bigl(a_{i,j+1}+a_{i+1,j+1}\bigr)\pmod{2}.
Isto significa que, para linhas consecutivas i e i+1, a paridade da diferença entre as duas linhas é a mesma para todas as colunas.

Passo 3

Da observação do passo anterior concluímos uma propriedade estrutural importante: para cada i\) fixo, os elementos de duas linhas consecutivas \(i\) e \(i+1\) ou são iguais em todas as colunas ou são complementares em todas as colunas. Formalizando, defina \[c_i=\begin{cases} 0,&\text{se }a_{i+1,j}=a_{i,j}\text{ para toda coluna }j,\\\\ 1,&\text{se }a_{i+1,j}=1-a_{i,j}\text{ para toda coluna }j. \end{cases}
Pelo argumento módulo 2\] acima, para cada \(i o valor c_i é bem definido (não depende de j). Assim, cada linha i+1 é ou igual à linha i (quando c_i=0) ou é a complementação bit a bit da linha i (quando c_i=1).

Passo 4

Isso nos dá uma descrição geradora de toda a matriz: se conhecemos a primeira linha r_1=(a_{1,1},\dots,a_{1,2025})\) e a sequência \((c_1,c_2,\dots,c_{2024})\in\{0,1\}^{2024}\), então as demais linhas são determinadas unicamente por \[r_{k+1}=\begin{cases} r_k,&\text{se }c_k=0,\\\ \text{complemento de }r_k,&\text{se }c_k=1. \end{cases}
Portanto cada par (r_1,(c_i))\] gera exatamente uma matriz candidata. Falta apenas impor a condição aritmética exata (soma \(=2), que pode restringir r_1 dependendo da sequência (c_i).

Passo 5

Vamos ver que restrições adicionais aparecem quando algum c_i=0 (isto é, quando existe um par de linhas consecutivas iguais). Tome um índice i tal que c_i=0. Então r_i=r_{i+1}. Aplicando a condição da subgrade 2\times2 nas colunas j e j+1 e nas linhas i,i+1 obtemos, para todo j,
r_i[j]+r_i[j+1]+r_{i+1}[j]+r_{i+1}[j+1]=2.
Como r_{i}=r_{i+1}, isto vira
2\bigl(r_i[j]+r_i[j+1]\bigr)=2\quad\Longrightarrow\quad r_i[j]+r_i[j+1]=1.
Isto vale para todo j, logo a linha r_i (e portanto r_1, já que r_i difere de r_1 no máximo por complementações uniformes) deve ser uma sequência alternante de 0 e 1: ou 0,1,0,1,\dots ou 1,0,1,0,\dots. Em outras palavras, se existe algum c_i=0, então a primeira linha r_1 tem exatamente 2 possibilidades (as duas sequências alternantes).
Por outro lado, se para todos os i temos c_i=1 (ou seja, todas as linhas consecutivas são complementares), então a condição da soma =2 é automaticamente satisfeita para todos os blocos 2\times2 independentemente de r_1. (Isto pode ser verificado substituindo r_{i+1}= complemento de r_i na soma: cada par de entradas aparece com seu complemento e soma =2 se e somente se o total de zeros e uns no bloco for 2; a verificação direta mostra que a igualdade é verdadeira para qualquer r_1.)

Passo 6

Agora contamos as matrizes usando a partição dos casos "todas as c_i=1" e "existe algum c_i=0". Seja n=2025.
  • Caso A: todas as c_i=1. Há exatamente 1 escolha para a sequência (c_i) (toda composta por 1's) e qualquer r_1\in\{0,1\}^n é permitido. Assim obtemos 2^{n} matrizes neste caso.
  • Caso B: existe pelo menos um c_i=0. O número de sequências (c_1,\dots,c_{n-1}) com pelo menos um zero é 2^{\,n-1}-1 (todas as 2^{n-1} sequências menos a sequência com todos 1's). Para cada uma dessas sequências, a primeira linha r_1 tem exatamente 2 possibilidades (as duas alternâncias). Portanto o total neste caso é
2\bigl(2^{\,n-1}-1\bigr)=2^{n}-2.
Somando os dois casos:
\#\text{matrizes} = 2^{n} + \bigl(2^{n}-2\bigr)=2^{n+1}-2.

Passo 7

Aplicando o resultado para n=2025 obtemos o número de preenchimentos pedidos:
\boxed{2^{2026}-2}.
Se quiser, dá um suspiro de alívio: apesar do enunciado parecer assustador pela dimensão, a estrutura imposta pelos blocos 2\times2 dá uma classificação simples que permite contar de forma limpa!

Resposta

2^{2026}-2

Exercícios relacionados