Quantas são as soluções inteiras e não-negativas de
?
Passo 1
O enunciado pede: contar quantas tripas
existem tais que
,
e
são inteiros não-negativos e satisfazem
Informações dadas:
- As variáveis são inteiras e não-negativas:
. - A condição é uma desigualdade estrita:
.
A pergunta é: qual é o número total de tripletasque obedecem essa condição?
Passo 2
Como
,
e
são inteiros, a desigualdade estrita
é equivalente à desigualdade não-estrita
Explicação curta: se a soma é menor que
e é inteira, então ela vale um dos inteiros
, ou seja, no máximo
. Portanto podemos contar soluções de
o que é mais fácil de tratar.
Passo 3
Estratégia para contar: transformar a desigualdade em uma equação somando uma variável folga (slack). Defina uma variável extra
tal que
Cada solução não-negativa de
corresponde de maneira bijetiva a uma solução não-negativa de
(basta pegar
). Então contamos soluções da equação acima.
Fórmula necessária (e sua intuição): o número de soluções em inteiros não-negativos de
é
Intuição via “stars and bars” (estrelas e barras): represente
unidades por
estrelas e use
barras para separar essas estrelas em
caixinhas (cada caixinha corresponde a uma variável
). Uma sequência de
estrelas e
barras tem comprimento
; escolher as posições das
barras entre essas
posições determina a solução. Logo há
escolhas.
Exemplo concreto para fixar: para
(aqui
e
) a fórmula dá
e de fato as soluções são
.
Passo 4
Aplicando ao nosso caso: agora temos
variáveis
e
. Pelo fórmula,
Calculemos
:
Verificação alternativa (opcional, para confiança): contar por soma
com
. Para cada
o número de soluções de
é
. Somando:
o que coincide com
(identidade do tipo “hockey-stick”).
Passo 5
Portanto o número total de soluções inteiras não-negativas de
é
. Força aí na prova — você consegue!