Questão 1 (4pts)
Quantas soluções inteiras não negativas existem para
Quantas soluções inteiras não negativas existem para
Passo 1
O enunciado pede: contar o número de soluções inteiras não negativas da equação
sujeitas às condições
e
.
Informações relevantes dadas:
- Soma total:
. - Restrição 1:
(equivalente a ). - Restrição 2:
. - Procuramos apenas soluções com todas as
inteiras e não negativas.
Passo 2
Transformar a restrição
para trabalhar com variáveis não negativas padrão. Defina
então
e
. Substituindo na soma:
Isolando os termos:
Agora temos uma soma de cinco variáveis não negativas que vale
, com a única restrição ainda sendo
.
Passo 3
Apresentar a ferramenta principal: o princípio “bolinhas e urnas” (stars and bars).
Fato (estendido e explicado): o número de soluções inteiras não negativas da equação
é dado por
Por que isso? Imagine
estrelas colocadas em fila; para dividir essas estrelas em
grupos (cada grupo correspondendo a
) colocam-se
barras entre as estrelas. Cada escolha das posições das
barras entre as
posições determina uma composição dos
em
partes não negativas. Assim contamos as formas de escolher essas posições:
.
Exemplo pequeno (para fixar a ideia): para
(isto é
,
), temos
soluções — pode-se listar e verificar.
Passo 4
Aplicar a fórmula ao problema transformado sem considerar ainda a restrição superior em
.
Aqui
e
. O número total de soluções não negativas de
sem restrição superior é
Calcular
passo a passo:
Compute numerador e denominador:
Logo
Passo 5
Agora impor a restrição
. Usamos contagem por complemento (inclusão-exclusão simples): contamos todas as soluções e subtraímos as que violam a restrição, ou seja, as soluções com
.
Para contar soluções com
, faça a substituição
com
. A equação torna-se
Aqui
e
, portanto o número de soluções com
é
Calcule
:
Passo 6
Aplicar a inclusão-exclusão simples: o número de soluções que satisfazem todas as condições é
Intuição final: começamos contando todas as distribuições possíveis após ajustar
, e então removemos aquelas em que
é grande demais (
). O resultado é o número pedido.
Resposta
3750