★ Desafio: Uma grade de dimensões
, deve ser preenchida com os números 0 e 1 , de modo que em qualquer subgrade
existam exatamente dois 0 's e dois 1 's. De quantas maneiras a grade pode ser preenchida? (
pt.)
Passo 1
O enunciado pede: contar de quantas maneiras podemos preencher uma grade de dimensões
com os números
e
de modo que, em qualquer subgrade
, existam exatamente dois
's e dois
's.\n
Informações relevantes dadas:
Informações relevantes dadas:
- A grade tem
linhas e colunas. - Cada célula contém
ou . - Para todo
com e , a soma dos quatro elementos da subgrade formada por linhas e colunas é exatamente . - Precisamos contar todas as matrizes binárias
que satisfazem essa condição.
Passo 2
Vamos introduzir notação e traduzir a condição matematicamente.\n
Denotemos por a entrada na linha
e coluna
, com índices
. A condição do enunciado escreve-se como:
Denotemos por
Uma consequência útil é olhar essa igualdade módulo
. Reduzindo ambos os lados módulo
obtemos:
Reescrevendo, para cada
e para todos
,
Isto significa que, para linhas consecutivas
e
, 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
Pelo argumento módulo
o valor
é bem definido (não depende de
). Assim, cada linha
é ou igual à linha
(quando
) ou é a complementação bit a bit da linha
(quando
).
Passo 4
Isso nos dá uma descrição geradora de toda a matriz: se conhecemos a primeira linha
Portanto cada par
), que pode restringir
dependendo da sequência
.
Passo 5
Vamos ver que restrições adicionais aparecem quando algum
(isto é, quando existe um par de linhas consecutivas iguais). Tome um índice
tal que
. Então
. Aplicando a condição da subgrade
nas colunas
e
e nas linhas
obtemos, para todo
,
Como
, isto vira
Isto vale para todo
, logo a linha
(e portanto
, já que
difere de
no máximo por complementações uniformes) deve ser uma sequência alternante de
e
: ou
ou
. Em outras palavras, se existe algum
, então a primeira linha
tem exatamente
possibilidades (as duas sequências alternantes).
Por outro lado, se para todos os
temos
(ou seja, todas as linhas consecutivas são complementares), então a condição da soma
é automaticamente satisfeita para todos os blocos
independentemente de
. (Isto pode ser verificado substituindo
complemento de
na soma: cada par de entradas aparece com seu complemento e soma
se e somente se o total de zeros e uns no bloco for
; a verificação direta mostra que a igualdade é verdadeira para qualquer
.)
Passo 6
Agora contamos as matrizes usando a partição dos casos "todas as
" e "existe algum
". Seja
.
-
Caso A: todas as
. Há exatamente escolha para a sequência (toda composta por 's) e qualquer é permitido. Assim obtemos matrizes neste caso. -
Caso B: existe pelo menos um
. O número de sequências com pelo menos um zero é (todas as sequências menos a sequência com todos 's). Para cada uma dessas sequências, a primeira linha tem exatamente possibilidades (as duas alternâncias). Portanto o total neste caso é
Somando os dois casos:
Passo 7
Aplicando o resultado para
obtemos o número de preenchimentos pedidos:
Se quiser, dá um suspiro de alívio: apesar do enunciado parecer assustador pela dimensão, a estrutura imposta pelos blocos
dá uma classificação simples que permite contar de forma limpa!