Questão 1 (4pts)
De quantas formas diferentes podemos colocar 20 bolas idênticas em 4 caixas diferentes se cada caixa deve ter pelo menos 2 bolas?
De quantas formas diferentes podemos colocar 20 bolas idênticas em 4 caixas diferentes se cada caixa deve ter pelo menos 2 bolas?
Passo 1
O enunciado pede: de quantas formas diferentes podemos colocar
bolas idênticas em
caixas diferentes, sabendo que cada caixa deve conter pelo menos
bolas.
Informações importantes extraídas do enunciado:
Informações importantes extraídas do enunciado:
- Há
bolas idênticas. - Há
caixas distintas (ou seja, a identificação das caixas importa). - Restrição: em cada caixa deve haver pelo menos
bolas.
A pergunta é: contar o número de distribuições (arranjos) possíveis que satisfaçam essas condições.
Passo 2
Modelagem matemática: denoto por
o número de bolas na caixa
, para
. Então as condições do enunciado viram:
com
Aqui
são números inteiros não negativos (na verdade inteiros
). O objetivo é contar o número de soluções inteiras dessa equação sob as restrições dadas.
Passo 3
Técnica padrão para esse tipo de restrição “cada variável tem pelo menos um mínimo” é retirar o mínimo de cada variável e trabalhar com variáveis não-negativas. Defino:
Como
, segue que
. Substituindo na soma:
Daí
Portanto, contar as distribuições originais é equivalente a contar as soluções em inteiros não negativos de
com
.
Passo 4
Agora vou ensinar o princípio que usamos: “stars and bars” (estrelas e barras). A versão que usaremos diz: o número de soluções em inteiros não negativos de
é
Explicação intuitiva (sem jargão): imagine
estrelas alinhadas (cada estrela representa uma unidade a distribuir) e
barras que separam as
caixas. Cada arranjo distinto de estrelas e barras corresponde a uma distribuição distinta. No total há
posições e basta escolher em quais posições ficarão as
barras, daí o número de escolhas é
. Aqui:
-
é o total de unidades a distribuir (no nosso caso ), -
é o número de caixas (no nosso caso ).
Portanto o número de soluções é
Passo 5
Cálculo explícito do binômio:
Faço simplificações fáceis para evitar cálculo pesado:
e
. Assim
Calculando passo a passo:
e
.
Passo 6
Interpretação final: existem
distribuições diferentes de
bolas idênticas em
caixas distintas com pelo menos
bolas em cada caixa.