1.1.1.5. Inspetor:
O Inspetor de Ensino vai visitar sete escolas, E, F, G, H, I, J e K. As seguintes condições devem ser obedecidas quanto à ordem em que as escolas serão visitadas:
- O Inspetor visita E antes de F.
- O Inspetor visita F antes de I.
- O Inspetor visita I depois de G.
- O Inspetor visita H depois de G.
- O Inspetor visita J depois de I.
- O Inspetor não visita K imediatamente antes ou imediatamente depois de visitar F .
- O Inspetor não visita K imediatamente antes ou imediatamente depois de visitar I.
Passo 1
O enunciado dá sete escolas:
e impõe estas restrições sobre a ordem de visita:
-
antes de . -
antes de . -
antes de . -
antes de . -
antes de . -
não pode estar imediatamente antes nem imediatamente depois de . -
não pode estar imediatamente antes nem imediatamente depois de .
O que vamos responder (pressuposição razoável, dado o enunciado): contar de quantas maneiras distintas o Inspetor pode ordenar as sete visitas respeitando todas as condições acima. Ou seja, determinar o número total de permutações das sete escolas que satisfazem todas as relações dadas.
Informações relevantes (resumindo as restrições em forma de precedências):
- Há uma cadeia
. - Há também
e . - Portanto
devem aparecer antes de ; deve aparecer depois de ; deve aparecer depois de . - As únicas restrições de adjacência são sobre
: não pode ser adjacente a nem a .
Passo 2
Planejamento do método (sem resolver ainda): como há precedências (tipo ordem parcial) vamos contar ordenações lineares (extensões topológicas) do poset formado pelas precedências, e depois eliminar as que violam as proibições de adjacência de
. Uma observação útil:
tem três predecessores obrigatórios (
), logo a posição de
na sequência de 7 só pode ser
ou
(porque precisam existir ao menos 3 elementos antes dele e ao menos 1 depois dele — o
). Portanto vamos fazer enumeração por casos segundo
. Isso divide o problema em subproblemas mais simples e evita enumerar tudo de uma vez.
Vou contar, para cada caso
, quantas ordens possíveis há respeitando as precedências (sem as restrições de
inicialmente, quando for conveniente), e então aplicar as proibições envolvendo
. Em cada passo explico por que conto assim.
Passo 3
Caso 1:
.
-
Se
está na posição , então as posições devem conter exatamente os três predecessores obrigatórios , com a única ordem forçada entre eles ser antes de . Assim as permutações possíveis de com são: porque entree apenas metade das permutações de respeitam . -
As posições
devem conter . A restrição já está satisfeita porque está em ou e estará em ou (todas após ). A restrição também está satisfeita ( está em ou depois de em 4). -
As proibições para
: não pode ser imediatamente antes nem depois de . Como está em , isso proíbe na posição ou . Mas aqui só pode estar em , então a única posição proibida é a . Também não pode ser adjacente a , mas está em ou , então nenhuma das posições está adjacente a . Logo a única restrição efetiva para colocar em é que . -
Portanto, o número de arranjos possíveis para
em é porque se fixamosem há permutações dos outros dois elementos nas posições . -
Multiplicando pelas
ordens possíveis de obtemos para este caso:
Passo 4
Caso 2:
.
-
Se
está na posição , então (que vem depois de ) deve ocupar a única posição depois de , isto é, está forçosamente em . -
As posições
devem conter com as precedências (entre ) e (entre ). Não há outra precedência entre esses cinco elementos. -
Primeiro conte as permutações destas cinco com as duas precedências: o número total sem mais restrições éporque cada uma das condições
e reduz pela metade o conjunto de permutações independentes. -
Agora impomos as proibições envolvendo
: -
não pode ser imediatamente antes ou depois de . Como está em , isso proíbe na posição . -
não pode ser imediatamente antes ou depois de . Isso proíbe as permutações onde e são adjacentes.
-
-
Vamos subtrair as permutações proibidas por esses critérios a partir dos
. (a) Quantas dastêm na posição ? Fixando em , restam permutar em com e , portanto Então háarranjos com em . (b) Quantas dastêm adjacente a ? Vamos contar as permutações onde e são adjacentes (seja antes de ou depois). Use o método do bloco: - Se formarmos o bloco
(isto é, imediatamente antes de ), então o bloco mais os outros dois elementos (lembrando a condição implica precisa vir antes do bloco, porque está dentro do bloco) resulta em permutar 4 “itens” com a restrição antes do bloco e . O número de permutações válidas é , mas aqui o bloco já fixa a ordem interna , então dão arranjos. - Analogamente, se o bloco for
( imediatamente antes de ), pela mesma razão há mais arranjos. - Assim, em total há
arranjos nas em que e são adjacentes.
(c) Alguns dessesarranjos de adjacência podem também ter em posição . Contar quantos têm simultaneamente em e adjacente a : se está em e adjacente a , então deve estar em e o bloco é colocado nas posições . Contando permutações com o bloco nas últimas duas posições: fixado esse bloco, os outros três lugares (1,2,3) acomodam com (já satisfeito pois está no bloco final) e . O número é . Logo há arranjos que estão em ambas as contagens (adjacência e em ). (d) Agora aplicamos inclusão-exclusão: o número de arranjos proibidos por (serem OU ser adjacente a ) é - Se formarmos o bloco
-
Subtrair estes
proibidos dos válidos sem restrições dá arranjos possíveis para as posições a . Multiplicando por (pois em 7 é fixo) obtemos para este caso:
Passo 5
Caso 3:
.
-
Se
está na posição , então deve estar em uma das posições ou (já que é depois de ). Os elementos que precisam estar antes de são , então as posições conterão e mais um elemento dentre (porque não pode estar antes de ). Assim o quarto elemento antes de é ou ou . -
Além disso,
não pode ser adjacente a (posição ), então não pode ocupar a posição nem a posição . Isso implica: - Se
estiver antes de , ele só pode estar em ou (não em 4). - Se
estiver depois de , ele só pode estar em (porque posição 6 fica proibida).
- Se
Vamos fazer casos conforme quem está antes de
:
antes (e
depois) ou
antes (e
depois).
Subcaso 3.A:
está entre
e
; então
estará depois de
. Pelo argumento acima,
não pode ser posição
(adjacente a
), então
deve ser posição
. Então
fica forçosamente em
. Assim as duas últimas posições são fixas:
,
.
- As quatro primeiras posições
a são uma permutação de com e . O número de permutações é Não há restrição extra de adjacência com porque está em e não é adjacente a nenhum elemento em . Portanto o total deste subcaso é .
Subcaso 3.B:
está entre
e
(logo
é um dos elementos antes de
); então
estará depois de
(em
ou
), e
não pode ser posição
(pois seria adjacente a
). Assim
só pode ocupar posições
.
-
As posições
a serão uma permutação de com a única precedência . (A condição não impõe nada aqui porque está depois de neste subcaso.) -
As permutações de
com são Dessas, devemos excluir:- As que têm
na posição (proibido por adjacência a ). Quantas tem em ? Fixando em restam em com , ou seja . Portanto há com em . - As que têm
imediatamente adjacente a ( e juntos em posições consecutivas). Vamos contar quantas das têm e adjacentes. Usando o método do bloco: - Se o bloco for
: então o bloco + são itens com restrição que deve vir antes do bloco (pois está no bloco); permutações possíveis são . - Se o bloco for
: o bloco + , com antes do bloco, dá também . - Logo há
arranjos das onde e são adjacentes.
- Se o bloco for
-
Entre esses
arranjos adjacentes, alguns já tinham em . Quantos têm simultaneamente em e adjacência? Se está em e adjacente a , então está em e o bloco é nas posições . Contando permutações com esse bloco final, os outros dois lugares ocupam com nenhuma restrição além de (que já é satisfeita porque está no bloco final), então há permutações (as duas ordens possíveis de ). Portanto há arranjos com ambas as propriedades. -
Aplicando inclusão-exclusão dentro deste conjunto de
: número de arranjos proibidos (ou seja, com em OU com adjacente a ) é -
Assim os arranjos válidos nas posições
a neste subcaso são
- As que têm
-
Para cada uma dessas
arrumações iniciais, as posições são ocupadas por em qualquer ordem (duas opções), já que precisa estar depois de e está em . Portanto o total deste subcaso é -
Somando os dois subcasos para
:
Passo 6
Somando os três casos:
-
deu . -
deu . -
deu .
Total de sequências válidas:
Resposta
43