1. Suponha que n carros estão em fila para entrar em um estacionamento que possui n vagas, lado a lado. Se o 1^{\circ} carro pode escolher qualquer vaga e cada um dos outros carros ao estacionar deve justapor-se a um carro já estacionado, quantos são os modos possíveis dos carros ocuparem as n vagas?

Passo 1

O enunciado dá as seguintes informações e faz a seguinte pergunta.
  • Informações dadas:
    • \,n\, carros que chegam em fila, numerados pela ordem de chegada como 1,2,\dots,n.
    • O estacionamento tem \,n\, vagas lado a lado, numeradas implicitamente da esquerda para a direita.
    • O 1^{\circ} carro (ou seja, o carro 1) pode escolher qualquer vaga para estacionar.
    • Cada um dos outros carros, quando chega, deve estacionar em uma vaga vazia que seja imediatamente adjacente (justaposta) a alguma vaga já ocupada — ou seja, a vaga escolhida deve ficar ao lado esquerdo ou direito de alguma vaga ocupada, de modo que as vagas ocupadas formem sempre um bloco contínuo.
  • Pergunta pedida:
    • Quantos são os modos possíveis (quantas configurações finais distintas de ocupação das \,n\, vagas pelos carros 1,\dots,n) que podem ocorrer respeitando essa regra de estacionar?

Passo 2

Vamos entender o problema com exemplos pequenos — isso ajuda a ver o padrão antes de provar.
  • Caso \,n=1: só há uma vaga e um carro; claramente existe exatamente 1 modo.
  • Caso \,n=2: primeiro o carro 1 pode escolher uma das duas vagas. Depois o carro 2 só pode ocupar a vaga restante, porque ela é adjacente à ocupada. Os resultados finais são: (1,2) ou (2,1) (lendo as vagas da esquerda para a direita), ou seja, 2 modos.
  • Caso \,n=3: se o carro 1 escolhe uma das vagas das extremidades (esquerda ou direita), então o carro 2 tem só uma escolha (a vaga ao lado), depois o carro 3 fica determinado — essas duas possibilidades (porque 1 podia escolher a esquerda ou a direita) dão 2 modos. Se o carro 1 escolhe a vaga central, o carro 2 tem 2 escolhas (esquerda ou direita), e o carro 3 fica determinado em cada caso — isso dá mais 2 modos. Total 4 modos.
Com esses exemplos observamos os números 1,2,4 para n=1,2,3 — já dá a impressão de que o número pode ser 2^{n-1}. Vamos provar isso de forma clara e didática.

Passo 3

Observação estrutural (a chave da solução): após cada carro estacionar as vagas ocupadas formam sempre um bloco contínuo de vagas adjacentes. Isso porque o primeiro carro ocupa uma única vaga (bloco de tamanho 1) e cada novo carro só pode ocupar uma vaga adjacente ao bloco existente, o que estende esse bloco à esquerda ou à direita. Portanto, em qualquer momento temos um bloco contínuo de vagas ocupadas.
Agora pense na configuração final: ao olharmos as \,n\, vagas da esquerda para a direita, obtemos uma sequência (ordem) dos carros que terminaram estacionados. Quero caracterizar quais sequências são possíveis.

Passo 4

Construção por decisões “esquerda/direita” (bijeção com sequências de escolhas):
  • Considere o processo de chegada na ordem 1,2,\dots,n.
  • No instante em que o carro k chega (para k\ge 2), ele precisa estacionar em uma vaga que seja imediatamente à esquerda ou imediatamente à direita do bloco já ocupado pelos carros 1,\dots,k-1. Portanto, em termos da ordem dos carros ao longo do bloco ocupado, o carro k será colocado ou na extremidade esquerda do bloco ou na extremidade direita do bloco.
  • Logo, para cada k=2,3,\dots,n existe (no plano abstrato das posições relativas dentro do bloco) a decisão “colocar k à esquerda” ou “colocar k à direita” do bloco atual.
Agora vou transformar isso numa contagem precisa. Pegue uma sequência de escolhas
(c_2,c_3,\dots,c_n),
onde cada c_k é ou “L” (left = esquerda) ou “R” (right = direita). A partir dessa sequência construo uma ordem final dos carros da seguinte forma: começo com a lista [1]; para cada k=2,\dots,n insiro k à esquerda da lista se c_k=\mathrm{L} e à direita se c_k=\mathrm{R}. No final obtemos uma lista (permutação) P dos carros 1,\dots,n que representa a ordem, da esquerda para a direita, das vagas ocupadas.
  • Exemplo rápido: para n=4 e escolhas (c_2,c_3,c_4)=(\mathrm{R},\mathrm{L},\mathrm{R}) construímos:
    • Começa [1].
    • c_2=\mathrm{R} [1,2].
    • c_3=\mathrm{L} [3,1,2].
    • c_4=\mathrm{R} [3,1,2,4].
      Isso significa que existe um processo de estacionamento que resulta, da esquerda para a direita, em 3,1,2,4.

Passo 5

Por que essa construção conta exatamente todas as configurações possíveis (e sem repetições)?
  • Existência: dada qualquer sequência de escolhas (c_2,\dots,c_n) a construção acima produz uma ordem P dos carros. Podemos então colocar essa ordem P nas vagas da esquerda para a direita (vagas 1,2,\dots,n). Se quisermos, podemos simular o processo real de estacionamento: o carro 1 estava em algum lugar do bloco; ao chegar 2, pela escolha c_2 ele fica numa extremidade do bloco; ao chegar 3 a escolha c_3 o coloca na extremidade atual, e assim por diante. Portanto cada sequência de L/R corresponde a pelo menos uma maneira válida de preencher as vagas obedecendo à regra de adjacência — isto mostra que a função da sequência de escolhas para uma configuração final é bem definida (existe).
  • Unicidade / injectividade: duas sequências distintas de escolhas (c_2,\dots,c_n) e (c'_2,\dots,c'_n) produzem listas finais P diferentes. Isso é claro porque a construção é determinística: ao inserir k à esquerda ou à direita obtemos posições relativas diferentes para k, e se as escolhas diferem no menor índice em que são diferentes, a posição do correspondente k difere nas listas resultantes. Logo não há colisão: sequências distintas geram ordens distintas.
  • Cobertura / surjectividade: toda configuração final possível (isto é, toda ordenação dos carros que pode resultar do processo real de estacionar obedecendo à regra) pode ser obtida por essa construção: se você tem uma configuração final real, olhe para ela e recupere, para cada k\ge2, se o carro k está à esquerda ou à direita do bloco formado por 1,\dots,k-1 no momento em que k estacionou; isso recupera as escolhas c_k. Assim toda configuração realizável vem de uma sequência de escolhas.
Portanto há uma bijeção entre o conjunto de sequências de escolhas (c_2,\dots,c_n) (cada c_k sendo L ou R) e o conjunto de configurações finais admissíveis.

Passo 6

Contagem final:
  • O número de sequências (c_2,\dots,c_n) em que cada c_k pode ser L ou R é exatamente
2^{n-1},
porque para cada um dos n-1 índices k=2,\dots,n há duas escolhas independentes.
  • Pela bijeção provada no passo anterior, o número de modos possíveis dos carros ocuparem as \,n\, vagas é exatamente \,2^{n-1}\,.

Resposta

2^{n-1}

Exercícios relacionados