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?
  2. De quantos modos 15 jogadores podem ser divididos em 3 times de basquetebol de 5 jogadores cada, denominados Esperança, Confiança e Vitória?

Passo 1

Questão 26: temos \,n carros em fila (carros numerados por ordem de chegada: 1^{\circ},2^{\circ},\dots,n^{\circ}) e n vagas em linha, lado a lado. O enunciado diz: o 1^{\circ} carro pode escolher qualquer vaga; cada um dos outros carros, quando for estacionar, deve justapor‑se (ou seja, ocupar uma vaga imediatamente à esquerda ou à direita) a um carro já estacionado. A pergunta é: de quantos modos possíveis os carros podem ocupar as \,n vagas, isto é, de quantas formas finais (associação carro ↔ vaga) obedecendo a essa regra existem?
Questão 27: temos 15 jogadores e queremos dividi‑los em 3 times de basquetebol, cada time com 5 jogadores, sendo os times denominados (isto é, os times são distintos: Esperança, Confiança e Vitória). A pergunta é: de quantos modos podemos formar esses três times (considerando que a ordem dentro de cada time não importa, só quem pertence a qual time)?

Passo 2

Vamos atacar a Questão 26. Primeiro, vou traduzir a regra para algo mais manejável: ao longo do processo de entrada, os carros sempre formam um “bloco” contíguo de vagas ocupadas — porquê? porque o primeiro carro ocupa uma vaga isolada e todo carro seguinte tem que estacionar em uma vaga imediatamente adjacente a alguma vaga já ocupada; isso faz com que as vagas ocupadas nunca fiquem com buracos no meio: o conjunto ocupado é sempre um intervalo contíguo na reta das vagas. É importante entender bem esse ponto antes de contar.

Passo 3

Vamos ver exemplos pequenos para sentir o padrão.
  • Para \,n=1: só existe uma vaga e um carro; modos possíveis =1.
  • Para \,n=2: o 1^{\circ} carro escolhe uma das \,2 vagas; o 2^{\circ} carro tem uma única vaga adjacente restante. Modos possíveis =2.
  • Para \,n=3: considere as três vagas numeradas da esquerda para a direita. Se o 1^{\circ} carro escolhe a vaga do meio, o 2^{\circ} carro pode escolher esquerda ou direita (2 opções) e o 3^{\circ} fica na última vaga; se o 1^{\circ} carro escolhe uma das vagas de extremidade, as escolhas são forçadas. Contando todos os casos obtemos 4 modos. Observe a sequência 1,2,4 para n=1,2,3 — já dá pista de uma potência de 2.

Passo 4

Intuição do procedimento: cada carro, no momento em que entra, estaciona numa das duas extremidades do bloco já existente (extremidade esquerda ou extremidade direita). Quando um carro estaciona numa extremidade, ele pode depois deixar essa extremidade disponível para que outro carro venha colar mais para o lado (ou não). Um ponto-chave para contar é ver que, no final, se removermos os carros na ordem inversa (isto é, começamos tirando o último carro que entrou e vamos voltando até o primeiro), em cada etapa o carro removido estará numa extremidade do bloco atual — por quê? porque quando o carro entrou, ele entrou numa extremidade do bloco existente; removendo carros em ordem inversa garantimos que o carro que entrou por último continua sendo uma extremidade (não existem carros posteriores que o tenham envolvido), e assim sucessivamente. Isso garante uma correspondência entre cada configuração final e uma sequência de escolhas “esquerda/direita” feitas nos \,n-1 momentos em que os carros 2,3,\dots,n entraram.

Passo 5

Formalizando a correspondência (bastante usada em combinatória para esse tipo de problema): para cada configuração final válida podemos reconstruir unicamente, lendo os carros da última entrada para a primeira, uma sequência de escolhas onde cada entrada (exceto a primeira) foi feita numa das duas extremidades; essa sequência tem comprimento \,n-1 e cada termo é “L” (esquerda) ou “R” (direita). A reconstrução é única porque, na etapa de remoção inversa, o carro a ser removido tem que estar numa extremidade — então sabemos se, no momento em que entrou, ele escolheu a extremidade esquerda ou a direita do bloco. Assim existe uma bijeção entre:
  • configurações finais válidas, e
  • sequências de \,n-1 escolhas binárias (L ou R).

Passo 6

Contagem: o número de sequências binárias de comprimento \,n-1 é \,2^{\,n-1}. Pela bijeção do passo anterior, o número de configurações finais (isto é, modos possíveis dos carros ocuparem as \,n vagas seguindo a regra) é exatamente
2^{\,n-1}.
Vou reforçar a ideia com uma lembrete intuitivo: o primeiro carro não tem “lado” a escolher (é o primeiro), e cada dos \,n-1 carros seguintes, ao entrar, efetivamente escolhe um dos dois lados do bloco já existente — por isso a potência de 2.

Passo 7

Agora a Questão 27. Vou explicitar o modelo: temos um conjunto de \,15 jogadores distintos. Queremos formar três times distintos (nomes diferentes), cada time com exatamente \,5 jogadores. Dentro de cada time a ordem não importa — só importa quem está no time.

Passo 8

Método direto (sequencial com binomiais): primeiro escolho os \,5 jogadores que irão para o time Esperança. O número de escolhas para isso é
\binom{15}{5}.
Depois, dos \,10 jogadores restantes, escolho os \,5 que irão para o time Confiança:
\binom{10}{5}.
Os \,5 restantes irão automaticamente para o time Vitória:
\binom{5}{5}=1.
Pelo princípio multiplicativo, o total de divisões é
\binom{15}{5}\binom{10}{5}\binom{5}{5}.

Passo 9

Simplificação usando fatoriais (fórmula do binomial): lembrando que
\binom{15}{5}=\dfrac{15!}{5!\,10!}\quad\text{e}\quad \binom{10}{5}=\dfrac{10!}{5!\,5!},
multiplicando obtemos
\binom{15}{5}\binom{10}{5}\binom{5}{5} =\dfrac{15!}{5!\,10!}\cdot\dfrac{10!}{5!\,5!}\cdot 1 =\dfrac{15!}{(5!)^3}.
Observação rápida: se os times não fossem denominados (ou seja, se fossem indistintos), teríamos que dividir ainda por \,3! porque permutar os nomes dos três times não mudaria a divisão. Mas aqui os times têm nomes (Esperança, Confiança e Vitória), então não dividimos por \,3!.

Passo 10

Recapitulando de forma bem direta: para 26 a contagem é feita pela correspondência com sequências de decisões “esquerda/direita” de comprimento \,n-1 e dá \,2^{n-1}. Para 27 usamos escolhas sucessivas com coeficientes binomiais e obtemos \dfrac{15!}{(5!)^{3}}.

Resposta

\;2^{\,n-1}
\;\dfrac{15!}{(5!)^{3}}

Exercícios relacionados