Enunciado
Um jogo com tabuleiro
e peças:
- Peça A: ocupa 3 quadrados horizontais
- Peça B: ocupa 7 quadrados em formato “L”
- Peça C: ocupa 4 quadrados verticais
a) De quantas formas cada peça pode ser posicionada sem sobreposição?
b) Se B está fixada na
coluna, quantas maneiras
e
podem ser posicionadas?
a) De quantas formas cada peça pode ser posicionada sem sobreposição?
b) Se B está fixada na
Passo 1
Vamos resumir o problema. Temos um tabuleiro de
e três peças:
– Peça
: barra de comprimento 3 quadrados, só na orientação horizontal.
– Peça : letra “L” formada por dois braços de 4 quadrados (um vertical e um horizontal), totalizando
quadrados. Pode ser girada em 4 orientações. O tamanho da “caixa mínima” de
é
.
– Peça : barra de comprimento 4 quadrados, só na orientação vertical.
– Peça
– Peça
Na parte (a) queremos contar, para cada peça isolada, de quantas maneiras ela se encaixa no tabuleiro (sem sair dos limites e sem se auto-sobrepor). Na parte (b) fixamos uma posição de
tal que seu braço vertical ocupe a coluna 3, e contamos de quantas maneiras podemos colocar
e
sem sobreposição com
nem entre si.
Passo 2
Contagem de posições da peça
.
Ela é uma barra , só horizontal. Em cada uma das 4 linhas ela pode começar nas colunas
(se começar em 5 ou 6 sairia do tabuleiro).
Logo o número de posições de é
Ela é uma barra
Logo o número de posições de
Passo 3
Contagem de posições da peça
.
Cada orientação de cabe numa caixa de
. O tabuleiro tem 4 linhas, logo verticalmente só cabe alinhada ao topo. Em colunas, essa caixa de largura 4 pode começar em 1, 2 ou 3 (pois
). São 3 posições horizontais para cada uma das 4 rotações.
Cada orientação de
Passo 4
Contagem de posições da peça
.
É uma barra , só vertical. Em colunas ela pode ocupar qualquer das 6 colunas, e verticalmente só cabe uma vez (4 linhas ocupadas de uma só vez).
É uma barra
Passo 5
Agora parte (b):
está fixada de modo que seu braço vertical ocupe toda a coluna 3. Isso bloqueia esses 4 quadrados da coluna 3 e mais 3 quadrados em outra coluna (o braço horizontal), mas para contar
e
basta notar que em coluna 3 não cabe nada e que o braço horizontal de
também impede quadrados na linha correspondente. No entanto, como o braço horizontal está numa linha fixa ocupando colunas
a
, ele só bloqueia uma linha extra nessa região. Vamos simplificar: a única coluna totalmente bloqueada é a coluna 3, e além disso na linha onde está o braço horizontal bloqueia colunas 4,5,6.
Contagem de posições de
que não intersectam
.
Originalmente tinha 16 posições, mas qualquer barra de 3 quadrados que cruze a coluna 3 ou a linha do braço horizontal de
fica proibida. Note que as únicas posições viáveis de
ficam inteiras nas colunas
, começando na coluna 4. Em cada uma das 4 linhas, há exatamente 1 posição válida (início na coluna 4).
Originalmente
Passo 6
Contagem de posições de
sem sobrepor
.
precisa de uma coluna livre para ocupar 4 quadrados. A coluna 3 está totalmente ocupada por
, então
pode ir em qualquer uma das outras 5 colunas:
Passo 7
Agora contabilizamos pares
sem sobreposição mútua.
– Se ficar na coluna 1 ou 2, não há nenhuma intersecção com as barras de
(que estão em colunas
), então para cada uma dessas 2 colunas temos as 4 posições de
. Total
.
– Se ficar em qualquer coluna de
, ele ocupará todas as 4 linhas dessa coluna e, portanto, conflitará com qualquer posição de
(que também ocupa um desses 4 quadrados). Logo nesses 3 casos não há posição de
compatível.
– Se
– Se
Somando, o total de configurações de
é
Resposta
a)
,
,
b) maneiras de posicionar
e
quando
está fixada na 3ª coluna.
b)