(Olimpiada de Wisconsin-97) Deve-se preencher as 16 casas de um tabuleiro 4 \times 4 com as letras a, b, c, d de tal modo que cada letra apareça precisamente uma vez em cada linha e precisamente uma vez em cada coluna. De quantas formas distintas isto pode ser feito?

Solução:

Designemos cada elemento como uma matriz, sendo cada elemento da forma \mathrm{x}_{\mathrm{ij}}. Inicialmente vamos preencher aleatoriamente a primeira linha e a primeira coluna.
a b c d
b
c
d
Para escolher os 4 elementos da primeira coluna temos 4!=24 formas diferentes. Para escother os outros 3 elementos da primeira limha temos 3!=6 formas distintas. Desta forma, já montamos a primeira linha e a primeira coluna, sendo necessários para isto 6.24 = 144 formas diferentes. Montemos agora os outros elementos. Digamos que a distribuição da 1^{\text {a }} linha e da 1^{\text {a }} coluna seja a do desenho acima.
Sabemos que x_{22} \neq b. Suponhamos que x_{22}=a. Assim, temos que:
i) x_{32}=d \quad x_{42}=c \quad x_{23}=d \quad x_{24}=c \quad x_{33}=a \quad x_{34}=b \quad x_{43}=b \quad x_{44}=a
i) x_{32}=d \quad x_{42}=c \quad x_{23}=d \quad x_{24}=c \quad x_{33}=b \quad x_{34}=a \quad x_{43}=a \quad x_{44}=b
Ju scja, para x_{22}=a temos 2 possibilidades.
suponhamos que x_{22}= c. Assim:
x_{32}=d \quad x_{42}=a \quad x_{23}=d \quad x_{24}=a \quad x_{33}=a \quad x_{34}=a \quad x_{43}=b \quad x_{44}=c
Ou seja, para x_{22}=c temos apenas uma possibilidade.
Suponhamos que x_{22}=d. Assim:
x_{32}=a \quad x_{42}=c \quad x_{23}=a \quad x_{24}=c \quad x_{33}=d \quad x_{34}=b \quad x_{43}=b \quad x_{44}=a
Ou seja, para x_{22}=d temos apenas uma possibilidade.
Como para cada conjunto de 1^{\text {a }} coluna e 1^{\text {a }} linha existem 4 outras possibilidades de preencher o quadro, existem (6.24). 4=576 possibilidades de preencher o quadro.

Passo 1

O problema pede o número de quadrados latinos de ordem 4 usando as letras a,b,c,d, ou seja, matrizes 4\times4 em que cada linha e cada coluna contém exatamente uma vez cada letra. Para contar, vamos fixar a primeira linha e a primeira coluna e depois ver quantas maneiras restam de completar o bloco 3\times3 interno.

Passo 2

Fixar a primeira linha. Como é uma permutação de \{a,b,c,d\}, existem
4! = 24
formas de escolher a primeira linha.

Passo 3

Fixar a primeira coluna. Após colocar o elemento (1,1), sobram 3 posições na coluna 1 a preencher pelas 3 letras restantes, o que pode ser feito em
3! = 6
formas. Assim, há no total
4!\times3! = 24\times6 = 144
maneiras de escolher simultaneamente a primeira linha e a primeira coluna.

Passo 4

Restam então preencher o subquadro 3\times3 formado pelas linhas 2,3,4 e colunas 2,3,4, obedecendo a cada linha e cada coluna usar as letras faltantes. Uma análise caso a caso (por exemplo, escolhendo o valor de x_{22} dentre as 3 opções e completando as demais entradas segundo as restrições) mostra que existem exatamente 4 maneiras de completar esse bloco.

Passo 5

Multiplicando as escolhas iniciais pelas extensões, obtemos
144 \times 4 = 576.

Resposta

\,576

Exercícios de Livros Relacionados