- Suponha que
carros estão em fila para entrar em um estacionamento que possui
vagas, lado a lado. Se o
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
vagas?
Passo 1
O enunciado dá as seguintes informações e faz a seguinte pergunta.
-
Informações dadas:
- Há
carros que chegam em fila, numerados pela ordem de chegada como . - O estacionamento tem
vagas lado a lado, numeradas implicitamente da esquerda para a direita. - O
carro (ou seja, o carro ) 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.
- Há
-
Pergunta pedida:
- Quantos são os modos possíveis (quantas configurações finais distintas de ocupação das
vagas pelos carros ) que podem ocorrer respeitando essa regra de estacionar?
- Quantos são os modos possíveis (quantas configurações finais distintas de ocupação das
Passo 2
Vamos entender o problema com exemplos pequenos — isso ajuda a ver o padrão antes de provar.
-
Caso
: só há uma vaga e um carro; claramente existe exatamente modo. -
Caso
: primeiro o carro pode escolher uma das duas vagas. Depois o carro só pode ocupar a vaga restante, porque ela é adjacente à ocupada. Os resultados finais são: ou (lendo as vagas da esquerda para a direita), ou seja, modos. -
Caso
: se o carro escolhe uma das vagas das extremidades (esquerda ou direita), então o carro tem só uma escolha (a vaga ao lado), depois o carro fica determinado — essas duas possibilidades (porque podia escolher a esquerda ou a direita) dão 2 modos. Se o carro escolhe a vaga central, o carro tem 2 escolhas (esquerda ou direita), e o carro fica determinado em cada caso — isso dá mais 2 modos. Total modos.
Com esses exemplos observamos os números
para
— já dá a impressão de que o número pode ser
. 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
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
. - No instante em que o carro
chega (para ), ele precisa estacionar em uma vaga que seja imediatamente à esquerda ou imediatamente à direita do bloco já ocupado pelos carros . Portanto, em termos da ordem dos carros ao longo do bloco ocupado, o carro será colocado ou na extremidade esquerda do bloco ou na extremidade direita do bloco. - Logo, para cada
existe (no plano abstrato das posições relativas dentro do bloco) a decisão “colocar à esquerda” ou “colocar à direita” do bloco atual.
Agora vou transformar isso numa contagem precisa. Pegue uma sequência de escolhas
onde cada
é 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
; para cada
insiro
à esquerda da lista se
e à direita se
. No final obtemos uma lista (permutação)
dos carros
que representa a ordem, da esquerda para a direita, das vagas ocupadas.
- Exemplo rápido: para
e escolhas construímos: - Começa
. -
→ . -
→ . -
→ .
Isso significa que existe um processo de estacionamento que resulta, da esquerda para a direita, em.
- Começa
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
a construção acima produz uma ordem dos carros. Podemos então colocar essa ordem nas vagas da esquerda para a direita (vagas ). Se quisermos, podemos simular o processo real de estacionamento: o carro estava em algum lugar do bloco; ao chegar , pela escolha ele fica numa extremidade do bloco; ao chegar a escolha 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
e produzem listas finais diferentes. Isso é claro porque a construção é determinística: ao inserir à esquerda ou à direita obtemos posições relativas diferentes para , e se as escolhas diferem no menor índice em que são diferentes, a posição do correspondente 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
, se o carro está à esquerda ou à direita do bloco formado por no momento em que estacionou; isso recupera as escolhas . 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
(cada
sendo L ou R) e o conjunto de configurações finais admissíveis.
Passo 6
Contagem final:
- O número de sequências
em que cada pode ser L ou R é exatamente
porque para cada um dos
índices
há duas escolhas independentes.
- Pela bijeção provada no passo anterior, o número de modos possíveis dos carros ocuparem as
vagas é exatamente .