(OBM-06) Seja n inteiro positivo. De quantas maneiras podemos distribuir n+1 brinquedos distintos para n crianças de modo que toda criança receba pelo menos um brinquedo?

Solução:

Perceba que uma das crianças vai receber exatamente dois brinquedos enquanto què as demais n-1 crianças vão receber exatamente um brinquedo. Inicie escolhendo um dos n+1 brinquedos e o separe: n+1 possibilidades. Depois permute os n brinquedos restantes entre os n alunos: n ! fatorial. Agora escolha o aluno que vai ficar com dois brinquedos: n possibilidades. Note, porém, que está se considerando a ordem da distribuição dos brinquedos da criança que vai receber dois brinquedos. Para retirar essa ordem basta dividir tudo por 2!.
Deste modo, a quantidade total de maneiras é: \frac{(n+1) \cdot n!\cdot n}{2!}=\frac{n \cdot(n+1)!}{2}.

Passo 1

O enunciado pede o número de formas de distribuir n+1 brinquedos distintos entre n crianças de modo que cada criança receba pelo menos um brinquedo. O conteúdo usado será o princípio multiplicativo e combinações, além do raciocínio pelo princípio da casa dos pombos.

Passo 2

Como há n+1 brinquedos e n crianças, pelo princípio da casa dos pombos exatamente uma criança ficará com dois brinquedos e as demais receberão exatamente um.

Passo 3

Escolhemos qual criança ficará com dois brinquedos. Isso pode ser feito de n maneiras.

Passo 4

Em seguida, escolhemos quais dois brinquedos dessa criança, dentre os n+1 disponíveis. Há
\binom{n+1}{2}
formas de fazer essa escolha.

Passo 5

Os n-1 brinquedos restantes devem ser distribuídos, um para cada uma das outras n-1 crianças. Como cada brinquedo é distinto, há
(n-1)!
maneiras de atribuir esses brinquedos às demais crianças.

Passo 6

Pelo princípio multiplicativo, o total de distribuições é
n \times \binom{n+1}{2} \times (n-1)!
e, simplificando,
n \times \frac{(n+1)n}{2} \times (n-1)! \;=\;\frac{n(n+1)!}{2}.

Resposta

\displaystyle \frac{n(n+1)!}{2}

Exercícios de Livros Relacionados