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,F,G,H,I,J,K e impõe estas restrições sobre a ordem de visita:
  • E antes de F.
  • F antes de I.
  • G antes de I.
  • G antes de H.
  • I antes de J.
  • K não pode estar imediatamente antes nem imediatamente depois de F.
  • K não pode estar imediatamente antes nem imediatamente depois de I.
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 \,E \prec F \prec I \prec J\,.
  • Há também G \prec I e G \prec H.
  • Portanto E,F,G devem aparecer antes de I; J deve aparecer depois de I; H deve aparecer depois de G.
  • As únicas restrições de adjacência são sobre K: K não pode ser adjacente a F nem a I.

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 K. Uma observação útil: I tem três predecessores obrigatórios ( E,F,G), logo a posição de I na sequência de 7 só pode ser \,4,5 ou 6 (porque precisam existir ao menos 3 elementos antes dele e ao menos 1 depois dele — o J). Portanto vamos fazer enumeração por casos segundo \operatorname{pos}(I)=4,5,6. Isso divide o problema em subproblemas mais simples e evita enumerar tudo de uma vez.
Vou contar, para cada caso \operatorname{pos}(I)=p, quantas ordens possíveis há respeitando as precedências (sem as restrições de K inicialmente, quando for conveniente), e então aplicar as proibições envolvendo K. Em cada passo explico por que conto assim.

Passo 3

Caso 1: \operatorname{pos}(I)=4.
  • Se I está na posição 4, então as posições 1,2,3 devem conter exatamente os três predecessores obrigatórios E,F,G, com a única ordem forçada entre eles ser E antes de F. Assim as permutações possíveis de \{E,F,G\} com E\prec F são:
    \text{número}=\frac{3!}{2} = 3,ú
    porque entre E e F apenas metade das permutações de \{E,F,G\} respeitam E\prec F.
  • As posições 5,6,7 devem conter \{J,H,K\}. A restrição G\prec H já está satisfeita porque G está em 1,2 ou 3 e H estará em 5,6 ou 7 (todas após G). A restrição I\prec J também está satisfeita ( J está em 5,6 ou 7 depois de I em 4).
  • As proibições para K: K não pode ser imediatamente antes nem depois de I. Como I está em 4, isso proíbe K na posição 3 ou 5. Mas K aqui só pode estar em 5,6,7, então a única posição proibida é a 5. Também K não pode ser adjacente a F, mas F está em 1,2 ou 3, então nenhuma das posições 6,7 está adjacente a F. Logo a única restrição efetiva para colocar K em 5,6,7 é que K\neq5.
  • Portanto, o número de arranjos possíveis para \{J,H,K\} em 5,6,7 é
    3!- \#(\text{arranjos com }K\text{ em }5)=6-2=4,
    porque se fixamos K em 5 2 permutações dos outros dois elementos nas posições 6,7.
  • Multiplicando pelas 3 ordens possíveis de \{E,F,G\} obtemos para este caso:
    3\times 4 = 12.

Passo 4

Caso 2: \operatorname{pos}(I)=6.
  • Se I está na posição 6, então J (que vem depois de I) deve ocupar a única posição depois de 6, isto é, J está forçosamente em 7.
  • As posições 1,2,3,4,5 devem conter \{E,F,G,H,K\} com as precedências E\prec F (entre E,F) e G\prec H (entre G,H). 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 é
    \frac{5!}{2\cdot 2} = \frac{120}{4} = 30,
    porque cada uma das condições E\prec F e G\prec H reduz pela metade o conjunto de permutações independentes.
  • Agora impomos as proibições envolvendo K:
    1. K não pode ser imediatamente antes ou depois de I. Como I está em 6, isso proíbe K na posição 5.
    2. K não pode ser imediatamente antes ou depois de F. Isso proíbe as permutações onde K e F são adjacentes.
  • Vamos subtrair as permutações proibidas por esses critérios a partir dos 30.
    (a) Quantas das 30 têm K na posição 5? Fixando K em 5, restam permutar E,F,G,H em 1,2,3,4 com E\prec F e G\prec H, portanto
    \frac{4!}{2\cdot 2} = \frac{24}{4} = 6.
    Então há 6 arranjos com K em 5.
    (b) Quantas das 30 têm K adjacente a F? Vamos contar as permutações onde K e F são adjacentes (seja K antes de F ou depois). Use o método do bloco:
    • Se formarmos o bloco [K,F] (isto é, K imediatamente antes de F), então o bloco mais os outros dois elementos E,G,H (lembrando a condição E\prec F implica E precisa vir antes do bloco, porque F está dentro do bloco) resulta em permutar 4 “itens” com a restrição E antes do bloco e G\prec H. O número de permutações válidas é \dfrac{4!}{2\cdot 2}=6, mas aqui o bloco já fixa a ordem interna K,F, então dão 6 arranjos.
    • Analogamente, se o bloco for [F,K] ( F imediatamente antes de K), pela mesma razão há mais 6 arranjos.
    • Assim, em total há 6+6=12 arranjos nas 30 em que K e F são adjacentes.
    (c) Alguns desses 12 arranjos de adjacência podem também ter K em posição 5. Contar quantos têm simultaneamente K em 5 e K adjacente a F: se K está em 5 e adjacente a F, então F deve estar em 4 e o bloco é [F,K] colocado nas posições 4,5. Contando permutações com o bloco nas últimas duas posições: fixado esse bloco, os outros três lugares (1,2,3) acomodam E,G,H com E\prec F (já satisfeito pois F está no bloco final) e G\prec H. O número é 3!/2=3. Logo há 3 arranjos que estão em ambas as contagens (adjacência e K em 5).
    (d) Agora aplicamos inclusão-exclusão: o número de arranjos proibidos por (ser K em 5 OU ser adjacente a F) é
    6 + 12 - 3 = 15.
  • Subtrair estes 15 proibidos dos 30 válidos sem restrições dá 30-15=15 arranjos possíveis para as posições 1 a 5. Multiplicando por 1 (pois J em 7 é fixo) obtemos para este caso:
    15.

