(Olimpiada de Wisconsin-97) Deve-se preencher as 16 casas de um tabuleiro
com as letras
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
. 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
formas diferentes. Para escother os outros 3 elementos da primeira limha temos
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
linha e da
coluna seja a do desenho acima.
Sabemos que
. Suponhamos que
. Assim, temos que:
i)
i)
Ju scja, para
temos 2 possibilidades.
suponhamos que
c. Assim:
Ou seja, para
temos apenas uma possibilidade.
Suponhamos que
. Assim:
Ou seja, para
temos apenas uma possibilidade.
Como para cada conjunto de
coluna e
linha existem 4 outras possibilidades de preencher o quadro, existem (6.24).
possibilidades de preencher o quadro.
a | b | c | d |
b | |||
c | |||
d |
Sabemos que
i)
i)
suponhamos que
Ou seja, para
Suponhamos que
Ou seja, para
Como para cada conjunto de
Passo 1
O problema pede o número de quadrados latinos de ordem 4 usando as letras
, ou seja, matrizes
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
interno.
Passo 2
Fixar a primeira linha. Como é uma permutação de
, existem
formas de escolher a primeira linha.
Passo 3
Fixar a primeira coluna. Após colocar o elemento
, sobram 3 posições na coluna 1 a preencher pelas 3 letras restantes, o que pode ser feito em
formas. Assim, há no total
maneiras de escolher simultaneamente a primeira linha e a primeira coluna.
Passo 4
Restam então preencher o subquadro
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
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