Passo 5

Caso 3: \operatorname{pos}(I)=5.
  • Se I está na posição 5, então J deve estar em uma das posições 6 ou 7 (já que J é depois de I). Os elementos que precisam estar antes de I são E,F,G, então as posições 1,2,3,4 conterão E,F,G e mais um elemento dentre \{H,K\} (porque J não pode estar antes de I). Assim o quarto elemento antes de I é ou H ou K.
  • Além disso, K não pode ser adjacente a I (posição 5), então K não pode ocupar a posição 4 nem a posição 6. Isso implica:
    • Se K estiver antes de I, ele só pode estar em 1,2 ou 3 (não em 4).
    • Se K estiver depois de I, ele só pode estar em 7 (porque posição 6 fica proibida).
Vamos fazer casos conforme quem está antes de I: H antes (e K depois) ou K antes (e H depois).
Subcaso 3.A: H está entre 1 e 4; então K estará depois de I. Pelo argumento acima, K não pode ser posição 6 (adjacente a I), então K deve ser posição 7. Então J fica forçosamente em 6. Assim as duas últimas posições são fixas: 6=J, 7=K.
  • As quatro primeiras posições 1 a 4 são uma permutação de E,F,G,H com E\prec F e G\prec H. O número de permutações é \frac{4!}{2\cdot 2} = 6.Não há restrição extra de adjacência com K porque K está em 7 e não é adjacente a nenhum elemento em 1\!-\!4. Portanto o total deste subcaso é 6.
Subcaso 3.B: K está entre 1 e 4 (logo K é um dos elementos antes de I); então H estará depois de I (em 6 ou 7), e K não pode ser posição 4 (pois seria adjacente a I). Assim K só pode ocupar posições 1,2,3.
  • As posições 1 a 4 serão uma permutação de \{E,F,G,K\} com a única precedência E\prec F. (A condição G\prec H não impõe nada aqui porque H está depois de I neste subcaso.)
  • As permutações de \{E,F,G,K\} com E\prec F são
    \frac{4!}{2} = 12.
    Dessas, devemos excluir:
    1. As que têm K na posição 4 (proibido por adjacência a I). Quantas tem K em 4? Fixando K em 4 restam E,F,G em 1,2,3 com E\prec F, ou seja \dfrac{3!}{2}=3. Portanto há 3 com K em 4.
    2. As que têm K imediatamente adjacente a F ( K e F juntos em posições consecutivas). Vamos contar quantas das 12 têm K e F adjacentes. Usando o método do bloco:
      • Se o bloco for [K,F]: então o bloco + E,G são 3 itens com restrição que E deve vir antes do bloco (pois F está no bloco); permutações possíveis são \dfrac{3!}{2}=3.
      • Se o bloco for [F,K]: o bloco + E,G, com E antes do bloco, dá também 3.
      • Logo há 3+3=6 arranjos das 12 onde K e F são adjacentes.
    • Entre esses 6 arranjos adjacentes, alguns já tinham K em 4. Quantos têm simultaneamente K em 4 e adjacência? Se K está em 4 e adjacente a F, então F está em 3 e o bloco é [F,K] nas posições 3,4. Contando permutações com esse bloco final, os outros dois lugares 1,2 ocupam E,G com nenhuma restrição além de E\prec F (que já é satisfeita porque F está no bloco final), então há 2 permutações (as duas ordens possíveis de E,G). Portanto há 2 arranjos com ambas as propriedades.
    • Aplicando inclusão-exclusão dentro deste conjunto de 12: número de arranjos proibidos (ou seja, com K em 4 OU com K adjacente a F) é
      3 + 6 - 2 = 7.
    • Assim os arranjos válidos nas posições 1 a 4 neste subcaso são
      12 - 7 = 5.
  • Para cada uma dessas 5 arrumações iniciais, as posições 6,7 são ocupadas por \{J,H\} em qualquer ordem (duas opções), já que H precisa estar depois de G e G está em 1\!-\!4. Portanto o total deste subcaso é
    5 \times 2 = 10.
  • Somando os dois subcasos para \operatorname{pos}(I)=5:
    6 + 10 = 16.

Passo 6

Somando os três casos:
  • \operatorname{pos}(I)=4 deu 12.
  • \operatorname{pos}(I)=5 deu 16.
  • \operatorname{pos}(I)=6 deu 15.
Total de sequências válidas:
12 + 16 + 15 = 43.

Resposta

43

Exercícios relacionados